RSA维纳攻击

适用情况

e过大或过小

在e过大或过小的情况下,可使用算法从e中快速推断出d的值。

原理

我不生产原理,我只是原理的搬运工

Wiener 表示如果满足:

d < 1 3 n 1 4 d<\frac{1}{3}n^{\frac{1}{4} } d<31​n41​

那么一种基于连分数(一个数论当中的问题)的特殊攻击类型就可以危害 RSA 的安全。此时需要满足:

q<p<2q

如果满足上述条件,通过 Wiener Attack 可以在多项式时间中分解 n,思路如下:

回想一下 RSA:

N = pq

φ(n)=(p−1)(q−1)=pq−(p+q)+1=N−(p+q)+1

∵ p, q 非常大,∴ pq≫p+q,∴φ(n)≈N

∵ed≡1 mod φ(n),∴ed−1=kφ(n),这个式子两边同除 dφ(n) 可得:

e ϕ ( n ) − k d = 1 d ϕ ( n ) \frac{e}{\phi(n) } -\frac{k}{d} =\frac{1}{d\phi(n)} ϕ(n)e​−dk​=dϕ(n)1​

∵φ(n)≈N,∴ e N − k d = 1 d ϕ ( n ) \frac{e}{N } -\frac{k}{d} =\frac{1}{d\phi(n)} Ne​−dk​=dϕ(n)1​,同样 dφ(n) 是一个很大的数,所以 e N \frac{e}{N} Ne​ 略大于 k d \frac{k}{d} dk​

为啥要这么写呢,因为 e 和 N 是我们是知道的,公钥中给我们的,所以我们计算出 e N \frac{e}{N} Ne​ 后,比它略小的 k d \frac{k}{d} dk​ 怎么出来呢,计算 e N \frac{e}{N} Ne​ 的连分数展开,依次算出这个分数每一个渐进分数,由于 e N \frac{e}{N} Ne​ 略大于 k d \frac{k}{d} dk​,wiener 证明了,该攻击能精确的覆盖 k d \frac{k}{d} dk​(论文刚不动,只知道结论)

我们来举个例子,现在有一个 rsa, e = 42667, N = 64741,我们来求。第一步,我们把分数 e/N 连分数展开,以此求出每一个渐进分数:0,1, 1/2, 2/3 …用 1/2 举例子:

假设 1/2 成立,则把 k=1, d=2 代入上面的 ed−1=kφ(n) 中,显然 e,d,k 都有了,φ(n) 就有了,知道 φ(n) 有啥用呢?我们知道 φ(n) = pq - (p + q) + 1 = N - (p + q) + 1,N = pq 作为公钥我们是知道的,所以知道了 φ(n) 我们只要算出 N- φ(n)+1 就是(p + q)的值,好回到初三,现在知道了 pq,和 p+q 的值,我们如何求出 p 和 q 的值呢?很简单,利用韦达定理,我们可以轻松构造出方程 x 2 − ( p + q ) ∗ x + p q = 0 x^{2}−(p+q)∗x+pq=0 x2−(p+q)∗x+pq=0, 这个方程的两个根就是我们要求的 p,q, 至此 rsa 中所有的参数都被我们求了出来

运用

脚本是不会写的,其实原理都没看明白

不过github上已经有现成的了:链接

直接工具脚本一把梭:

打开RSAwienerHacker.py,里面有两个函数test_hack_RSA()和hack_RSA(),test_hack_RSA函数是测试用的,没啥用处;要用的时候直接调用hack_RSA()就行了,传e和n进去,会返回d

示例:

from Crypto.Util.number import *
from gmpy2 import *
from RSAwienerHacker import *

n= 76230002233243117494160925838103007078059987783012242668154928419914737829063294895922280964326704163760912076151634681903538211391318232043295054505369037037489356790665952040424073700340441976087746298068796807069622346676856605244662923296325332812844754859450419515772460413762564695491785275009170060931
e= 19252067118061066631831653736874168743759225404757996498452383337816071866700225650384181012362739758314516273574942119597579042209488383895276825193118297972030907899188520426741919737573230050112614350868516818112742663713344658825493377512886311960823584992531185444207705213109184076273376878524090762327
c= 51129364468759654610691969029018077135681286452403720342930701227318278867902499808039789577625318001225092301902887105131054762178225243088434961189430225241008880599986750881642671737591885881772112932433413661123951666955204365852817050308723133101090183352917490942744092495494108693783108146041173249096

d=hack_RSA(e,n)
flag=long_to_bytes(pow(c,d,n))
print(flag)

上一篇:JavaCV的摄像头实战之三:保存为mp4文件


下一篇:Python基础:字符串中的切片str[0:-1]