RSA维纳攻击及其扩展

RSA两种特殊攻击情况

P和q的不当分解

|p-q|很大时，一定存在某个参数ip较小，这里我们假设p较小我们可以通过穷举法分解模数，但是很少遇到

|p-q|较小

$(p+q)^2/4-n=(p-q)^2/4$;

|p-q|较小，那么(p-q)/2和n^1/2^也比较接近

  • 顺序检查 √nn 的每一个整数 x，直到找到一个 x 使得 x2−nx2−n 是平方数，记为 y2y2
  • 那么 x2−n=y2x2−n=y2，进而根据平方差公式即可分解 N

举例

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 Crypto.Util.number import getPrime
import random

# 生成 p 和 q
p = getPrime(1024)
q = gmpy2.next_prime(p, p + 10000) 
n = p * q

print("p=",p)
print("q=",q)
print("n=",n)
def factor(n):
    a = gmpy2.iroot(n, 2)[0] #a可以看作p+q
    while True:
        a+=1
        b2 = a * a - n  #

        if gmpy2.is_square(b2):#判断b2是否是全平方
            b2 = gmpy2.mpz(b2)  # 转换为大整数
            b, xflag = gmpy2.iroot(b2, 2) #返回元组
            assert xflag  # 如果能平方返回True
            return (a - b, a + b)

print(factor(n))

一个变式题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import gmpy2
from flag import flag
assert flag[:5]==b'flag{'
​
m1 = bytes_to_long(flag[:20])
p  = getPrime(512)
p1 = gmpy2.next_prime(p)
q  = getPrime(512)
q1 = gmpy2.next_prime(q)
n1 = p*q*p1*q1
print('n1 =',n1)
e = 0x10001
c1 = pow(m1,e,n1)
print('c1 =',c1)
​

这里有n=四个素数因子乘积

上述可以分为两种。。(p,q)(p1,q1)…(p,q1)(p1,q)这两组每组两个元素乘积相近，可以利用费马分解。

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
48
49
50
import gmpy2
from Crypto.Util.number import getPrime, inverse, long_to_bytes
import random

from gmpy2 import gcd
from pywin.Demos.cmdserver import flags
from scipy.signal import qspline1d
from sympy import factor_list


def factor(n):
    a = gmpy2.iroot(n, 2)[0] #a可以看作p+q
    factor_list = []
    while True:
        a+=1
        b2 = a * a - n  #

        # 如果 b^2 是一个完全平方数
        if gmpy2.is_square(b2):
            b2 = gmpy2.mpz(b2)  # 转换为大整数
            b, xflag = gmpy2.iroot(b2, 2) #返回元组
            assert xflag# 如果能平方返回True
            factor_list.append([a + b, a - b])
            if len(factor_list) == 2:
                break

    return factor_list
e = 0x10001
c1 = 6201882078995455673376327652982610102807874783073703018551044780440620679217833227711395689114659144506630609087600915116940111002026241056808189658969089532597757995423694966667948250438579639890580690392400661711864264184444018345499567505424672090632235109624193289954785503512742400960515331371813467034511130432319427185134018830006918682733848618201088649690422818940385123599468595766345668931882249779415788129316594083269412221804774856038796248038700275509397599351533280014908894068141056694660319816046357462684688942519849441237878018480036145051967731081582598773076490918572392784684372694103015244826
n = 6348779979606280884589422188738902470575876294643492831465947360363568026280963989291591157710389629216109615274754718329987990551836115660879103234129921943824061416396264358110216047994331119920503431491509529604742468032906950984256964560405062345280120526771439940278606226153077959057882262745273394986607004406770035459301695806378598890589432538916219821477777021460189140081521779103226953544426441823244765828342973086422949017937701261348963541035128661464068769033772390320426795044617751909787914185985911277628404632533530390761257251552073493697518547350246993679844132297414094727147161169548160586911
factor_list=factor(n)
X1,Y1=factor_list[0]
X2,Y2=factor_list[1]
p=gcd(X1,X2)
p1=gcd(Y1,Y2)
q=X1//p
q1=Y1//p1
Phi=(p-1)*(q-1)*(p1-1)* (q1-1)
print("p=",p)
print("q=",q)
print("q1=",q1)
print("p1",p1)
print("Phi=",Phi)

d = inverse(e, Phi)
flag=pow(c1,d,n)
print("flag=",long_to_bytes(flag),"}")

'''
flag= b'flag{Euler_funct1ons' }'''

维纳攻击

使用条件

私钥d<1/3N^1/4^,选择较大的公钥e，用*e* ′代替*e*，其中*e* ′ = *e* + *k* ⋅ *λ* ( *N* )，*k*为某个较大的数。当*e* ′ 足够大时，即*e* ′ > N 3/2 ，则无论d有多小，都无法实施维纳攻击。假设p与q二进制长度相等即p<q<2p，可以得到p+q<3p<3(n)^0.5^

欧拉函数φ(N)=N-p-q+1 满足N-3(N)^0.5^<φ(N)<N

  • 基于定理

维纳攻击

维纳的方法

ed=1+k*φ(N)

|$e\over φ(N) $-$k\over d$|=$1 \over φ(n)$

φ(N)约等于N,K/gd约等于e/—>|$e\over N$-$k\over d$|=|$k(p+q-1)-1\over Nd$|

要使上述式子<1/(2d^2^)

p+q<3(N)^0.5^,0<K<d可以推断，|$e\over N$-$k\over d$|<3/N)^0.5^

所以d<3/(n)^0.25^

edg=k(p−1)(q−1)+g,k>g

同时除以k，k/g<1可以忽略

⌊ked**g⌋=(p−1)(q−1)

(pq−(p−1)(q−1)+1)/2=(p+q)/2

($(p+q)\over 2$)^2^-pq=($p-q\over 2$)^2^ #可以用这个判断连分数收敛是否为所需的k/(dg)

例题sagemath上的连分数扩展函数实现更便捷

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
def possible(e,alist,N):
    for x in alist:
        if x==0:
            continue
        phi=(e*x.denominator()-1)//x.numerator()
        if (N-phi+1)%2==0 and sqrt(pow((N-phi+1)//2,2)-N).is_integer():
            (p,q)=var('p q')
            x=solve([(p-1)*(q-1)==phi,p*q==N],p,q)
            return x 
        else:
            continue
def wienner_attack(e,N):
    c=continued_fraction(e/N)#获取连分数集合
    alist=c.convergents()#利用连分数得到连分数收敛
    return possible(e,alist,N)
'''
x.denominator():

这个函数返回分数 x 的分母。
x.numerator():

这个函数返回分数 x 的分子。
e * x.denominator():

这个部分将 e 乘以 x 的分母。
e * x.denominator() - 1:
'''

这个代码返回的是p和q

rrrrrrsa–一道题

这是一个关于rsa-wiener攻击拓展的推导

1
2
3
4
5
6
7
8
9
10
P1 = getPrime(1038)
P2 = sympy.nextprime(P1)
assert(P2 - P1 < 1000)

Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)

N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2

刚好可以应用在这里。

很明显是满足条件的。所以Q1/Q2是N1/N2的收敛连分数扩展

N1/N2=(P1/P1)^2^*(Q1/Q2)

Q1/Q1>N1/N2,N1<N2,Q1<Q2

n1/n2<Q1/Q2<1,然后我们用

因为Q1和Q2都是素数，我们可以直接得到Q1和Q2

并用N1%Q1来判断是否符合条件

解题代码

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
from Crypto.Util.number import long_to_bytes, inverse

import gmpy2
def possible(alist,N1):
    for x in alist:
        if x==0:
            continue
        Q1=x.numerator()
        if N1%Q1==0 and Q1!=1:
            Q2=x.denominator()
            return Q1,Q2
        else:
            continue
def wienner_attack(N1,N2):
    c=continued_fraction(N1/N2)#获取连分数集合
    alist=c.convergents()#利用连分数得到连分数收敛
    return possible(alist,N1)
N1=
N2=
c1=
c2=
E1=
E2=
t=wienner_attack(N1,N2)
Q1=t[0]
Q2=t[1]
print(Q1)
print(Q2)
P2=gmpy2.iroot(N2//Q2,2)[0]
P1=gmpy2.iroot(N1//Q1,2)[0]
phi1=(P1-1)*P1*(Q1-1)
phi2=(P2-1)*P2*(Q2-1)
d1=gmpy2.invert(E1,phi1)
d2=gmpy2.invert(E2,phi2)
m1=gmpy2.powmod(c1,d1,N1)
m2=gmpy2.powmod(c2,d2,N2)
f1=long_to_bytes(m1)
f2=long_to_bytes(m2)
print(f1,f2)
'''
11628371843051760370952910026406764366191062991235308941262037248377376991693250742343307155422036713746576338866595433599862614339347536916226536644210947
11628371843051760370952910026406764366191062991235308941262037248377376991693250742343307155422036713746576338866595433599862614339347536916226536644211929
b'GWHT{3aadab41754799' b'f978669d53e64a3aca}
'''

扩展维纳

参考：论文:https://dunkirkturbo.github.io/2020/05/04/WriteUp-De1CTF2020-Crypto/howgrave-graham1999.pdf

ctf-wiki-扩展维纳

维纳的方法

这里我们忽略前面提到的q<p<2q的条件。利用其他进行维纳攻击

这里有个前提，e约等于n,S约等于(n)^0.5^(大概就是2的指数差不多)

λ(N)=lcm(p-1,q-1)….g=gcd(p-1,q-1). s=1-p-q

$ed-k*λ(N)=1$

$edg-kN=g+ks$

$e\over N$-$k\over dg$=($k\over dg$)($s\over N$)+$1\over dN$

这里原论文的证明近似的量有点多，不够严谨，不能算是严格的维纳证明，最开始的那个更细节

GUO的方法

考虑存在两个e。

$e_1d_1g-k_1(p-1)(p-1)=g$

$e_2d_2g-k_2(p-1)(q-1)=g$

化简可以得到

$k_2d_1e_1−k_1d_2e_2=k_2−k_1$

同时除以$k_2d_1e_2$

$e_1\over e_2$-$k_1d_2\over k_2d_1$=$k_2-k_1\over k_2d_1e_2$

设$d_i<N^α$

$k_2-k_1\over k_2d_1e_2$≈N^−(1+α)^

为了满足上述定理

2(k2−k1)d1k2<e2

但是通过$k_1d_2\over k_2 d_1$找到分解N不是很现实，这个扩展结合了上述两种方法利用格来求

扩展维纳攻击

两个关系：

$d_ige_i−k_iN=g+k_is$ —M

k_id_je_j−k_jd_ie_i=k_i−k_j —Gi,j

我们假设$d_i$ 和$k_i $都小于N^αn^，且g很小，s≈N^1/2^。可以注意到$W_i$ 和Gi的右侧非常小，实际上分别最多为N^1/2+α^ 和N^α^。

接下来我们可以利用四个等式构造格

$k_1 k_2=k_1 k_2$

$d_1ge_1−k_1N=g+k_1s$

$k_1d_2e_2−k_2d_1e_1=k_1−k_2$

$d_1d_2g^2e_1e_2−d_1gk_2e_1N−d_2gk_1e_2N+k_1k_2N_2=(g+k_1s)(g+k_2s)$

可以构造如下格

屏幕截图-2025-01-05-155922

视作A*L=B

根据假设

屏幕截图-2025-01-05-155934

img

明显|L|≈2N,但是明显N^2α^,N^1/2+2α^,N^α2^,N^1+2α^.明显这里不符合定理要求需要构造一下，

$M_1=N$^1/2^,$M_2=N$^1+α^，得到

屏幕截图-2025-01-05-161454

根据上述条件

α≤5/14

把B2当作求出的最短向量。A=B*L^-1^。这是我们就能得到A，A[1]/A[0]=$d_1g\over k_1$

φ(N)=$edg\over k$-$g\over k$=$edg\over k$

羊城杯 simple.py

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
48
49
50
51
52
53
54
55
56
from Crypto.Util.number import *
from Crypto.Cipher import DES
import gmpy2
from secret import flag
import random

key = "abcdefgh"

def des_encrypt(m):
    des = DES.new(key, DES.MODE_ECB)
    res = des.encrypt(m)
    return res

def gen_key():
    p = getPrime(2048)
    q = getPrime(2048)
    n = p * q
    bit = n.bit_length()
    phi_n = (p - 1) * (q - 1)
    num = random.randint(1, 100)
    while True:
        u = getPrime(bit / 4 - num)
        if gmpy2.gcd(u, phi_n) != 1:
            continue
        t = gmpy2.invert(u, phi_n)
        e = bytes_to_long(des_encrypt(long_to_bytes(t)))
        if gmpy2.gcd(e, phi_n) == 1:
            break
    return (n, e)

P = getPrime(1024)
Q = getPrime(1024)
N = P * Q
E = 65537
lcm = gmpy2.lcm(P-1, Q-1)
e1 = gmpy2.invert(getPrime(730), lcm)
e2 = gmpy2.invert(getPrime(730), lcm)
m = bytes_to_long(flag)
c = pow(m, E, N)
print "N = " + str(N)
print "e2 = " + str(e2)
print "c = " + str(c)
_n, _e = gen_key()
_c = pow(e1, _e, _n)
print "_n = " + str(_n)
print "_e = " + str(_e)
print "_c = " + str(_c)

# N = 14922959775784066499316528935316325825140011208871830627653191549546959775167708525042423039865322548420928571524120743831693550123563493981797950912895893476200447083386549353336086899064921878582074346791320104106139965010480614879592357793053342577850761108944086318475849882440272688246818022209356852924215237481460229377544297224983887026669222885987323082324044645883070916243439521809702674295469253723616677245762242494478587807402688474176102093482019417118703747411862420536240611089529331148684440513934609412884941091651594861530606086982174862461739604705354416587503836130151492937714365614194583664241
# e2 = 27188825731727584656624712988703151030126350536157477591935558508817722580343689565924329442151239649607993377452763119541243174650065563589438911911135278704499670302489754540301886312489410648471922645773506837251600244109619850141762795901696503387880058658061490595034281884089265487336373011424883404499124002441860870291233875045675212355287622948427109362925199018383535259913549859747158348931847041907910313465531703810313472674435425886505383646969400166213185676876969805238803587967334447878968225219769481841748776108219650785975942208190380614555719233460250841332020054797811415069533137170950762289
# c = 6472367338832635906896423990323542537663849304314171581554107495210830026660211696089062916158894195561723047864604633460433867838687338370676287160274165915800235253640690510046066541445140501917731026596427080558567366267665887665459901724487706983166070740324307268574128474775026837827907818762764766069631267853742422247229582756256253175941899099898884656334598790711379305490419932664114615010382094572854799421891622789614614720442708271653376485660139560819668239118588069312179293488684403404385715780406937817124588773689921642802703005341324008483201528345805611493251791950304129082313093168732415486813
# _n = 440489238264900860776949063845200558734341182253911040104689726634414488997095518284964514078079911856352824174173937251558842251349762631716798307360995414545464514355957499460396352456341058329671470384493547042182238690727766731554287411757022792467324815342497916894285866240516524768645049867582541899123632009100512965460004548382054578461249990158442675234477122521189649316341623637146867589119951831385717513964941787562068891523060843170463600255518728070958509224053460041184869943038887434435024428311063533345514827827485121055022245800823723487812635502090530820946638405345755666124356919178290008475459419571761406117827422883820901663916276191422633940699113760516149002609672230610575442643822241126824287790055264162725209120192661985259423924307785452001927701323647247782658775780117642900694831475681037634691806232211286493187121464506122012889644137364079403183353774265910554863733455161820449073656744610495110838881353269890437984975607744603113572453211439334880155671730821755361054781243639407912133971530394031933785051770725331242932929244719594830548310768937037042243794551163891451545574837838357398072638709907958216067999891842395376953596940377457308329336524488962532620850237570279134567668379
# _e = 861605654852236668414010386016782729745549477722901970933220380452652052018502113737968204529790495739233258572209422774257139256367928649554562561889013164344608269555777150446651170697255381344437283003508476336814132594917061838422072660017477530465048729471603537912401826065081663165440462979219418291010867656746870617893935758241591032350010782861988742885918015532494020406350897048575155800941991107973433915573030255070411073793489218782862225921465295055907689734413881263179029741870520797816282420230090879687287575328294171448819803530205292587159921154471289747571107461754730577787617451127061265552788125691266357724955508391085485034126227212788895416902189479587194999818764639403752596165043883295506465916277734482380252399557395621566461322664559344483889187037851178431011220134914560438657522787409632677020269086895142488669203469256629173438313487046130238010206678820035631793666627274457756812810094004185303422637897314225624079032617334487815628021058997628511963565055629435278956251869329025544623291223984190562109149316159243565323565271491356378189561005084676592786453581431393651385181326525455441155960432946682976515756161038293313433862078763004704003356983371787414787104076401121444383911561
# _c = 305937839546594439230463861584604201077374759167468410827830943528403007941779658881672477705113617614828611332427199124217887937391378281943856159571057598203709366891547401974326016980711130197275312149966105151573748299654404630150641461765232935912266448303266990247145252052886920248198006212876273661195636104435277145396636985516064154534488750879453474211852461463041960835745695368577903786702607508492658563272121038693371752289017330781719235752018697635304458321008407930986565779826278048082764754367267460637798512780153281325733348999426407049795270044819657399403071013496169060640127279409914638535996355848933378734045908205536540619564723586905257569498716707820544351092379516465943537383422680357333849248129118148543389733395686399565999586899123087310025442994131218237679518267106194962305629529210402269726736072967966518381350920965727690274018080619332676536005722214955949897632990356174168234408837737546230730400434240785496100281815168806724358191550743656843853383646410487436540166360406982096949178466861150173527305369007546917550634679211293496458282787881244581230558011582720632502886494712233308474151958909251857281750741736910202763888790654287328846201724930302778996046434656839999091303411


我们需要先求出e1，再通过e1和e2找到lcm，再通过lcm找到d和m

1
2
3
4
5
6
7
8
def des_decrypt(m):
    des = DES.new(key, DES.MODE_ECB)
    res = des.decrypt(m)
    return res
ciphertext = long_to_bytes(_e)
decrypted_data = des_decrypt(ciphertext)
_t=bytes_to_long(decrypted_data)
print(_t)利用这个先求出_t

t = gmpy2.invert(u, phi_n)，这里t满足维纳攻击的条件可以利用t求出phi_n再解出_d和e1。_

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from gmpy2 import invert
def possible(e,alist,N):
    for x in alist:
        if x==0:
            continue
        phi=(e*x.denominator()-1)//x.numerator()
        if (N-phi+1)%2==0 and sqrt(pow((N-phi+1)//2,2)-N).is_integer():
            (p,q)=var('p q')
            Phi=phi
            return Phi
        else:
            continue
def wienner_attack(e,N):
    c=continued_fraction(e/N)#获取连分数集合
    alist=c.convergents()#利用连分数得到连分数收敛
    return possible(e,alist,N)
_t=
_c = 
_n = 
_e = 
phi=wienner_attack(_t,_n)
d1=invert(_e,phi)
e1=pow(_c,d1,_n)
print(e1)

利用e1构造矩阵得到phi在求出m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from gmpy2 import invert
from Crypto.Util.number import bytes_to_long, long_to_bytes
c = 
e2 = 
e1 = 
N  = 
a  = 5./14
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=int(pow(c,d,N))
print(long_to_bytes(m))

crypto > RSA
#crypto #RSA
RSA维纳攻击及其扩展
http://example.com/2024/12/29/RSA-wiener/
Beitragsautor
fox
Veröffentlicht am
December 29, 2024
Urheberrechtshinweis