Wiener’s Attack

适用情况：
Wiener 表示如果满足：d<13n14d < \frac{1}{3} n^{\frac{1}{4}}，且 q<p<2qq < p < 2q，那么一种基于连分数（一个数论当中的问题）的特殊攻击类型就可以危害 RSA 的安全，通过 Wiener’s Attack 可以在多项式时间中分解 nn。

原理

直接上 Tr0y 师傅的博客文章：
https://www.tr0y.wang/2017/11/06/CTFRSA/index.html#低解密指数攻击

例子

2018picoctf：Super Safe RSA 2
每次 nc 连接可以获得不同的 cc、nn、ee。
例如一次连接中：

1
2
3
c: 27420976989291704853290942746692975639118638546067791801590979188047771542047787039580073164232184357645332167377536880357294473233587818671582569240436649745729337106688606707116526797597394519249817893131017053447035933993749956812524229683939314908415241390539611886521068601651355848422704542765488436854
n: 69988650330983375636872769052203818680340664553703450665990964469273736786617696120792164947740009300429031158862390894445991532951186399745338277739956748329285117725077102271964774512969566292237059962743570575241572400229054824465463170558697192026957786636086030806458003635105353720825305471780313159973
e: 4306944577640965469025251042732166573657840611335368059812648728269236926628151554925535212692608107002613526156095373259390632045899793249201966433087347582154469798178033266929734684449587674782655126590266569766563017074437592833170157173467749170261972368285470573484819815433505903223073580421828377345

可以看到 ee 非常大，即 dd 较小，可以尝试使用 Wiener’s Attack。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import gmpy2
from Crypto.Util.number import *

def continuedFra(x, y):
    cF = []
    while y:
        cF += [x / y]
        x, y = y, x % y
    return cF

def Simplify(ctnf):
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)

def calculateFrac(x, y):
    cF = continuedFra(x, y)
    cF = map(Simplify, (cF[0:i] for i in xrange(1, len(cF))))
    return cF

def solve_pq(a, b, c):
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) / (2 * a), (-b - par) / (2 * a)

def wienerAttack(e, n):
    for (d, k) in calculateFrac(e, n):
        if k == 0: continue
        if (e * d - 1) % k != 0: continue
        phi = (e * d - 1) / k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return abs(int(p)), abs(int(q))
    print 'not find!'

c = 27420976989291704853290942746692975639118638546067791801590979188047771542047787039580073164232184357645332167377536880357294473233587818671582569240436649745729337106688606707116526797597394519249817893131017053447035933993749956812524229683939314908415241390539611886521068601651355848422704542765488436854
n = 69988650330983375636872769052203818680340664553703450665990964469273736786617696120792164947740009300429031158862390894445991532951186399745338277739956748329285117725077102271964774512969566292237059962743570575241572400229054824465463170558697192026957786636086030806458003635105353720825305471780313159973
e = 4306944577640965469025251042732166573657840611335368059812648728269236926628151554925535212692608107002613526156095373259390632045899793249201966433087347582154469798178033266929734684449587674782655126590266569766563017074437592833170157173467749170261972368285470573484819815433505903223073580421828377345

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

可以得到 flag：picoCTF{w@tch_y0ur_Xp0n3nt$_c@r3fu11y_5689652}

Common Private Exponent Attack

若同一个私钥 dd 生成多个公钥 ee、NN，则可以通过构造格，使用 LLL 算法格基规约，从而得到 dd。

原理

若同一个私钥 dd 生成 rr 个公钥 ee、NN，令 M=⌊Nr1/2⌋M = \lfloor {N_r}^{1/2} \rfloor，则构造格：

B=[Me1e2⋯er0−N10⋯000−N2⋯0⋮⋮⋮⋱⋮000⋯−Nr]B = \begin{bmatrix} M & e_1 & e_2 & \cdots & e_r \\ 0 & -N_1 & 0 & \cdots & 0 \\ 0 & 0 & -N_2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 &0 & \cdots &-N_r \\ \end{bmatrix}

使用 LLL 算法得到 bb，则：

d=∣b1∣Md = \frac{| b_1 |}{M}

攻击能成功的条件是：

d<Nrδd < {N_r}^\delta

其中：

δ<12−12(r+2)−log⁡Nr6\delta < \frac{1}{2} - \frac{1}{2(r+2)} - \log_{N_r}{6}

具体的论文：Lattice Based Attack on Common Private Exponent RSA

例子

SCTF 2020 RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from random import randint
flag = int('SCTF{*******************}'.encode('hex'), 16)
d = getPrime(randint(380, 385))

for _ in range(3):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    fn = (p - 1) * (q - 1)
    e = inverse(d, fn)
    c = pow(flag, e, n)
    print 'e'+str(_)+str('=')+hex(e)
    print 'n'+str(_)+str('=')+hex(n)
    print 'c'+str(_)+str('=')+hex(c)

可以计算出，在 NN 最小的情况下 Nrδ{N_r}^\delta 的位数为 408 位，dd 最大只有 385 位，因此是可以算出的。

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

e0=0x2a22f9f4b74d667d5bfb78e11a52d47d049930ddf93269258521851699b8bfa9a6f83e81380b09a6e9c55756c1d2560e8441bac79e8d3af03bc414736c3c5b6c8c8045002898605be5e88432be1f247768bfebb0fa6fece6d379c023fc8d5157e6c451c28d34a9a831276d0685a60f5de30fd98df2300c705fb4fd053e8a8747L
n0=0x6f7747b79c0650eb6b530173ae9998f6274ba1586a71b8e7b066d56af3be6476e4abb11a84b2aeace0dab5acc7afdbbd2ef25c791a4c4c92cd4c530859c8e450b27c7bb991241fdc6aec8d3651a59f4677c37b679a2ae688b000bf094fe99b8c3f97a8dc08358cffc91988fe8c5cba8ef62fe4f570063db3e01fb7fbb89f675fL
e1=0xad9569e0d12678a089db52cf337909d63f781328ecfe81adf649e024992240ea5a10b119a7a4b358b1b20c0ac8fa40701ee466d97ccc4185c2ecb8f383b5f7a051d49517f773c89b3d78405f9d478b791aebaa49e11163139ff21bfda4734790c5197247ecd8ae25f0b384294e6b833b0a81b30426a3e731a38747d63be53d7L
n1=0xb5988f6c136b444755242f05f8863b5709a070c7edb237bd788caa29bf4cdf8f205692ee5008a90b25c8758cd714bada60d5ec1c05cd7ff730324028f6540a8de4318d5c39c08fcab5f3cb03ea297ed992fcb81cf4f8b57140c38deea0926027ae97b5caf0524993690b1905b245dbb3dd7866b3bbd494b0e2e4d25f9c951cffL
e2=0x305aa901bbadedb5caed2585ea8d4549abb19451206ec09e6d7161b6e1b7db8156bd2272b0022b057012c43b9f6df3de816d984cf2277e933551991f3e964a30195512c26e2582cc39ce45bed5606759e434b9948cbcc3d786d00909c7ff562eb6e31170705b84de3b2e7adf1f8b4766f55550588da1b4ef51874f8f4837a4dfL
n2=0x8e849207c1b8868ad30245ca969ec9e76fc51ffd032340dd862c578d96c6ee5bcc9494ed4fe388ef709322c7bc107503eacad9ee616decf67a0d581b08cd9c855a2f70a20660d16cbfa0aaf1afa4b7a6e8bbb5b110cfb8ab30ad3e540fc0a170af7135225e81407bd6f7fae9a835d16d7688d57699a031b500eb74544a1243b1L

M = floor(n2**0.5)
B = Matrix(ZZ, 4, 4)
B[0, 0] = M
B[0, 1] = e0
B[0, 2] = e1
B[0, 3] = e2
B[1, 1] = -n0
B[2, 2] = -n1
B[3, 3] = -n2
b = B.LLL()
d = int(abs(b[0][0]) / M)

c0=0x58fa8ba6e443d89684edc2b8bb1e7e5ba5f5abc61bb46595a9817fd36f9afc32113395dd72bb386b24804ce6a0023ca5a9b526fe3c83be1d0e742b4010be68b695d9a38d84035dd86ea6d01eecfd30092173922b84fc8ec241ff6a3b4943817b42fb03d4523acc5596e2cdef467fbfa62bb87557d82acd3ee2eed7833e6cd635L
print long_to_bytes(pow(c0, d, n0))

参考文章

https://www.tr0y.wang/2017/11/06/CTFRSA/index.html#低解密指数攻击