这里写目录标题

1.[NCTF2019]babyRSA2.[BJDCTF2020]easyrsa3.[ACTF新生赛2020]crypto-rsa34.[RoarCTF2019]babyRSA5.[MRCTF2020]Easy_RSA6.[MRCTF2020]babyRSA7.[BJDCTF2020]Polybius

1.[NCTF2019]babyRSA

文件打开分析代码： 已知e,d,c,求m。看来必须求q,p了 进一步分析p,q是1024位的,因此两者相乘大概是2048位,通过运算可知ed-1为2064位,因此k一定小于16位,我们只需在0到2**16遍历即可条件为（ed-1）%k==0(因为ed-1=k*phi) 代码：

import sympy.crypto import gmpy2 import binascii e=0x10001 d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913 c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804 e_d_1=e*d-1 p=0 q=0 for k in range(pow(2,15),pow(2,16)): if e_d_1%k==0: p=sympy.prevprime(gmpy2.iroot(e_d_1//k,2)[0]) q=sympy.nextprime(p) if (p-1)*(q-1)*k==e_d_1: break n=p*q print(n) m=gmpy2.powmod(c,d,n) print(m) print(binascii.unhexlify(hex(m)[2:]))

2.[BJDCTF2020]easyrsa

记录哈这个题的函数，Fraction(a,b)相当于a/b,Derivative(f(x),x))为f(x)的导函数，arctan()反正切函数，arth()反双曲函数所以最终z就等于q2+p2 解题

代码：

import gmpy2 import binascii e=65537 c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035 z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482 n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441 qaddp = gmpy2.iroot((z+2*n),2) print(qaddp) qaddp= 250474028594377426111821218884061933467907597574578255066146260367094595399741196827532923836761733594976933366636149201492628708413319929361097646526652140204561542573663223469009835925309935515892458499676903149172534494580503088868430625144808189083708827363335045028702993282231537893799541685169911232442 phi = n-qaddp+1 phi=gmpy2.mpz(phi) d = gmpy2.invert(e,phi) print('d:',d) m = gmpy2.powmod(c,d,n) flag = binascii.unhexlify(hex(m)[2:]) print('flag:',flag)

3.[ACTF新生赛2020]crypto-rsa3

直接用yafu分解n，后面就是常规的rsa解题过程了。

import binascii import gmpy2 e=65537 q = 13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179293 p = 13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179231 n = 177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683 c = 1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049 phi = (q-1)*(p-1) n = p*q d = gmpy2.invert(e,phi) m = pow(c,d,n) flag = binascii.unhexlify(hex(m)[2:]) print(flag)

4.[RoarCTF2019]babyRSA

打开文件有阶乘运算想到威尔逊定理，解题过程推到如下： 代码：

import gmpy2 import binascii import sympy A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407 B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596 A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927 B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026 n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733 e=0x1001 c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428 def jie(A,B): ans=1 temp=gmpy2.powmod(-1,1,A) for i in range(B+1,A): ans=(ans * gmpy2.invert(i,A) )%A return (ans*temp)%A p = sympy.nextprime(jie(A1,B1)) q = sympy.nextprime(jie(A2,B2)) r = n//p//q phi = (p-1)*(q-1)*(r-1) d = gmpy2.invert(e,phi) flag = gmpy2.powmod(c,d,n) print(binascii.unhexlify(hex(flag)[2:]))

5.[MRCTF2020]Easy_RSA

先读懂代码，关键在于求P，Q。

首先看gen_p()函数要求P必须知道p，q 由两个等式可求p，q。用sage解方程： 再求P：

p1 = 118153578345562250550767057731385782963063734586321112579869747650001448473633860305142281504862521928246520876300707405515141444727550839066835195905927281903880307860942630322499106164191736174201506457157272220802515607939618476716593888428832962374494147723577980992661629254713116923690067827155668889571 q1 = 118975085954858660642562584152139261422493348532593400307960127317249511761542030451912561362687361053191375307180413931721355251895350936376781657674896801388806379750757264377396608174235075021854614328009897408824235800167369204203680938298803752964983358298299699273425596382268869237139724754214443556383 f1 = 2021*p1 + 2020*q1 if f1<0: f = (-1)*f1 P = sympy.nextprime(f1) print('P:',P)

接着来求Q，已知e*d，n求p，q参考RSA已知e，d和n，分解N 脚本：

from random import randint import gmpy2 def oddr(r): while r % 2 == 0: r = r // 2 return r def funp(e_d, N): k = e_d - 1 r = oddr(k) while True: b = randint(2, N - 1) a = gmpy2.powmod(b, r, N) if a == 1: continue y = gmpy2.gcd(a - 1, N) if a > 1 and y > 1: q = N // y return q else: r = r * 2 n = 20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947 e_d = 100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201 p = funp(e_d, n) q = n // p phi = n - (p + q) + 1 if p * q == n: print('p:',p) print('q:',q)

再求Q：

q2 = 171847486694659608706336923173786708071603689972942289760669690002615525263534483261477699540482615520223300780778172120221008417518590133753701145591943840552802072474293556608389677806415392384924913911677288126066245025731416399656855625839288752326267741979436855441260177305707529456715625062080892327017 p2 = 120538849514661970159855851547577637711900368732462953774738483480759950867244867240401273864984981385806453735655967797329769252143125966966236767391995563418243748302685348336642872306042286401427581501609713577329945760930395130411743322595026287853073310150103535873078436896035943385067893062698858976291 f2 = 2021 * p2 - 2020 * q2 if f2 < 0: factor2 = (-1) * f2 Q = sympy.nextprime(f2) print('Q：',Q)

后面就常规的rsa解密了：

c = 40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021 e = 65537 d = gmpy2.invert(e,(Q-1)*(P-1)) m = pow(c,d,P*Q) flag = long_to_bytes(m) print(flag)

6.[MRCTF2020]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 '''

分析完代码主要求q，p。 求q容易就幂的模（开始我用的python自带函数pow()算不出来还是要用gmpy2库的powmod()）

#求q Q = gmpy2.powmod(sub_Q,Q_2,Q_1) q = sympy.nextprime(Q)

求p也简单就把P[9]左右的素数找到就好，用到sympy库的nextprime()，prevprime()。

#求p P = [0 for i in range(17)] P[9] = P_p for i in range(10,17): P[i] = sympy.nextprime(P[i-1]) for i in range(8,0,-1): P[i] = sympy.prevprime(P[i + 1]) P[0] = sympy.prevprime(P[1]) n = 1 phi = 1 for i in P: n *=i phi *= (i-1) d = gmpy2.invert(e,phi) m = gmpy2.powmod(P_factor,d,n) p = sympy.nextprime(m)

综合代码：

import binascii import sympy import gmpy2 P_p = 206027926847308612719677572554991143421 P_factor = 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839 Q_1 = 103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521 Q_2 = 151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743 sub_Q = 168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651 Ciphertext = 1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832 e = 65537 #求p P = [0 for i in range(17)] P[9] = P_p for i in range(10,17): P[i] = sympy.nextprime(P[i-1]) for i in range(8,0,-1): P[i] = sympy.prevprime(P[i + 1]) P[0] = sympy.prevprime(P[1]) n = 1 phi = 1 for i in P: n *=i phi *= (i-1) d = gmpy2.invert(e,phi) m = gmpy2.powmod(P_factor,d,n) p = sympy.nextprime(m) #求q Q = gmpy2.powmod(sub_Q,Q_2,Q_1) q = sympy.nextprime(Q) d=gmpy2.invert(e,(p-1)*(q-1)) plaintext=gmpy2.powmod(Ciphertext,d,p*q) print(binascii.unhexlify(hex(plaintext)[2:]))

7.[BJDCTF2020]Polybius

打开文件题目很明确给了密文，和hint hint用base64解密得到

与密文刚好2：1.搜索一下题目Polybius发现是一种加密方法。 信息安全加密技术–Polybius密码 密文出现aeiou五个字符，但是不知道排列顺序，选择暴力破解。 先把五个字符的所有排列 列出来按照5*5矩阵。再替换密文。 直接上脚本吧：

import itertools s="aeoiu" sumresult=[] for i in itertools.permutations(s,5): sumresult.append("".join(i)) print(sumresult) zimu = "abcdefghjklmnopqrstuvwxyz" for h in sumresult: c = "ou au uu oo oe ea ai ae au ie uo oe ei ea" n = 0 for i in h: for j in h: c = c.replace(i+j,zimu[n]) n +=1 cc = c.replace(' ', '') if 'flag'in cc: print(cc)

找到flag我是把i换成了j所以需要替换j为i。