[MRCTF 2020] - RSA

easy_RSA

题目：

import sympy from gmpy2 import gcd, invert from random import randint from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes import base64 from zlib import * flag = b"MRCTF{XXXX}" base = 65537 def gen_prime(N): A = 0 while 1: A = getPrime(N) if A % 8 == 5: break return A def gen_p(): p = getPrime(1024) q = getPrime(1024) assert (p < q) n = p * q print("P_n = ", n) F_n = (p - 1) * (q - 1) print("P_F_n = ", F_n) factor2 = 2021 * p + 2020 * q if factor2 < 0: factor2 = (-1) * factor2 return sympy.nextprime(factor2) def gen_q(): p = getPrime(1024) q = getPrime(1024) assert (p < q) n = p * q print("Q_n = ", n) e = getRandomNBitInteger(53) F_n = (p - 1) * (q - 1) while gcd(e, F_n) != 1: e = getRandomNBitInteger(53) d = invert(e, F_n) print("Q_E_D = ", e * d) factor2 = 2021 * p - 2020 * q if factor2 < 0: factor2 = (-1) * factor2 return sympy.nextprime(factor2) if __name__ == "__main__": _E = base _P = gen_p() _Q = gen_q() assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1) _M = bytes_to_long(flag) _C = pow(_M, _E, _P * _Q) print("Ciphertext = ", _C) ''' P_n = 14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024336556028267742021320891681762543660468484018686865891073110757394154024833552558863671537491089957038648328973790692356014778420333896705595252711514117478072828880198506187667924020260600124717243067420876363980538994101929437978668709128652587073901337310278665778299513763593234951137512120572797739181693 P_F_n = 14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024099427363967321110127562039879018616082926935567951378185280882426903064598376668106616694623540074057210432790309571018778281723710994930151635857933293394780142192586806292968028305922173313521186946635709194350912242693822450297748434301924950358561859804256788098033426537956252964976682327991427626735740 Q_n = 20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947 Q_E_D = 100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201 Ciphertext = 40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021 '''

gen_p()函数中给出了n和φ(n)，因此可以根据(图片参考https://mp.weixin.qq.com/s/TEnuxcUV1SHiW4VOWQK9eQ)计算出_P； gen_q()函数中给出了e*d和n，就可以分解出n得到p、q，参考RSA-已知ed分解n，进而得到_Q 接下来就是正常RSA操作

解题

# -*- coding: UTF-8 -*- import gmpy2 import sympy import random from Crypto.Util.number import * base = 65537 P_n = 14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024336556028267742021320891681762543660468484018686865891073110757394154024833552558863671537491089957038648328973790692356014778420333896705595252711514117478072828880198506187667924020260600124717243067420876363980538994101929437978668709128652587073901337310278665778299513763593234951137512120572797739181693 P_F_n = 14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024099427363967321110127562039879018616082926935567951378185280882426903064598376668106616694623540074057210432790309571018778281723710994930151635857933293394780142192586806292968028305922173313521186946635709194350912242693822450297748434301924950358561859804256788098033426537956252964976682327991427626735740 Q_n = 20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947 Q_E_D = 100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201 Ciphertext = 40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021 paddq = P_n-P_F_n+1 psubq = gmpy2.iroot((paddq**2-4*P_n),2)[0] q = (paddq+psubq)//2 p = P_n//q _P=sympy.nextprime(2021 * p + 2020 * q) #print _P def getpq(ed, n): k = ed - 1 while True: g = random.randint(2, n-1) t = k while True: if t % 2 != 0: break t /= 2 x = pow(g, t, n) if x > 1 and gmpy2.gcd(x-1, n) > 1: p = gmpy2.gcd(x-1, n) return (p, n/p) _p,_q=getpq(Q_E_D,Q_n) _Q = sympy.nextprime((2021 * _p - 2020 * _q)*(-1)) #print _Q phi = (_P-1)*(_Q-1) d = gmpy2.invert(base,phi) m = pow(Ciphertext,d,_P*_Q) flag = long_to_bytes(m) print flag

babyRSA

题目:

import sympy import random from gmpy2 import gcd, invert from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes from z3 import * flag = b"MRCTF{xxxx}" base = 65537 def GCD(A): B = 1 for i in range(1, len(A)): B = gcd(A[i-1], A[i]) return B def gen_p(): P = [0 for i in range(17)] P[0] = getPrime(128) for i in range(1, 17): P[i] = sympy.nextprime(P[i-1]) print("P_p :", P[9]) n = 1 for i in range(17): n *= P[i] p = getPrime(1024) factor = pow(p, base, n) print("P_factor :", factor) return sympy.nextprime(p) def gen_q(): sub_Q = getPrime(1024) Q_1 = getPrime(1024) Q_2 = getPrime(1024) Q = sub_Q ** Q_2 % Q_1 print("Q_1: ", Q_1) print("Q_2: ", Q_2) print("sub_Q: ", sub_Q) return sympy.nextprime(Q) if __name__ == "__main__": _E = base _P = gen_p() _Q = gen_q() assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1) _M = bytes_to_long(flag) _C = pow(_M, _E, _P * _Q) print("Ciphertext = ", _C) ''' P_p : 206027926847308612719677572554991143421 P_factor : 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839 Q_1: 103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521 Q_2: 151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743 sub_Q: 168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651 Ciphertext = 1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832 '''

同样是两个分别生成p和q的函数，分别计算出_P和_Q解RSA就行了 先来看函数gen_p()，先是生成了17个连续的素数，并且给出了第十个素数，我们可以往前判断每个奇数，找出P_p前面9个素数并得到p[0]，继而轻松找到了所有素数，n为17个小素数相乘，φ(n)是每个小素数-1再相乘得到，然后进行一次常规的RSA求解得到_P； 接着看函数gen_q，_Q基本是白给，需要注意的就是Q = sub_Q ** Q_2 % Q_1，大数乘方的结果再取模效率太低，应改为快速幂取模算法Q = pow(sub_Q,Q_2,Q_1)

解题

import sympy import random from gmpy2 import * from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes base = 65537 P_p = 206027926847308612719677572554991143421 P_factor = 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839 Q_1= 103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521 Q_2= 151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743 sub_Q= 168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651 Ciphertext = 1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832 k=0 while k<9: P_p-=2 if(isPrime(P_p)): k+=1 #P_p=206027926847308612719677572554991143421 p=[0 for i in range(17)] p[0]=P_p for i in range(1,17): p[i]=next_prime(p[i-1]) n=1 phi=1 for i in range(17): phi *=p[i]-1 n *= p[i] P = pow(P_factor,invert(base,phi),n) _P = next_prime(P) Q = pow(sub_Q,Q_2,Q_1) _Q = next_prime(Q) _phi = (_P-1)*(_Q-1) _d = invert(base,_phi) m = pow(Ciphertext,_d,_P*_Q) flag = long_to_bytes(m) print flag #MRCTF{sti11_@_b@by_qu3st10n}