常用工具

分解大素數

factordb http://www.factordb.com
yafu（p,qp,q相差過大或過小yafu可分解成功）
sage divisors(n)（小素數）

Openssl

解析加密密鑰：

openssl rsa -pubin -text -modulus -in pub.key

生成解密密鑰：

python rsatool.py -f PEM -o key.key -p 1 -q 1 -e 1openssl rsautl -decrypt -inkey key.pem -in flag.enc -out flagopenssl rsautl -decrypt -oaep -inkey key.pem -in flag.enc -out flag （OAEP方式）

腳本生成解密密鑰：

# coding=utf-8 import math import sys from Crypto.PublicKey import RSAkeypair = RSA.generate(1024) keypair.p = keypair.q = keypair.e = keypair.n = keypair.p * keypair.q Qn = long((keypair.p - 1) * (keypair.q - 1))i = 1 while (True):x = (Qn * i) + 1if (x % keypair.e == 0):keypair.d = x / keypair.ebreaki += 1 private = open('private.pem', 'w') private.write(keypair.exportKey()) private.close()

RSA套路

給p,q,e,c

import gmpy2 as gp import binascii p = q = e = c = n = p*q phi = (p-1)*(q-1) d = gp.invert(e,phi) m = pow(c,d,n) print(m) print(bytes.fromhex(hex(m)[2:]))

給n,e,dp,c

import gmpy2 as gpe = n = dp = c = for x in range(1, e):if(e*dp%x==1):p=(e*dp-1)//x+1if(n%p!=0):continueq=n//pphin=(p-1)*(q-1)d=gp.invert(e, phin)m=gp.powmod(c, d, n)if(len(hex(m)[2:])%2==1):continueprint('--------------')print(m)print(hex(m)[2:])print(bytes.fromhex(hex(m)[2:]))

變種給 p,e,dp,c,b其中 n=p**b*q

from Crypto.Util.number import * import gmpy2 p = dp = c = b = e = mp1 = pow(c, dp, p) mp = pow(c, dp - 1, p) for i in range(1, b - 2):x = pow(c - pow(mp1, e), 1, p**(i + 1))y = pow(x * mp * (gmpy2.invert(e, p)), 1, p**(i + 1))mp1 = mp1 + y print(long_to_bytes(mp1))

變種 給n,e,dp0,c,k 其中dp0為dp高位即dp0 = dp>>k

#Sage dp0 = e = n = F.<x> = PolynomialRing(Zmod(n)) d = inverse_mod(e, n) for k in range(1, e):f = (secret << 200) + x + (k - 1) * dx0 = f.small_roots(X=2 ** (200 + 1), beta=0.44, epsilon=1/32)if len(x0) != 0:dp = x0[0] + (secret << 200)for i in range(2, e):p = (e * Integer(dp) - 1 + i) // iif n % p == 0:breakif p < 0:continueelse:print('k = ',k)print('p = ',p)print('dp = ',dp)break

給p,q,dp,dq,c

import gmpy2 as gpp = q = dp = dq = c = n = p*q phin = (p-1)*(q-1) dd = gp.gcd(p-1, q-1) d=(dp-dq)//dd * gp.invert((q-1)//dd, (p-1)//dd) * (q-1) +dq print(d)m = gp.powmod(c, d, n) print('-------------------') print(m) print(hex(m)[2:]) print(bytes.fromhex(hex(m)[2:]))

低解密指數攻擊/低私鑰指數攻擊（e長度較大，d小，Wiener Attack）

RSAWienerHacker工具：https://github.com/pablocelayes/rsa-wiener-attack

#腳本1（帶工具） #python2 import RSAwienerHacker n = e = d = RSAwienerHacker.hack_RSA(e,n) if d:print(d) import hashlib flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}" print flag #腳本2 #sage def rational_to_contfrac(x,y):# Converts a rational x/y fraction into a list of partial quotients [a0, ..., an]a = x // ypquotients = [a]while a * y != x:x, y = y, x - a * ya = x // ypquotients.append(a)return pquotientsdef convergents_from_contfrac(frac):# computes the list of convergents using the list of partial quotientsconvs = [];for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0 : i]))return convsdef contfrac_to_rational (frac):# Converts a finite continued fraction [a0, ..., an] to an x/y rational.if len(frac) == 0: return (0,1)num = frac[-1]denom = 1for _ in range(-2, -len(frac) - 1, -1): num, denom = frac[_] * num + denom, numreturn (num, denom)n = e = c = def egcd(a, b):if a == 0: return (b, 0, 1)g, x, y = egcd(b % a, a)return (g, y - (b // a) * x, x)def mod_inv(a, m):g, x, _ = egcd(a, m)return (x + m) % mdef isqrt(n):x = ny = (x + 1) // 2while y < x:x = yy = (x + n // x) // 2return xdef crack_rsa(e, n):frac = rational_to_contfrac(e, n)convergents = convergents_from_contfrac(frac)for (k, d) in convergents:if k != 0 and (e * d - 1) % k == 0:phi = (e * d - 1) // ks = n - phi + 1# check if x*x - s*x + n = 0 has integer rootsD = s * s - 4 * nif D >= 0:sq = isqrt(D)if sq * sq == D and (s + sq) % 2 == 0: return dd = crack_rsa(e, n) m = hex(pow(c, d, n))[2:] print(bytes.fromhex(m)) #腳本3 from Crypto.Util.number import long_to_bytes e = n = c = #將分數x/y展開為連分數的形式 def transform(x,y):arr=[]while y:arr+=[x//y]x,y=y,x%yreturn arr#求解漸進分數 def sub_fraction(k):x=0y=1for i in k[::-1]:x,y=y,x+i*yreturn (y,x) data=transform(e,n)for x in range(1,len(data)+1):data1=data[:x]d = sub_fraction(data1)[1]m = pow(c,d,n)flag = long_to_bytes(m)if b'flag{' in flag:print(flag)break

變種 N1/N2 < q1/q2 <1

參考：2020年羊城杯 - RRRRRRRSA
Paper: https://eprint.iacr.org/2015/399.pdf

連分數逼近：

def transform(x,y): #使用輾轉相除將分數x/y轉為連分數的形式res=[]while y:res.append(x//y)x,y=y,x%yreturn resdef continued_fraction(sub_res):numerator,denominator=1,0for i in sub_res[::-1]: #從sublist的后面往前循環denominator,numerator=numerator,i*numerator+denominatorreturn 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 resdef wienerAttack(n1,n2):for (q2,q1) in sub_fraction(n1,n2): #用一個for循環來注意試探n1/n2的連續函數的漸進分數，直到找到一個滿足條件的漸進分數if q1==0: #可能會出現連分數的第一個為0的情況，排除continueif n1%q1==0 and q1!=1: #成立條件return (q1,q2)print("該方法不適用")N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347 N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121 print(wienerAttack(N1,N2))

低加密指數廣播攻擊（Hastad攻擊）

#sage def chinese_remainder(modulus, remainders):Sum = 0prod = reduce(lambda a, b: a*b, modulus)for m_i, r_i in zip(modulus, remainders):p = prod // m_iSum += r_i * (inverse_mod(p,m_i)*p)return Sum % prod chinese_remainder([3,5,7],[2,3,2]) #23 #sage crt([2,3,2],[3,5,7])

共模攻擊（n,m相同，c,e不同）

import gmpy2 as gp def egcd(a, b):if a == 0:return (b, 0, 1)else:g, y, x = egcd(b % a, a)return (g, x - (b // a) * y, y)n = c1 = c2 = e1 = e2 = s = egcd(e1, e2) s1 = s[1] s2 = s[2] if s1<0:s1 = - s1c1 = gp.invert(c1, n) elif s2<0:s2 = - s2c2 = gp.invert(c2, n)m = pow(c1,s1,n)*pow(c2,s2,n) % n print(hex(m)[2:]) print(bytes.fromhex(hex(m)[2:]))

e,m相同，多個n中存在兩個n有GCD（模不互素）

import gmpy2 as gpn=[] for i in n:for j in n:if (i<>j):pub_p=gp.gcdext(i,j)if (pub_p[0]<>1)&(i>j):print(i)print(j)print(pub_p[0])a=i,p=pub_p[0] q=a//p p = q = e = c = n = p*q phi = (p-1) * (q-1) d = gp.invert(e, phi) m = pow(c, d, n) print(hex(m)[2:]) print(bytes.fromhex(hex(m)[2:]))

Rabin加密

適用情況：e=2e=2 。

一般先通過其他方法分解得到 p,qp,q，然后解密。

函數返回四個數，這其中只有一個是我們想要的明文，需要通過其他方式驗證。

import gmpy2def rabin_decrypt(c, p, q, e=2):n = p * qmp = pow(c, (p + 1) // 4, p)mq = pow(c, (q + 1) // 4, q)yp = gmpy2.invert(p, q)yq = gmpy2.invert(q, p)r = (yp * p * mq + yq * q * mp) % nrr = n - rs = (yp * p * mq - yq * q * mp) % nss = n - sreturn (r, rr, s, ss)c = p = q = m = rabin_decrypt(c,p,q) for i in range(4):try:print(bytes.fromhex(hex(m[i])[2:]))except:pass

Boneh和Durfee攻擊

參考 https://github.com/mimoo/RSA-and-LLL-attacks

Coppersmith攻擊（已知p的高位攻擊）

知道 p 的高位為 p 的位數的約1/2時即可。

#Sage from sage.all import * n = p4 = #p去0的剩余位 e = pbits = 1024 kbits = pbits - p4.nbits() print(p4.nbits()) p4 = p4 << kbits PR.<x> = PolynomialRing(Zmod(n)) f = x + p4 roots = f.small_roots(X=2^kbits, beta=0.4) #經過以上一些函數處理后，n和p已經被轉化為10進制 if roots: p = p4+int(roots[0]) print("n: "+str(n))print("p: "+str(p))print("q: "+str(n//p))

Coppersmith攻擊（已知明文高位攻擊，部分m）

這里我們假設我們首先加密了消息 mm，如下
C≡m**e * modN
并且我們假設我們知道消息 m 的很大的一部分 m0，即 m=m0+x，但是我們不知道 x。那么我們就有可能通過該方法進行恢復消息。這里我們不知道的 x 其實就是多項式的根，需要滿足 Coppersmith 的約束。
可以參考 https://github.com/mimoo/RSA-and-LLL-attacks 。
ee 足夠小，且部分明文泄露時，可以采用Coppersmith單變量模等式的攻擊，如下

#Sage n = e = c = mbar = kbits = beta = 1 nbits = n.nbits() print("upper {} bits of {} bits is given".format(nbits - kbits, nbits)) PR.<x> = PolynomialRing(Zmod(n)) f = (mbar + x)^e - c x0 = f.small_roots(X=2^kbits, beta=1)[0] # find root < 2^kbits with factor = n print("m:", mbar + x0)

Coppersmith攻擊（已知d的低位攻擊，部分d）

#Sage def partial_p(p0, kbits, n):PR.<x> = PolynomialRing(Zmod(n))nbits = n.nbits()f = 2^kbits*x + p0f = f.monic()roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.4) # find root < 2^(nbits//2-kbits) with factor >= n^0.4if roots:x0 = roots[0]p = gcd(2^kbits*x0 + p0, n)return ZZ(p) def find_p(d0, kbits, e, n):X = var('X')for k in range(1, e+1):results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)for x in results:p0 = ZZ(x[0])p = partial_p(p0, kbits, n)if p and p != 1:return p if __name__ == '__main__':n = e = c = d0 = beta = 0.5nbits = n.nbits()kbits = d0.nbits()print("lower %d bits (of %d bits) is given" % (kbits, nbits))p = int(find_p(d0, kbits, e, n))print("found p: %d" % p)q = n//int(p)print("d:", inverse_mod(e, (p-1)*(q-1)))

變種 n = pqr

#Sage def find_p(d0, kbits, e, n, p):X = var('X')for k in range(1, e + 1):k_dot = k * (p - 1)results = solve_mod([e * d0 * X - k_dot * X * (n - X + 1) + k_dot * n == X], 2^kbits)for x in results:q = ZZ(x[0])if n % q == 0:return qreturn Nonen = ... # q * r p = c = d0 = e = kbits = d0.nbits() q = find_p(d0, kbits, e, n, p) phi = (p - 1) * (q - 1) * (n // q - 1) d = inverse_mod(e, phi) print(bytes.fromhex(hex(pow(c, d, p * n))[2:]))

Coppersmith攻擊（已知N一個因子的高位，部分p）

當我們知道一個公鑰中模數 N 的一個因子的較高位時，我們就有一定幾率來分解 N。

參考 https://github.com/mimoo/RSA-and-LLL-attacks 。

關注下面的代碼：

beta = 0.5 dd = f.degree() epsilon = beta / 7 mm = ceil(beta**2 / (dd * epsilon)) tt = floor(dd * mm * ((1/beta) - 1)) XX = ceil(N**((beta**2/dd) - epsilon)) + 1000000000000000000000000000000000 roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)

#Sage n = e = c = pbar = kbits = print("upper %d bits (of %d bits) is given" % (pbar.nbits()-kbits, pbar.nbits())) PR.<x> = PolynomialRing(Zmod(n)) f = x + pbar x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.4 p = x0 + pbar print("p:", p) q = n // int(p) d = inverse_mod(e, (p-1)*(q-1)) print("m:", pow(c, d, n))

Coppersmith’s Short-pad Attack & Related Message Attack（Franklin-Reiter攻擊）

#腳本1 #Sage import binascii def attack(c1, c2, b, e, n):PR.<x>=PolynomialRing(Zmod(n))g1 = x^e - c1g2 = (x+b)^e - c2def gcd(g1, g2):while g2:g1, g2 = g2, g1 % g2return g1.monic()return -gcd(g1, g2)[0] c1 = c2 = n = e= a = 1 id1 = 1 id2 = 2 b = id2 - id1 m1 = attack(c1,c2, b,e,n) print(binascii.unhexlify("%x" % int(m1 - id1))) #腳本2 #Sage def short_pad_attack(c1, c2, e, n):PRxy.<x,y> = PolynomialRing(Zmod(n))PRx.<xn> = PolynomialRing(Zmod(n))PRZZ.<xz,yz> = PolynomialRing(Zmod(n))g1 = x^e - c1g2 = (x+y)^e - c2q1 = g1.change_ring(PRZZ)q2 = g2.change_ring(PRZZ)h = q2.resultant(q1)h = h.univariate_polynomial()h = h.change_ring(PRx).subs(y=xn)h = h.monic()kbits = n.nbits()//(2*e*e)diff = h.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.4return diff def related_message_attack(c1, c2, diff, e, n):PRx.<x> = PolynomialRing(Zmod(n))g1 = x^e - c1g2 = (x+diff)^e - c2def gcd(g1, g2):while g2:g1, g2 = g2, g1 % g2return g1.monic()return -gcd(g1, g2)[0] if __name__ == '__main__':n = e = c1 =c2 = diff = short_pad_attack(c1, c2, e, n)print("difference of two messages is %d" % diff)m1 = related_message_attack(c1, c2, diff, e, n)print("m1:", m1)print("m2:", m1 + diff)

RSA Hastad Attack with non-linear padding and different public keys（帶非線性padding和不同公鑰的廣播攻擊）

參考：2020年羊城杯 - Invitation

#Sage #e=3, padding: m2+(3^431)k def linearPaddingHastads(cArray,nArray,aArray,bArray,eArray,eps):if(len(cArray) == len(nArray) == len(aArray) == len(bArray) == len(eArray)):for i in range(4):cArray[i] = Integer(cArray[i])nArray[i] = Integer(nArray[i])aArray[i] = Integer(aArray[i])bArray[i] = Integer(bArray[i])eArray[i] = Integer(eArray[i])TArray = [-1]*4for i in range(4):arrayToCRT = [0]*4arrayToCRT[i] = 1TArray[i] = crt(arrayToCRT,nArray)P.<x> = PolynomialRing(Zmod(prod(nArray)))gArray = [-1]*4for i in range(4):gArray[i] = TArray[i]*(pow(aArray[i]*x**2 + bArray[i],eArray[i]) - cArray[i])g = sum(gArray)g = g.monic()roots = g.small_roots(epsilon=eps)if(len(roots)== 0):print("No Solutions found!")return -1return rootselse:print("Input error!")def nonLinearPadding():eArr = [3 for i in range(4)]nArr = [146694460234280339612721415368435987068740712812770728817136582256341063038147863645902264969297892447333024201649306207442798919845916187823646745721109151386096190207317810424580842120750075213595282979568495342617919336417068886973047979116994072272482630372638964064972815256237040541007947708358680368391,65031485534704406281490718325237831433086480239135617407356760819741796565231283220528137697949585150709734732370203390254643835828984376427852793969716489016520923272675090536677771074867975287284694860155903327351119710765174437247599498342292671117884858621418276613385329637307269711179183430246951756029,126172075578367446151297289668746433680600889845504078949758568698284471307000358407453139846282095477016675769468273204536898117467559575203458221600341760844973676129445394999861380625435418853474246813202182316736885441120197888145039130477114127079444939102267586634051045795627433724810346460217871661901,75691424835079457343374072990750986689075078863640186724151061449621926239051140991748483370587430224317778303489124525034113533087612981452189061743589227565099659070008017454957304620495920813121234552401715857719372861565651204968408267740732475458128601061676264465241188491988485848198323410127587280471]cArr = [129274519334082165644106292383763271862424981496822335330342328217347928093592453953990448827969549377883054831490973006383371688359344675312001881631556371220779971357039899721241880304156884612458373310254854821837978876725801047977081900824202659636258168216028784656056334358157381820784576207338479493823,8140023566779187828652447593867705813386781164538611122714708931585587727699213769519135028841126072130625547328311301696554048174772606261707345115571968105138543476580875347239912760797035694220505996377127309341770427102697008350472060971360460756799310951343070384766137332401117333917901167639276168214,25434511525127530194830986592289179576070740435049947678930286998924519588985583799757299734846614343604661534391991096353170465467791358514448923161460366596251448937540153262731348684727026598527904328268639060306102090278287818149679940661579357649191023269947102746200467430583428889484549034314463114080,9435583236354598287661880148272717764447540972316605192855157484524753847806158586224733743434644389385148450722945845355791145016665856388503878165725148745517696840251674049929524448078129458846254866804153080766917319923905682824180976106679633180818527967145571143203594244851742143986040226240019541346]aArr = [1 for i in range(4)]bArr = [i * 3 ** 431 for i in [3,8,10,11]]msg = linearPaddingHastads(cArr,nArr,aArr,bArr,eArr,eps=1/20)for i in msg:print(bytes.fromhex(hex(i)[2:]))if __name__ == '__main__':nonLinearPadding()

Least Significant Bit Oracle Attack （LSB Oracle Attack / Parity Oracle）

import decimal def oracle():return lsb == 'odd'def partial(c, e, n):k = n.bit_length()decimal.getcontext().prec = k # for 'precise enough' floatslo = decimal.Decimal(0)hi = decimal.Decimal(n)for i in range(k):if not oracle(c):hi = (lo + hi) / 2else:lo = (lo + hi) / 2c = (c * pow(2, e, n)) % n# print i, int(hi - lo)return int(hi)

Common Private Exponent（共私鑰指數攻擊，d相同）

參考：SCTF 2020 - RSA

###Sage### from gmpy2 import * e0= n0= c0= e1= n1= c1= e2= n2= c2=M=iroot(int(n2),int(2))[0] a=[0]*4 a[0]=[M,e0,e1,e2] a[1]=[0,-n0,0,0] a[2]=[0,0,-n1,0] a[3]=[0,0,0,-n2]Mat = matrix(ZZ,a) Mat_LLL=Mat.LLL() d = abs(Mat_LLL[0][0])/M print(bytes.fromhex(hex(pow(c1,int(d),int(n1)))[2:]))

多組低解密指數攻擊

適用情況：2-4組 ee，且 dd 較小
給定2組

#Sagen = e1 = e2 = c = from Crypto.Util.number import *for i in range(731, 682, -1):print(i)alpha2 = i / 2048M1 = round(n ^ 0.5)M2 = round(n ^ (1 + alpha2))A = Matrix(ZZ, [[n, -M1*n, 0, n^2],[0, M1*e1, -M2*e1, -e1*n],[0, 0, M2*e2, -e2*n],[0, 0, 0, e1*e2]])AL = A.LLL()C = Matrix(ZZ, AL[0])B = A.solve_left(C)[0]phi1 = floor(e1 * B[1] / B[0])phi2 = floor(e2 * B[2] / B[0])d1 = inverse(e1, phi1)d2 = inverse(e2, phi2)m1 = long_to_bytes(pow(c, d1, n))m2 = long_to_bytes(pow(c, d2, n))if b"De1" in m1 or b"De1" in m2:print(m1)print(m2)break

參考：De1CTF 2020 - easyRSA
給定3組
類似2組情況，其中

多項式RSA

#腳本1 #Sage #已知p,n,m^e p= P = PolynomialRing(Zmod(p), name = 'x') x = P.gen() e = n = c =#分解N q1, q2 = n.factor() q1, q2 = q1[0], q2[0]#求φ，注意求法， phi = (p**q1.degree() - 1) * (p**q2.degree() - 1) assert gcd(e, phi) == 1 d = inverse_mod(e, phi) m = pow(c,d,n)#取多項式系數 flag = bytes(m.coefficients()) print("Flag: ", flag.decode()) #腳本2 #Sage #已知p=2,n,e,c p = P = PolynomialRing(GF(p), name = 'x') x = P.gen() e = n = R.<a> = GF(2^2049) c = []q1, q2 = n.factor() q1, q2 = q1[0], q2[0]phi = (p**q1.degree() - 1) * (p**q2.degree() - 1) assert gcd(e, phi) == 1 d = inverse_mod(e, phi)ans = '' for cc in c:cc = P(R.fetch_int(cc))m = pow(cc,d,n)m = R(P(m)).integer_representation()print(m)ans += chr(m) print(ans) 參考：[0ctf - babyrsa](https://xz.aliyun.com/t/4545)[watevrCTF 2019 - Swedish RSA](https://blog.csdn.net/cccchhhh6819/article/details/103563019)[InCTF 2020 - PolyRSA](https://github.com/S3v3ru5/CTF-writeups/tree/master/Inctfi-2020)[Polynomial based RSA](http://www.diva-portal.se/smash/get/diva2:823505/FULLTEXT01.pdf)

其他特別情況

總結

以上是生活随笔為你收集整理的RSA总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。