私钥指数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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
import sympy
from Crypto.Util.number import *

c = 22730870187133824324228675028117719550579621786418410526433100555421216509259768701063565651266713330221394301821668831223255476258881502843661708776486213017448587923997208274122378818946333107741608407342804195868790855142625983288511254090514372470131276375144076089598269204646767312177621796428736728779967346731402588695917885955114228627009295430425202646751794085374803222427127171168036666137030163093226584796480954717301747457923221177748142824518187223837731561778325379781411390051057906848738310752921703160792769865774953181344017055711236733055653549542184666937065858845681633154289319670141744685821
d = 26726287944521640632422343371230419277658354157697493437848975145530800646605865709471623616770488965112778966249609776887374434442211532587075378073876211312538193428479825062818439199304719862941756118534589788930247976456136331055648585746347994380079256912072146307223403059094649022213246309789504624591638215417355054012913053608606606577298923393727744298441232636338936667361418534859035982127016422412924117909281554088263602987915485505812048625240137550194262581012426172058829812858913321942575214848228043509335135828219719831811741940623535219880892439456864253983636953337106852529668688824017189739713

e = 65537
ed1 = e*d - 1
for k in range(1, e):
    if ed1%k == 0:
        #print(k)
        tphi = ed1 // k
        tp = gmpy2.iroot(tphi,2)[0]
        tp = gmpy2.next_prime(tp)
        tq = tphi//(tp-1)+1
        if tphi%(tp-1) == 0 and isPrime(tq):
            n = tp*tq
            m = pow(c,d,tp*tq)
            print(long_to_bytes(m))

这里可以通过e，d，phi的位数推算k的位数进行爆破。

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)