共私钥d的RSA攻击

攻击原理

不深究数学原理

对于RSA给出的r个式子满足：

$$ \begin{align*} e_1 d &= 1 + k_1 \phi(N_1) \\ e_2 d &= 1 + k_2 \phi(N_2) \\ &\ \vdots \\ e_r d &= 1 + k_r \phi(N_r) \end{align*} $$

私钥指数d相同，模数N大小相似，且满足

$$ N_1 < N_2 < N_3 < .... < Nr < 2N_1 $$

$ϕ(N_r)=N_i−s_i$,

$$ 在 RSA 中，模数N=pq，欧拉函数 \varphi(N) = (p-1)(q-1) = pq - p - q + 1 = N - (p+q) + 1 \\ 令 s = p + q - 1，那么 \varphi(N) = N - s $$

在攻击中，$ϕ(N_r)$未知，所以可以将其转换成N-s，

$$ 所以e_i d = 1 + k_i \varphi(N_i)\\ 就变成了 e_i d = 1 + k_i (N_i - s_i) \quad\Rightarrow\quad e_i d - N_i k_i = 1 - k_i s_i $$

令$M=\sqrt{N_r}$这样就可以根据这个方程构造格：

$$ dM=dM\\ e_1d-N_1k_1=1-k_1s_1\\ e_2d-N_2k_2=1-k_2s_2\\ ...\\ e_rd-N_rk_r=1-k_rs_r\\ $$

构造过程：

$$ d\begin{pmatrix} M \\ e_1 \\ e_2 \\ ... \\ e_r\end{pmatrix}+k_1\begin{pmatrix} 0 \\ -N_1 \\0 \\ ... \\ 0\end{pmatrix}+k_2\begin{pmatrix} 0 \\ 0 \\-N_2 \\ ... \\ 0\end{pmatrix}+...+k_r\begin{pmatrix} 0 \\ 0 \\0 \\ ... \\ -N_r\end{pmatrix}=\begin{pmatrix} dM \\ 1-k_1s_1 \\1-k_2s_2 \\ ... \\ 1-k_rs_r\end{pmatrix} $$

转置得到这个矩阵来进行LLL：

$$ \begin{pmatrix} M &e_1 &e_2 & \dotsb &e_r \\ 0 & -N_1 & 0 & \dotsb & 0 \\ 0 & 0 & -N_2 & \dotsb & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dotsb & -N_r \end{pmatrix} $$

题

 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


from Crypto.Util.number import *
from random import randint
from secret import flag

flag = bytes_to_long(flag)
d = getPrime(randint(370, 390))


def enc(i):
    print()
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = inverse(d, phi)
    c = pow(flag, e, n)
    print(f'e_{i} =', e)
    print(f'n_{i} =', n)
    print(f'c_{i} =', c)


if __name__ == '__main__':
    for i in range(3):
        enc(i)

# e_0 = 37389635736858807810703086504264263440188928763651776502954117173983775626039037008534821321761858567723984257427640816113325770208734640385635663643682102780255726244659849205653007212192504491177021176624605722718152646889627480051142935241036578957272339153039961711802753021931124235464986935316295647379
# n_0 = 87704526707772151782606625126900349506318713860335977395824997219721333991491994027303721441548488339412359519408127174109547119019245873976917916080340858937125736650376514406944094998893225164676363063781400756374403299951466867573215964360920244878373810391250391475087527409213204756990192602517961590163
# c_0 = 78656123855003406993963573497876652287109947684890741747390020445306861422604130132525802389554149844489256622057009394678814584233565675702142297935509191018145970589418173328145004732595569847696022333024124469320873194195223535859964387627938665526123562969554622541694399263934496631337485091067073489148

# e_1 = 28535169211141109871379321582501492434722235009040085167442370469971731780018594508141105234950857774463438226249819106596920677559656398153362076685288045484306156454558741088396794170762527953573082734587618137075161676392362016474076363311708889307420903699720319611668580377903356783222664068961626803615
# n_1 = 134298877057487865189085342936485527664167450453080897084604607959501054859295769447683135156167266222961308751016451904929475702646252122360203167489936020076488657815646993920082535307414536854323149177250531362615850689341066360635074886835720438532107976530111551202845697404444502476862934946146194420313
# c_1 = 3208711484494445700905074340207543865325589037128163311082565190422756093807236786011349707275838139469873445326457948489588753029946395247710197747538418278782966047404435385208682596795152082296050804126524129644617710791433973098499266439604632728957505961744280687343384601998774018570047292904007768763

# e_2 = 27653153186459366670449283776658896188717513017934031993526241644501850206894800647711159987946276669184047769965182746812351757618147642060630769822810070480507035319320426666128599562714143342910248758055424582501972900763786232170145957578683616604737178839977216709381529813768748145393798635858691196687
# n_2 = 82113192811251631639012300385672674439485256963081847790431181633372052788107703751257606763043873164706839243919206719171536710944060815484051324239120708906418093409305166299531826404505861042666985630956832163750255358332156122245372899824101210233079028706971698312018388678352739819636695333269309456613
# c_2 = 79145689398302968140315554300835109898158799236562716569497147385375487041207363302776833573990584370222316102267792795080448018216133931915984139305260191001847394275311719986838969706049641052337337102739487620502723651258075501409442088938776353037366614208693030741599888985069155346722608948495955447606

构造格

$$ \begin{pmatrix} M & e_0 & e_1 & e_2 \\ 0 & -n_0 & 0 & 0 \\ 0 & 0 & -n_1 & 0 \\ 0 & 0 & 0 &-n_2 \end{pmatrix} $$

 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


import gmpy2
from sage.all import *
e_0 = 37389635736858807810703086504264263440188928763651776502954117173983775626039037008534821321761858567723984257427640816113325770208734640385635663643682102780255726244659849205653007212192504491177021176624605722718152646889627480051142935241036578957272339153039961711802753021931124235464986935316295647379
n_0 = 87704526707772151782606625126900349506318713860335977395824997219721333991491994027303721441548488339412359519408127174109547119019245873976917916080340858937125736650376514406944094998893225164676363063781400756374403299951466867573215964360920244878373810391250391475087527409213204756990192602517961590163
c_0 = 78656123855003406993963573497876652287109947684890741747390020445306861422604130132525802389554149844489256622057009394678814584233565675702142297935509191018145970589418173328145004732595569847696022333024124469320873194195223535859964387627938665526123562969554622541694399263934496631337485091067073489148

e_1 = 28535169211141109871379321582501492434722235009040085167442370469971731780018594508141105234950857774463438226249819106596920677559656398153362076685288045484306156454558741088396794170762527953573082734587618137075161676392362016474076363311708889307420903699720319611668580377903356783222664068961626803615
n_1 = 134298877057487865189085342936485527664167450453080897084604607959501054859295769447683135156167266222961308751016451904929475702646252122360203167489936020076488657815646993920082535307414536854323149177250531362615850689341066360635074886835720438532107976530111551202845697404444502476862934946146194420313
c_1 = 3208711484494445700905074340207543865325589037128163311082565190422756093807236786011349707275838139469873445326457948489588753029946395247710197747538418278782966047404435385208682596795152082296050804126524129644617710791433973098499266439604632728957505961744280687343384601998774018570047292904007768763

e_2 = 27653153186459366670449283776658896188717513017934031993526241644501850206894800647711159987946276669184047769965182746812351757618147642060630769822810070480507035319320426666128599562714143342910248758055424582501972900763786232170145957578683616604737178839977216709381529813768748145393798635858691196687
n_2 = 82113192811251631639012300385672674439485256963081847790431181633372052788107703751257606763043873164706839243919206719171536710944060815484051324239120708906418093409305166299531826404505861042666985630956832163750255358332156122245372899824101210233079028706971698312018388678352739819636695333269309456613
c_2 = 79145689398302968140315554300835109898158799236562716569497147385375487041207363302776833573990584370222316102267792795080448018216133931915984139305260191001847394275311719986838969706049641052337337102739487620502723651258075501409442088938776353037366614208693030741599888985069155346722608948495955447606
M,exact = gmpy2.iroot(n_2,2)
M=ZZ(M)
L = matrix([
    [M,0,0,0],
    [e_0,-n_0,0,0],
    [e_1,0,-n_1,0],
    [e_2,0,0,-n_2]
]).T
print(L.LLL())
Md = L.LLL()[0][0]        
d = Md//M
print(d)
print(long_to_bytes(pow(c_0,d,n_0)))