RSA私钥相关攻击

Wiener’s Attack

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

原理

直接上 Tr0y 师傅的博客文章:
https://www.tr0y.wang/2017/11/06/CTFRSA/index.html#%E4%BD%8E%E8%A7%A3%E5%AF%86%E6%8C%87%E6%95%B0%E6%94%BB%E5%87%BB

例子

2018picoctf:Super Safe RSA 2
每次 nc 连接可以获得不同的 $c$、$n$、$e$。
例如一次连接中:

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

可以看到 $e$ 非常大,即 $d$ 较小,可以尝试使用 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}

参考文章

https://www.tr0y.wang/2017/11/06/CTFRSA/index.html#%E4%BD%8E%E8%A7%A3%E5%AF%86%E6%8C%87%E6%95%B0%E6%94%BB%E5%87%BB