知识点

如果按照正确的方式来进行 RSA 的密钥生成、密钥管理和加解密流程，本质上是不会有太多问题的。

本篇即是生成密钥时，随机产生的质数 $p,q$​ 之间的差异不合安全要求，过大或者过小，进而存在安全隐患。

针对本篇所述的分解方法，已经在很多工具中集成了，如 sage， yafu，但是对于一个数程序是不能判断应该用哪种方式来进行分解才是更正确的，所以它会一个方法一个方法的试，所以简单的还是自己写，这样更高效。

费马分解法

若两个质数 $p$ 和 $q$ 之间差异过小，则可以利用 费马分解法 进行模数 $n$​ 的分解。

设模数 $n$ 的一个平方根为 $r$ ，即 $r^2=n$​ ，而已知 $n$ 求解其平方根还是很容易的。

则此时质数 $p$ 和 $q$ 一定在 $r$​ 附近。且 $p,q$ 差异越小，两者都越接近 $r$ 。

这一点非常好理解，就不用证明了。

那么用在解题中，可以通过对 $n$ 开平方根，取整数部分，再在附近进行质数枚举，则能很快找到 $n$ 的因子。这个时间复杂度取决于 $p,q$ 之间的差异大小。

Pollard-Rho 算法

这个算法写出证明和方法相对较长，网上也有很多现成的轮子，很多工具中也自动集成了，如 sage，yafu。所以这里就只提一句，更多可以查阅这个文章，介绍的挺详细的。

Pollard-Rho 就是构建了一个伪随机数生成器，然后不停用生成的随机数去判断是不是模数 $n$ 的一个根。

例题：p、q 差异过小

题目

你听说过谁是费马吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from secret import flag
import random
from Crypto.Util.number import bytes_to_long, getPrime

def gen_key(bits):
    r = random.randint(2000, 114514)
    while True:
        p = getPrime(512)
        q = getPrime(512)
        if 0<abs(p-q) < r:
            return p, q

p, q = gen_key(512)

e = 65537

n = p * q

m = bytes_to_long(flag)

c = pow(m, e, n)
print(n)
print(e)
print(c)
"""
60185696829890545473600170921138252864153435891956616117644363495163559822563769896054913574845863472188996832864617702604328522459504366334588582295263609846454984890704732984706982761296838507648353985279219183393135318354667468753697423633600885651727153265159767882153899093544960378089443673265025951881
65537
47718150793477839679806558768100680079555002273921723382643988605574000939130306295135268945769825749520550037156868227443731910814546030486586991385210729480621455049708606985496992422482157265389691283804955247415395652735364225781339696709539445429053107848713145715781012426812830318108548123420917501606
"""

题解

题目给了点提示，说的费马，所以还是很容易想到使用费马分解法的。

那就废话不多说，直接开始写分解脚本，然后得到 flag。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
from Crypto.Util.number import long_to_bytes

n = 60185696829890545473600170921138252864153435891956616117644363495163559822563769896054913574845863472188996832864617702604328522459504366334588582295263609846454984890704732984706982761296838507648353985279219183393135318354667468753697423633600885651727153265159767882153899093544960378089443673265025951881
e = 65537
c = 47718150793477839679806558768100680079555002273921723382643988605574000939130306295135268945769825749520550037156868227443731910814546030486586991385210729480621455049708606985496992422482157265389691283804955247415395652735364225781339696709539445429053107848713145715781012426812830318108548123420917501606

r = gmpy2.iroot(n, 2)[0]

while True:
    if n % r == 0:
        p = r
        q = n // r
        break
    r = gmpy2.next_prime(r)

phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)

flag = long_to_bytes(m)
print(flag)
# b'flag{baby_RSA_Fermat_decompose_by_closly_pq}'

使用 yafu 也能很快地分解出来。

image-20210811190659812

例题2

Pollard rho 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from secret import flag
import random
from Crypto.Util.number import bytes_to_long, getPrime

p = getPrime(64)
q = getPrime(960)

e = 65537

n = p * q

m = bytes_to_long(flag)

c = pow(m, e, n)
print(n)
print(e)
print(c)
"""
109545997692908640119778180616615467137263427346363802157101552308802035492583042305484510872534250590204633890244012206473254944461578586731214479823902016210524858119992792343323857591801815602755298907816653745787237243249250754438184465780079300046955351380874983219424509804046044155105420624134928950593
65537
60835437241864616192646285092530462791482725574153065942344577805774055748070517968700896734457803124921034248954830110681513200207051446917051984997517664598318213803834381020228321147094302180952863972870121774478463815061457961638522310049125447256023780435286831159331599643037004105968056930196956357111
"""

题目明确告诉了是 Pollard rho 那就跑呗。

这边使用 yafu 和 sage 都可以很快地跑出来。

sage分解

yafu分解

所以就可以很快地写出来脚本

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

p = 11639886772540103443
q = 9411259734187523103027675618443565372807125050899515342998490623549273883177328780379175308588514434780739787574605085438293481576063488642974019749445750913039827524375474045314235436032681283099464284573452668138513029067298857272645063686634812862494880622038134429507982478626463225051
n = 109545997692908640119778180616615467137263427346363802157101552308802035492583042305484510872534250590204633890244012206473254944461578586731214479823902016210524858119992792343323857591801815602755298907816653745787237243249250754438184465780079300046955351380874983219424509804046044155105420624134928950593
e = 65537
c = 60835437241864616192646285092530462791482725574153065942344577805774055748070517968700896734457803124921034248954830110681513200207051446917051984997517664598318213803834381020228321147094302180952863972870121774478463815061457961638522310049125447256023780435286831159331599643037004105968056930196956357111

phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)

flag = long_to_bytes(m)
print(flag)
# b'flag{baby_RSA_Fermat_decompose_by_far_pq}'

结语

虽然上面的列题全是笔者一拍脑门想的，（这也就说明 CTF 中要么不这么考，要么考了不会这么明显告诉你可以去分解。

但是这其实也启示了我们，如果拿到一个题实在没有招了，可以先用各种工具来跑着分解着 $n$ 再去想其他办法，万一就分解成功了呢？