私钥指数d的相关攻击

1.d泄露攻击:

可攻击特征:

首先当 d 泄露之后,我们自然可以解密所有加密的消息。我们甚至还可以对模数 N 进行分解。

原理:

我们知道e * d ≡ 1 (mod phi) -> e * d = k * phi + 1

所以如果得到e和d的话我们可以暴力k得到phi(一般根据phi的位数作为判断条件)

这样我们就得到了phi,如果q为p下一个素数,则可以对phi开根号,向前和向后分别取素数得到p,q。

2.Wiener’s Attack:

参考自 (20条消息) RSA之初学维纳攻击_rreally的博客-CSDN博客_维纳攻击

维纳攻击简介:

适用情况:e过大。

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

Wiener 表示如果满足:

1
d < 1/3 * pow(n,1/4)         d 小于 3分之一乘以n的四分之一次方

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

1
q < p < 2q

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

1
2
3
4
5
6
7
8
9
10
11
N = pq

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

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

∵ed≡1modφ(n),
∴ed−1=kφ(n),
∴ed−kφ(n)=1

这个式子两边同除 dφ(n)

可得:

1
2
3
4
5
e/φ(n)− k/d= 1 /dφ(n)

∵φ(n)≈N,

∴e/N − k/d= 1 /dφ(n)

同样 dφ(n) 是一个很大的数,所以 e /N 略大于 k /d, e 和 N 是我们是知道的,公钥中给我们的,所以我们计算出来 e /N后,比它略小的 k / d 用计算 e /N 的连分数展开,依次算出这个分数每一个渐进分数,由于 e /N 略大于k/ d,wiener 证明了,该攻击能精确的覆盖 k/d。

例题:
在不分解n的前提下,求d。

给定:

e = (很大)

n =

说明过程。

按照求解的渐进分数的分子分母分别对应减数的分子分母,从头将所有的渐进分数的分子分母求解出来。

exp:

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
45
46
47
import gmpy2
def transform(x,y): #使用辗转相处将分数 x/y 转为连分数的形式
res=[]
while y:
res.append(x//y)
x,y=y,x%y
return res

def continued_fraction(sub_res):
numerator,denominator=1,0
for i in sub_res[::-1]: #从sublist的后面往前循环
denominator,numerator=numerator,i*numerator+denominator
return denominator,numerator #得到渐进分数的分母和分子,并返回


#求解每个渐进分数
def sub_fraction(x,y):
res=transform(x,y)
res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res))))) #将连分数的结果逐一截取以求渐进分数
return res

def get_pq(a,b,c): #由p+q和pq的值通过维达定理来求解p和q
par=gmpy2.isqrt(b*b-4*a*c) #由上述可得,开根号一定是整数,因为有解
x1,x2=(-b+par)//(2*a),(-b-par)//(2*a)
return x1,x2

def wienerAttack(e,n):
for (d,k) in sub_fraction(e,n): #用一个for循环来注意试探e/n的连续函数的渐进分数,直到找到一个满足条件的渐进分数
if k==0: #可能会出现连分数的第一个为0的情况,排除
continue
if (e*d-1)%k!=0: #ed=1 (mod φ(n)) 因此如果找到了d的话,(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
continue

phi=(e*d-1)//k #这个结果就是 φ(n)
px,qy=get_pq(1,n-phi+1,n)
if px*qy==n:
p,q=abs(int(px)),abs(int(qy)) #可能会得到两个负数,负负得正未尝不会出现
d=gmpy2.invert(e,(p-1)*(q-1)) #求ed=1 (mod φ(n))的结果,也就是e关于 φ(n)的乘法逆元d
return d
print("该方法不适用")


e =
n =
d=wienerAttack(e,n)
print("d=",d)`

当然,python中有winner attack库,可以直接使用:

1
2
3
4
5
6
7
8
import  RSAwienerHacker

N =
e =

d = RSAwienerHacker.hack_RSA(e,N)
if d:
print(d)

3.扩展 Wiener’s Attack:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from gmpy2 import invert
c =
e2 =
e1 =
N =
a = 0.356#731./2049
M1=N**0.5
M2= N **(a+1)
D = diagonal_matrix(ZZ,[N,M1,M2,1])
M=matrix(ZZ,[[1,-N,0,N**2],[0,e1,-e1,-e1*N],[0,0,e2,-e2*N],[0,0,0,e1*e2]])*D
L=M.LLL()
t=vector(ZZ,L[0])
x=t*M**(-1)
phi = int(x[1]/x[0]*e1)
d = invert(0x10001,phi)
m=pow(c,d,N)
print long_to_bytes(m)