RSA 加密算法是一种非对称加密算法，算法的可靠性由极大整数因数分解的难度决定，到目前为止，还没有任何可靠的攻击 RSA 算法的方式。

基础

RSA 概要

  1. 随机选择两个不同大质数 pp 和 qq，计算 n=p×qn = p \times q。
  2. 根据欧拉函数，求得 φ(n)=(p−1)(q−1)\varphi (n) = (p-1)(q-1)。
  3. 选择一个小于 φ(n)\varphi (n) 的整数 ee，使 ee 和 φ(n)\varphi (n) 互质，即 gcd(e,φ(n))=1gcd(e, \varphi (n)) = 1。
  4. 求得 ee 关于 φ(n)\varphi (n) 的模逆元 dd，有 ed≡1  mod φ(n)ed \equiv 1\ \bmod \varphi (n)。
  5. 将 pp 和 qq 的记录销毁。(n,e)(n,e) 是公钥对，(n,d)(n,d) 是私钥对。
  6. 加解密：c=me mod nc = m^e \bmod n， m=cd mod nm = c^d \bmod n。其中 mm 为明文，cc 为密文，要求 0≤m<n0 \leq m < n

简单 RSA 解密

分析 pem 公钥文件

有的题目不会直接给出公钥对 (n,e)(n,e)，而是会给出 pem 公钥文件，这时就需要分析公钥文件了。例如有 public.key：

1
2
3
4
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhANmelSKWptlg38JQSrpUW5RC1gp7npMK
/0UceOxV1VXrAgMBAAE=
-----END PUBLIC KEY-----

用 pycrypto 库直接得到公钥对：

1
2
3
4
5
from Crypto.PublicKey import RSA
with open('public.key', 'r') as f:
    key = RSA.importKey(f)
print 'n =', key.n
print 'e =', key.e
1
2
n = 98432079271513130981267919056149161631892822707167177858831841699521774310891
e = 65537

分析密文

同样的，有的题也不会直接给出密文 cc，而是给出加密后的文件，我们需要将之转换为整数。例如有encrypted.message1，按字节输出：

1
b'\x0b9\xcc\x1ba'\xd3\xbb\xed+\xc0E\x14\x8c\x91\x1dFy\x85\xa9K\x14~\xde\x80u\x0f\x95\xa3`\xd4z'

可以看到是字节与 ascii 码混合的形式。将之转换为整数：

1
2
3
4
from Crypto.Util.number import *

c = bytes_to_long(open('encrypted.message1', 'rb').read())
print 'c =', c
1
c = 5077560311513279671817430508125151837396585328082180175253360345086848717946

分解n

最简单的情况是可以直接分解 nn 得到 pp 和 qq。
查询已知的 nn 的可分解情况：
http://factordb.com/
当 pp 和 qq 相差较大或较小时可使用yafu快速分解：

1
$ yafu-x64.exe factor(12345)

此处要注意 Status，判断是否成功分解。具体含义如下：

Status Meaning
C Composite, no factors known
CF Composite, factors known
FF Composite, fully factored
P Definitely prime
Prp Probably prime
U Unknown
Unit Just for “1”

将之前的 nn 分解可得到：

1
2
p = 302825536744096741518546212761194311477
q = 325045504186436346209877301320131277983

计算私钥d并求得明文

利用 gmpy2 库进行大数精确计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
from Crypto.Util.number import *

n = 98432079271513130981267919056149161631892822707167177858831841699521774310891
p = 302825536744096741518546212761194311477
q = 325045504186436346209877301320131277983
# 检验 n == p * q
assert p * q == n	
e = 65537
d = gmpy2.invert(e, (p - 1) * (q - 1))
c = 5077560311513279671817430508125151837396585328082180175253360345086848717946
# 计算 m
m = pow(c, d, n)
print 'd =', d
print 'm =', m
# 将整数明文转换为字符串
print long_to_bytes(m)
1
2
3
d = 1958518567680136759381316911808879057130620824462099039954817237801766103617
m = 4158303007256248428645717132056961048040890469299157691939817852236882442
         flag{3b6d3806-4b2b

可以得到部分 flag。将三个密文按此解密后，可得到完整flag：flag{3b6d3806-4b2b-11e7-95a0-000c29d7e93d}

参考文章

https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory/
https://xz.aliyun.com/t/2446#toc-2