Tags: rsa crypto
Rating:
The problem give us a statement:
```txt
== proof-of-work: disabled ==
n: 9099069576005010864322131238316022841221043338895736227456302636550336776171968946298044005765927235002236358603510713249831486899034262930368203212096032559091664507617383780759417104649503558521835589329751163691461155254201486010636703570864285313772976190442467858988008292898546327400223671343777884080302269
Here is RSA encrypted flag.(e=65537)
7721448675656271306770207905447278771344900690929609366254539633666634639656550740458154588923683190330091584419635454991419701119568903552077272516472473602367188377791329158090763546083264422552335660922148840678536264063681459356778292303287448582918945582522946194737497041408425657842265913159282583371732459
Let's see a property of numbers... I like small numbers.
pow(4, x, n) = 3
x->2076118641589166085567213874123474567491402237019668147884288468645748227900602149506213192343093244218866119520289447791172877431433341258605333332347317311240605414266962400678327394383961953495485042589683815930048091844890318004699674982043472077122232159707521022410989077157770575872817558884492139975614597
pow(8, x, n) = 7
x->570481792553282645867016247709264298221131860678573812616921555986238556312142113287582311278495020362100663108209217027748644136334829350490306775744918923811231372691300869181402544517366663817020095330354191043859808572829301218801816885745384781881259366872787514869251800308553996081149858726536089368839064
pow(4, x, n) = 7
x->855722688829923968800524371563896447331697791017860718925382333979357834468213169931373466917742530543150994662313825541622966204502244025735460163617378385716847059036951303772103816776049995725530142995531286565789712859243951828202725328618077172821889050309181272303877700462830994121724788089804134053258596
pow(2, x, n) = 3
x->4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229194
pow(9, x, n) = 7
x->1054156663532949017820446207672781543086515249287744969638214339331295245382323409940477418924969955788539945803249537876463709506856113889266213509621440928560104784495364553042394060462684347026550923448282194835059887286242632372339522130562494706847419860622125915531462963858618845383475136682837714340274340
pow(5, x, n) = 7
x->3916704810437927145600864918236836170491099995953699168541731264707734332610664820402524451306018121752526504056848858498261740094610196113519273038900804576322610451175905222231364299872297068281255941214365432478262573598957328534058633443808701127122560630454143760365394739477719428783885592620907691725814382
pow(2, x, n) = 9
x->3754939778354158910107789877335886849355087278630804477809002556307824523516424124875830766489409359374346298779402434539775766276216233569237231723341252968455894584408143678496101610613389877101646294181565422615598678053423609327485531311004778211836628609338110226534895570202818439605250908707603466887326390
pow(4, x, n) = 9
x->1877469889177079455053894938667943424677543639315402238904501278153912261758212062437915383244704679687173149389701217269887883138108116784618615861670626484227947292204071839248050805306694938550823147090782711307799339026711804663742765655502389105918314304669055113267447785101409219802625454353801733443663195
pow(5, x, n) = 4
x->1409828699698033208091409044455165366643801419932373553123260771987699896353688393694756863763560622086506122042233901651495199885942636834433947550336356542178907165298626723075515405354701129627152693478823016506389518956567226250580121882030622556782873851604640300443552173844660124075798887496649067556217390
pow(6, x, n) = 2
x->939292781082112016281996120029640558513504271209074729744679536785999346698143634739122352482233665730748662161995597875421203578208037954730627469631250345432329905035343676336544953322597208540536869444672643207916253721052582779000448220996637632239183670918288993354842447149274646102688185469428348953985987
pow(5, x, n) = 3
x->2133766932864388673682415264428852563157697531212805381722606537415880821651881836036219743693469157186116448622886351607608930829881035994695888699244352664133706885871664208865202356948720814126562878822367646312138979081062675067312895961013235414261084030444892478136847891250703661546259439777289170770933244
pow(6, x, n) = 9
x->2670949225838281399597073379098730303583513127029718654238792244703169694689697203670777297918496286039620854977764160874073336293101055555722846666785515585641867262589018571544118060277263519799220137287824554688761181884032497133312272175175834832173932687655395876399375844129714571680642955891508395107160026
pow(7, x, n) = 4
x->782048530527862007921345086825967824809921804253677698357640394456486443141294396991806703662463153174674499822712272620352264740247063132442983714411111748779418558073361927132656469123102907840771323625012596232213516808553077385813641065260507991821817461035116755889737568582054061118287348291920439180743213
pow(8, x, n) = 3
x->1384079094392777390378142582748983044994268158013112098589525645763832151933734766337475461562062162812577413013526298527448584954288894172403555554898211540827070276177974933785551596255974635663656695059789210620032061229926878669799783321362314718081488106471680681607326051438513717248545039256328093317076398
pow(6, x, n) = 8
x->2817878343246336048845988360088921675540512813627224189234038610357998040094430904217367057446700997192245986485986793626263610734624113864191882408893751036296989715106031029009634859967791625621610608334017929623748761163157748337001344662989912896717551012754866980064527341447823938308064556408285046861957961
pow(5, x, n) = 9
x->4267533865728777347364830528857705126315395062425610763445213074831761643303763672072439487386938314372232897245772703215217861659762071989391777398488705328267413771743328417730404713897441628253125757644735292624277958162125350134625791922026470828522168060889784956273695782501407323092518879554578341541866488
pow(3, x, n) = 7
x->2108313327065898035640892415345563086173030498575489939276428678662590490764646819880954837849939911577079891606499075752927419013712227778532427019242881857120209568990729106084788120925368694053101846896564389670119774572485264744679044261124989413694839721244251831062925927717237690766950273365675428680548680
pow(2, x, n) = 6
x->4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229195
pow(7, x, n) = 3
x->302667136777917447885639399855798746783792281082047426137560224394234690761198213214781903275125974443412434383258389499537763965208434880475329103516951799391535587982643066857765962424901807944918698865193821688853878387134235170443608989618620354405251870857636073985822876614487518015398151778674906411808601
pow(6, x, n) = 4
x->1878585562164224032563992240059281117027008542418149459489359073571998693396287269478244704964467331461497324323991195750842407156416075909461254939262500690864659810070687352673089906645194417081073738889345286415832507442105165558000896441993275264478367341836577986709684894298549292205376370938856697907971974
pow(8, x, n) = 6
x->2900590690393612534431831122468320185197775381162401469832242751855554947962396257387149462523050035312950139447444750735753832770794604660798256090247550299662579300397876908524620918563460614623754653785512490988229957671972766233570839527085351416965588116302338635977012964247935005210551481533116457655453731
pow(6, x, n) = 3
x->3610242006920393415879069499128370862097017398238793383983471781489169041387840838409899650400729951770369517139759758749494539871309093510453474136416765931074197167624362247880663013599860728339757006732497197896677435605085079912312720396172472464413116358573684869754218291278989217783331141360936744061146012
pow(3, x, n) = 4
x->1363952586418552326838027389457770381128348610341916654151049344040269791768048789580711074747324279253953986869951673094759791136335614290642926045930520993156736257909660908648437081973019508017016877769804013904226195162132557973767673754417051913608582789200470895254896416316547292509925572389642012264907490
pow(7, x, n) = 9
x->605334273555834895771278799711597493567584562164094852275120448788469381522396426429563806550251948886824868766516778999075527930416869760950658207033903598783071175965286133715531924849803615889837397730387643377707756774268470340887217979237240708810503741715272147971645753228975036030796303557349812823617202
pow(2, x, n) = 7
x->1711445377659847937601048743127792894663395582035721437850764667958715668936426339862746933835485061086301989324627651083245932409004488051470920327234756771433694118073902607544207633552099991451060285991062573131579425718487903656405450657236154345643778100618362544607755400925661988243449576179608268106517192
pow(8, x, n) = 9
x->2768158188785554780756285165497966089988536316026224197179051291527664303867469532674950923124124325625154826027052597054897169908577788344807111109796423081654140552355949867571103192511949271327313390119578421240064122459853757339599566642724629436162976212943361363214652102877027434497090078512656186634152796
pow(6, x, n) = 7
x->4382451963215414951923427484295917714075099595415988392264685392449057783423441922126020145423600985804385331915992918388410803253438498450309874925605271432370368439308396818520118534947166364332426731242512326875404549273011444416465627832281990548624424694040059123529752908838818278511190008322930537534907342
pow(9, x, n) = 4
x->681976293209276163419013694728885190564174305170958327075524672020134895884024394790355537373662139626976993434975836547379895568167807145321463022965260496578368128954830454324218540986509754008508438884902006952113097581066278986883836877208525956804291394600235447627448208158273646254962786194821006132453745
pow(8, x, n) = 4
x->3033023192001670288107377079438674280407014446298578742485434212183445592057322982099348001921975745000745452867836904416610495633011420976789401070698677517671018048439803949478138644614971957920195917451446560736395792884091775127542112411446073397768200019661315908739373825618842575924012884553576728676754666
```
It's quite long, but after analyze, we recognize that, we actually need 3 arguments and last expression
+ `n=9099069576005010864322131238316022841221043338895736227456302636550336776171968946298044005765927235002236358603510713249831486899034262930368203212096032559091664507617383780759417104649503558521835589329751163691461155254201486010636703570864285313772976190442467858988008292898546327400223671343777884080302269`
+ `e = 65537`
+ `c = 7721448675656271306770207905447278771344900690929609366254539633666634639656550740458154588923683190330091584419635454991419701119568903552077272516472473602367188377791329158090763546083264422552335660922148840678536264063681459356778292303287448582918945582522946194737497041408425657842265913159282583371732459`
last expression:
```txt
pow(8, x, n) = 4
x->3033023192001670288107377079438674280407014446298578742485434212183445592057322982099348001921975745000745452867836904416610495633011420976789401070698677517671018048439803949478138644614971957920195917451446560736395792884091775127542112411446073397768200019661315908739373825618842575924012884553576728676754666
```
The reason we choose the last expression is because it is a clue for us to find phi(n), specifically as follows:
We have : `8^x = 4 (mod n)` or `2^{3x-2} = 1 (mod n)`
No we will analyze a litte bit about number of digit of `n` and `phi(n)`
We found that: Number of digits of `n` approxiate Number of digits of `phi(n)`
~~~
Because: n = p*q and phi(n) = (p-1)(q-1) ~ pq = n
~~~
And now, we continue see that:
`3x-2` has approxiate `n` , so we boldly guess that `3x-2` is `phi(n)`
And luckily, Finally we get the flag, detail as follow:
We have: `ed = 1 (mod phi(n))`, with `phi(n)=3x-2`
So we will easily find `d` and `flag = c^d (mod n)`
And this is my solution:
```py
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long,long_to_bytes
import random
import binascii
n = 9099069576005010864322131238316022841221043338895736227456302636550336776171968946298044005765927235002236358603510713249831486899034262930368203212096032559091664507617383780759417104649503558521835589329751163691461155254201486010636703570864285313772976190442467858988008292898546327400223671343777884080302269
e = 65537
c = 7721448675656271306770207905447278771344900690929609366254539633666634639656550740458154588923683190330091584419635454991419701119568903552077272516472473602367188377791329158090763546083264422552335660922148840678536264063681459356778292303287448582918945582522946194737497041408425657842265913159282583371732459
x = 3033023192001670288107377079438674280407014446298578742485434212183445592057322982099348001921975745000745452867836904416610495633011420976789401070698677517671018048439803949478138644614971957920195917451446560736395792884091775127542112411446073397768200019661315908739373825618842575924012884553576728676754666
phi_n = 3*x-2
d = pow(e,-1,phi_n)
flag = pow(c,d,n)
print(long_to_bytes(flag))
```
And we get result:
~~~
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@crew{d15cr373_l06_15_r3duc710n_f0r_f4c70r1n6}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
~~~
And flag is:
~~~
crew{d15cr373_l06_15_r3duc710n_f0r_f4c70r1n6}
~~~
