BUUCTF RSA（三）

1.[MRCTF2020]babyRSA

根据给出的代码可以很容易推出
_Q = sympy.nextprime(pow(sub_Q,Q_2,Q_1))。我们知道P[9]，就可以推出其他的素数，从而求出n1 = P[0] * … * P[16]和φ(n1) = (P[0]-1) * … * (P[16]-1),然后可以解出 _P。 _Q , _P , e , c 知道了就可以求出明文。

import gmpy2,libnum,sympy
from Crypto.Util.number import long_to_bytes
e = 65537
P_factor = 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839
P = [0 for i in range(17)]
P[9] = 206027926847308612719677572554991143421
i = 8
for i in range(9,0,-1):P[i-1] = sympy.prevprime(P[i])
for i in range(10,17):P[i] = sympy.nextprime(P[i-1])
n1 = 1
PHI = 1
for i in range(17):n1 *= P[i]PHI *= P[i]-1 
d1 = int(gmpy2.invert(e,PHI))
_P = sympy.nextprime(pow(P_factor,d1,n1))Q_1 = 103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521
Q_2 = 151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743
sub_Q = 168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651
_Q = sympy.nextprime(pow(sub_Q,Q_2,Q_1))Ciphertext = 1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832
N = _P*_Q
phi = (_P-1)*(_Q-1)
d = int(gmpy2.invert(e,phi))
m = pow(Ciphertext,d,N)
print(long_to_bytes(m))

2.[WUSTCTF2020]dp_leaking_1s_very_d@angerous

这个是已知dp,e,n,c的攻击方法。
dp,dq的解决方法

import libnum,gmpy2
e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825pd = e*dp-1
for t in range(1,e):if  pd%t == 0:p = pd//t + 1if n%p == 0:breakq = n//p
d = int(gmpy2.invert(e,(q-1)*(p-1)))
m = pow(c,d,n)
print(libnum.n2s(m))

3.[NPUCTF2020]EzRSA

这里的e = 54722，不是素数，明显不对劲。觉得题目有问题，求助网络。是啊！e不是素数，那我就把它变成素数呗。有公式e * d = 1 mod φ(n)，而e//2之后是素数，故有e * d = (e / 2) * (2 * d) = 1 mod φ(n)，令e1 = e/2，d1 = 2 * d，故e1 * d1 = 1 mod φ(n)。而m = c^d mod n ，所以m1 = c^d1 mod n =c^2*d mod n = m² mod n，所以求出m1再开根号就求出了m。

'''文件内容 from gmpy2 import lcm , powmod , invert , gcd , mpz from Crypto.Util.number import getPrime from sympy import nextprime from random import randint p = getPrime(1024) q = getPrime(1024) n = p * q gift = lcm(p - 1 , q - 1)#最小公倍数 e = 54722 #??? flag = b'NPUCTF{******************}' m = int.from_bytes(flag , 'big') c = powmod(m , e , n) print('n: ' , n) print('gift: ' , gift) print('c: ' , c) '''
import gmpy2,libnum
from Crypto.Util.number import long_to_bytes
n = 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
gift = 2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104
#gift = (p-1)*(q-1)//gcd(p-1,q-1)
c = 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
p = 106021448991021391444550749375115277080844281746248845802565680557785009341952320484175568763707424932172033597514861602114171459176440279045761846695231788376075050452154924141266290931413542110639081792550648106240966552406813059396358355737185354885474455248579946190266152416149137616855791805617206153497
q = 161136651053130509602530659420755324119806487925813087617466818245407407797561810253722204813002837916779909309520498985459703212021249251124954613236122142746302911323565396331355397916764254680629384957057354297855676493062493901977415968666512459829211010720514167083018352796496733697235524845188512914793
e = 54722    #e不是素数？
phi = (p-1)*(q-1)
print(gmpy2.is_prime(e//2))#True
d1 = int(gmpy2.invert(e//2,phi))
m1 = pow(c,d1,n)
m = int(gmpy2.iroot(m1,2)[0])
print(long_to_bytes(m))

4.[MRCTF2020]Easy_RSA

设gen_p()中的p,q是p1,q1，gen_q()中的p,q是p2,q2，根据python中的代码可以推出
_P = sympy.nextprime(2021 * p1 + 2020 * q1)
_Q = sympy.nextprime(abs(2021 * p2 - 2020 * q2))

import gmpy2,sympy
from Crypto.Util.number import long_to_bytes
P_n =  14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024336556028267742021320891681762543660468484018686865891073110757394154024833552558863671537491089957038648328973790692356014778420333896705595252711514117478072828880198506187667924020260600124717243067420876363980538994101929437978668709128652587073901337310278665778299513763593234951137512120572797739181693
p1 = 118153578345562250550767057731385782963063734586321112579869747650001448473633860305142281504862521928246520876300707405515141444727550839066835195905927281903880307860942630322499106164191736174201506457157272220802515607939618476716593888428832962374494147723577980992661629254713116923690067827155668889571
q1 = 118975085954858660642562584152139261422493348532593400307960127317249511761542030451912561362687361053191375307180413931721355251895350936376781657674896801388806379750757264377396608174235075021854614328009897408824235800167369204203680938298803752964983358298299699273425596382268869237139724754214443556383
P_F_n =  14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024099427363967321110127562039879018616082926935567951378185280882426903064598376668106616694623540074057210432790309571018778281723710994930151635857933293394780142192586806292968028305922173313521186946635709194350912242693822450297748434301924950358561859804256788098033426537956252964976682327991427626735740
_P = sympy.nextprime(2021 * p1 + 2020 * q1)Q_n =  20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
p2 = 120538849514661970159855851547577637711900368732462953774738483480759950867244867240401273864984981385806453735655967797329769252143125966966236767391995563418243748302685348336642872306042286401427581501609713577329945760930395130411743322595026287853073310150103535873078436896035943385067893062698858976291
q2 = 171847486694659608706336923173786708071603689972942289760669690002615525263534483261477699540482615520223300780778172120221008417518590133753701145591943840552802072474293556608389677806415392384924913911677288126066245025731416399656855625839288752326267741979436855441260177305707529456715625062080892327017
_Q = sympy.nextprime(abs(2021 * p2 - 2020 * q2))
Q_E_D =  100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201Ciphertext =  40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021
_E = 65537
_N = _Q*_P
_phi = (_Q-1)*(_P-1)
_D = int(gmpy2.invert(_E,_phi))
_M = pow(Ciphertext,_D,_N)
print(long_to_bytes(_M))

5.[INSHack2019]Yet Another RSA Challenge - Part 1

''' import subprocess p = subprocess.check_output('openssl prime -generate -bits 2048 -hex') q = subprocess.check_output('openssl prime -generate -bits 2048 -hex') flag = int('INSA{REDACTED}'.encode('hex'), 16)N = int(p,16) * int(q,16) print N print '0x'+p.replace('9F','FC') print pow(flag,65537,N) '''
import libnum,gmpy2
N = 719579745653303119025873098043848913976880838286635817351790189702008424828505522253331968992725441130409959387942238566082746772468987336980704680915524591881919460709921709513741059003955050088052599067720107149755856317364317707629467090624585752920523062378696431510814381603360130752588995217840721808871896469275562085215852034302374902524921137398710508865248881286824902780186249148613287250056380811479959269915786545911048030947364841177976623684660771594747297272818410589981294227084173316280447729440036251406684111603371364957690353449585185893322538541593242187738587675489180722498945337715511212885934126635221601469699184812336984707723198731876940991485904637481371763302337637617744175461566445514603405016576604569057507997291470369704260553992902776099599438704680775883984720946337235834374667842758010444010254965664863296455406931885650448386682827401907759661117637294838753325610213809162253020362015045242003388829769019579522792182295457962911430276020610658073659629786668639126004851910536565721128484604554703970965744790413684836096724064390486888113608024265771815004188203124405817878645103282802994701531113849607969243815078720289912255827700390198089699808626116357304202660642601149742427766381
P = 25819261471728040800872878541553321043152462679774978922658476743054196609615260085066604058841210698540997524876908144621893909307784554414162036327648281377886327091581347296131947730522807494517124526464816238370951647893862934621121004498569156746311594099412832189045390297120305667254913052800653355550915386064296154605648963278915319806240264672354108048953297992497878897540380622959711963257886237782410901325113329109297590870937017452019018930748754331672736756917137583464384303108259463535106592418534804375728748609362332554496296532372320633175091519075027001631454173292550340940515568940345329163887
Q = 27869881035956015184979178092922248885674897320108269064145135676677416930908750101386898785101159450077433625380803555071301130739332256486285289470097290409044426739584302074834857801721989648648799253740641480496433764509396039330395579654527851232078667173592401475356727873045602595552393666889257027478385213547302885118341490346766830846876201911076530008127691612594913799272782226366932754058372641521481522494577124999360890113778202218378165756595787931498460866236502220175258385407478826827807650036729385244897815805427164434537088709092238894902485613707990645011133078730017425033369999448757627854563
C = 596380963583874022971492302071822444225514552231574984926542429117396590795270181084030717066220888052607057994262255729890598322976783889090993129161030148064314476199052180347747135088933481343974996843632511300255010825580875930722684714290535684951679115573751200980708359500292172387447570080875531002842462002727646367063816531958020271149645805755077133231395881833164790825731218786554806777097126212126561056170733032553159740167058242065879953688453169613384659653035659118823444582576657499974059388261153064772228570460351169216103620379299362366574826080703907036316546232196313193923841110510170689800892941998845140534954264505413254429240789223724066502818922164419890197058252325607667959185100118251170368909192832882776642565026481260424714348087206462283972676596101498123547647078981435969530082351104111747783346230914935599764345176602456069568419879060577771404946743580809330315332836749661503035076868102720709045692483171306425207758972682717326821412843569770615848397477633761506670219845039890098105484693890695897858251238713238301401843678654564558196040100908796513657968507381392735855990706254646471937809011610992016368630851454275478216664521360246605400986428230407975530880206404171034278692756
e = 65537
phi = (P-1)*(Q-1)
d = int(gmpy2.invert(e,phi))
m = pow(C,d,N)
print(libnum.n2s(m))