维纳攻击(wiener attack)

标签（空格分隔）： RSA

原理

这是一个基于连分数的攻击
可以看看这个文章 连分数

wiener attack 是依靠连分数进行的攻击方式，适用于非常接近某一值（比如1）时，求一个比例关系，通过该比例关系再来反推关键信息就简单很多。

这种攻击对于解密指数d很小时有很好的效果，一般的用法是

通过ed mod φ(n)=1

得到 ed=k*φ(n)+1

即 e/φ(n)=k/d+1/φ(n)

这种情况下φ(n)≈n，且φ(n)非常大

所以有 e/N - k/d = 1/φ(n)，也就是说k/d与e/N非常接近，而e/N又是已知的

对e/N进行连分数展开，得到的一串分数的分母很有可能就是d

然后基于这个，列出的$[a_0,a_1,…a_i]$ 反推 形成的完整分数的分子,分母$p_i,q_i$
此时有个定义

$p_0 = 0,p_1 = 1$
$q_0 = 1,q_1 = 0$

然后递推公式是
$pᵢ = aᵢ × pᵢ₋₁ + pᵢ₋₂$
$qᵢ = aᵢ × qᵢ₋₁ + qᵢ₋₂$
此时可以一直递推然后获得d的疑似值，在进行验证，便爆破出了

例题

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

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)   #取个512比特的随机质数
N = p * q
phi = (p-1) * (q-1)
while True:
    d = getRandomNBitInteger(200)  #生成恰好为200比特的随机数
    if GCD(d, phi) == 1:
        e = inverse(d, phi)
        break

c = pow(m, e, N)

print(c, e, N, sep='\n')

# 37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066
# 46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
# 86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289

Exp

1
2
3
4
5
6
7
8
9
from RSAwienerHacker import hack_RSA
import libnum
e=46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
n=86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289
d=hack_RSA(e,n)
print(d)
enc=37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066
m=pow(enc ,d ,n)
print(libnum.n2s(m))