Tags: rsa crypto pollard-p-1
Rating:
# toydl
## Challenge [[Link]](https://ctftime.org/task/20472)
> Somebody gives many clue for decrypting ciphertext. How do you obtain the flag?
> nc toydl.crewctf-2022.crewc.tf 1337
## Solution
After connecting to the server, we got:
```
== 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(2, x, n) = 3, x->4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229194
pow(2, x, n) = 6, x->4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229195
pow(2, x, n) = 7, x->1711445377659847937601048743127792894663395582035721437850764667958715668936426339862746933835485061086301989324627651083245932409004488051470920327234756771433694118073902607544207633552099991451060285991062573131579425718487903656405450657236154345643778100618362544607755400925661988243449576179608268106517192
pow(2, x, n) = 9, x->3754939778354158910107789877335886849355087278630804477809002556307824523516424124875830766489409359374346298779402434539775766276216233569237231723341252968455894584408143678496101610613389877101646294181565422615598678053423609327485531311004778211836628609338110226534895570202818439605250908707603466887326390
pow(3, x, n) = 4, x->1363952586418552326838027389457770381128348610341916654151049344040269791768048789580711074747324279253953986869951673094759791136335614290642926045930520993156736257909660908648437081973019508017016877769804013904226195162132557973767673754417051913608582789200470895254896416316547292509925572389642012264907490
pow(3, x, n) = 7, x->2108313327065898035640892415345563086173030498575489939276428678662590490764646819880954837849939911577079891606499075752927419013712227778532427019242881857120209568990729106084788120925368694053101846896564389670119774572485264744679044261124989413694839721244251831062925927717237690766950273365675428680548680
pow(4, x, n) = 3, x->2076118641589166085567213874123474567491402237019668147884288468645748227900602149506213192343093244218866119520289447791172877431433341258605333332347317311240605414266962400678327394383961953495485042589683815930048091844890318004699674982043472077122232159707521022410989077157770575872817558884492139975614597
pow(4, x, n) = 7, x->855722688829923968800524371563896447331697791017860718925382333979357834468213169931373466917742530543150994662313825541622966204502244025735460163617378385716847059036951303772103816776049995725530142995531286565789712859243951828202725328618077172821889050309181272303877700462830994121724788089804134053258596
pow(4, x, n) = 9, x->1877469889177079455053894938667943424677543639315402238904501278153912261758212062437915383244704679687173149389701217269887883138108116784618615861670626484227947292204071839248050805306694938550823147090782711307799339026711804663742765655502389105918314304669055113267447785101409219802625454353801733443663195
pow(5, x, n) = 3, x->2133766932864388673682415264428852563157697531212805381722606537415880821651881836036219743693469157186116448622886351607608930829881035994695888699244352664133706885871664208865202356948720814126562878822367646312138979081062675067312895961013235414261084030444892478136847891250703661546259439777289170770933244
pow(5, x, n) = 4, x->1409828699698033208091409044455165366643801419932373553123260771987699896353688393694756863763560622086506122042233901651495199885942636834433947550336356542178907165298626723075515405354701129627152693478823016506389518956567226250580121882030622556782873851604640300443552173844660124075798887496649067556217390
pow(5, x, n) = 7, x->3916704810437927145600864918236836170491099995953699168541731264707734332610664820402524451306018121752526504056848858498261740094610196113519273038900804576322610451175905222231364299872297068281255941214365432478262573598957328534058633443808701127122560630454143760365394739477719428783885592620907691725814382
pow(5, x, n) = 9, x->4267533865728777347364830528857705126315395062425610763445213074831761643303763672072439487386938314372232897245772703215217861659762071989391777398488705328267413771743328417730404713897441628253125757644735292624277958162125350134625791922026470828522168060889784956273695782501407323092518879554578341541866488
pow(6, x, n) = 2, x->939292781082112016281996120029640558513504271209074729744679536785999346698143634739122352482233665730748662161995597875421203578208037954730627469631250345432329905035343676336544953322597208540536869444672643207916253721052582779000448220996637632239183670918288993354842447149274646102688185469428348953985987
pow(6, x, n) = 3, x->3610242006920393415879069499128370862097017398238793383983471781489169041387840838409899650400729951770369517139759758749494539871309093510453474136416765931074197167624362247880663013599860728339757006732497197896677435605085079912312720396172472464413116358573684869754218291278989217783331141360936744061146012
pow(6, x, n) = 4, x->1878585562164224032563992240059281117027008542418149459489359073571998693396287269478244704964467331461497324323991195750842407156416075909461254939262500690864659810070687352673089906645194417081073738889345286415832507442105165558000896441993275264478367341836577986709684894298549292205376370938856697907971974
pow(6, x, n) = 7, x->4382451963215414951923427484295917714075099595415988392264685392449057783423441922126020145423600985804385331915992918388410803253438498450309874925605271432370368439308396818520118534947166364332426731242512326875404549273011444416465627832281990548624424694040059123529752908838818278511190008322930537534907342
pow(6, x, n) = 8, x->2817878343246336048845988360088921675540512813627224189234038610357998040094430904217367057446700997192245986485986793626263610734624113864191882408893751036296989715106031029009634859967791625621610608334017929623748761163157748337001344662989912896717551012754866980064527341447823938308064556408285046861957961
pow(6, x, n) = 9, x->2670949225838281399597073379098730303583513127029718654238792244703169694689697203670777297918496286039620854977764160874073336293101055555722846666785515585641867262589018571544118060277263519799220137287824554688761181884032497133312272175175834832173932687655395876399375844129714571680642955891508395107160026
pow(7, x, n) = 3, x->302667136777917447885639399855798746783792281082047426137560224394234690761198213214781903275125974443412434383258389499537763965208434880475329103516951799391535587982643066857765962424901807944918698865193821688853878387134235170443608989618620354405251870857636073985822876614487518015398151778674906411808601
pow(7, x, n) = 4, x->782048530527862007921345086825967824809921804253677698357640394456486443141294396991806703662463153174674499822712272620352264740247063132442983714411111748779418558073361927132656469123102907840771323625012596232213516808553077385813641065260507991821817461035116755889737568582054061118287348291920439180743213
pow(7, x, n) = 9, x->605334273555834895771278799711597493567584562164094852275120448788469381522396426429563806550251948886824868766516778999075527930416869760950658207033903598783071175965286133715531924849803615889837397730387643377707756774268470340887217979237240708810503741715272147971645753228975036030796303557349812823617202
pow(8, x, n) = 3, x->1384079094392777390378142582748983044994268158013112098589525645763832151933734766337475461562062162812577413013526298527448584954288894172403555554898211540827070276177974933785551596255974635663656695059789210620032061229926878669799783321362314718081488106471680681607326051438513717248545039256328093317076398
pow(8, x, n) = 4, x->3033023192001670288107377079438674280407014446298578742485434212183445592057322982099348001921975745000745452867836904416610495633011420976789401070698677517671018048439803949478138644614971957920195917451446560736395792884091775127542112411446073397768200019661315908739373825618842575924012884553576728676754666
pow(8, x, n) = 6, x->2900590690393612534431831122468320185197775381162401469832242751855554947962396257387149462523050035312950139447444750735753832770794604660798256090247550299662579300397876908524620918563460614623754653785512490988229957671972766233570839527085351416965588116302338635977012964247935005210551481533116457655453731
pow(8, x, n) = 7, x->570481792553282645867016247709264298221131860678573812616921555986238556312142113287582311278495020362100663108209217027748644136334829350490306775744918923811231372691300869181402544517366663817020095330354191043859808572829301218801816885745384781881259366872787514869251800308553996081149858726536089368839064
pow(8, x, n) = 9, x->2768158188785554780756285165497966089988536316026224197179051291527664303867469532674950923124124325625154826027052597054897169908577788344807111109796423081654140552355949867571103192511949271327313390119578421240064122459853757339599566642724629436162976212943361363214652102877027434497090078512656186634152796
pow(9, x, n) = 4, x->681976293209276163419013694728885190564174305170958327075524672020134895884024394790355537373662139626976993434975836547379895568167807145321463022965260496578368128954830454324218540986509754008508438884902006952113097581066278986883836877208525956804291394600235447627448208158273646254962786194821006132453745
pow(9, x, n) = 7, x->1054156663532949017820446207672781543086515249287744969638214339331295245382323409940477418924969955788539945803249537876463709506856113889266213509621440928560104784495364553042394060462684347026550923448282194835059887286242632372339522130562494706847419860622125915531462963858618845383475136682837714340274340
```
I have no idea how these small numbers are used, but I found some interesting obeservation:
```
pow(2, x1, n) = 3, x1->4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229194
pow(2, x2, n) = 9, x2->3754939778354158910107789877335886849355087278630804477809002556307824523516424124875830766489409359374346298779402434539775766276216233569237231723341252968455894584408143678496101610613389877101646294181565422615598678053423609327485531311004778211836628609338110226534895570202818439605250908707603466887326390
```
We have `pow(2, x1, n)^2 == pow(2, x2, n)`. Let's assume `X = 2 * x1 - x2`, then we have `X % phi(n) == X % (p - 1) * (q - 1) == 0`.
This means `p - 1` and `q - 1` must be divisible by `X`.
Luckily, `X` is smooth per [factordb](http://factordb.com/index.php?query=4549534788002505432161065619158011420610521669447868113728151318275168388085984473149022002882963617501118179301755356624915743449517131465184101606048016276506527072659705924217207966922457936880293876177169841104593689326137662691313168617169110096652300029491973863109060738428263863886019326830365093015131998), then `p - 1` and `q - 1` must be smooth too. Thus we can apply [Pollard's p-1 algorithm](https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm) here to factorize `n`.
Once we get `n = p * q`, we can solve the standard [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) given `p, q, e, c, n`.
```python
from Crypto.Util.number import long_to_bytes
# pow(2, x, n) = 3, x->4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229194
# pow(2, x, n) = 9, x->3754939778354158910107789877335886849355087278630804477809002556307824523516424124875830766489409359374346298779402434539775766276216233569237231723341252968455894584408143678496101610613389877101646294181565422615598678053423609327485531311004778211836628609338110226534895570202818439605250908707603466887326390
n = 9099069576005010864322131238316022841221043338895736227456302636550336776171968946298044005765927235002236358603510713249831486899034262930368203212096032559091664507617383780759417104649503558521835589329751163691461155254201486010636703570864285313772976190442467858988008292898546327400223671343777884080302269
e = 65537
c = 7721448675656271306770207905447278771344900690929609366254539633666634639656550740458154588923683190330091584419635454991419701119568903552077272516472473602367188377791329158090763546083264422552335660922148840678536264063681459356778292303287448582918945582522946194737497041408425657842265913159282583371732459
x1 = 4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229194
x2 = 3754939778354158910107789877335886849355087278630804477809002556307824523516424124875830766489409359374346298779402434539775766276216233569237231723341252968455894584408143678496101610613389877101646294181565422615598678053423609327485531311004778211836628609338110226534895570202818439605250908707603466887326390
assert power_mod(2, x1, n) == 3
assert power_mod(2, x2, n) == 9
X = 2 * x1 - x2
# X % (p - 1) == 0 and X % (q - 1) == 0
X_factors = [x for (x, m) in factor(X) for _ in range(m)]
assert reduce(lambda x, y: x * y, X_factors) == X
# Pollard's p-1 algorithm
# https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm
def factor(n):
a = 2
b = 2
while True:
a = power_mod(a, b, n)
p = gcd(a - 1, n)
if 1 < p < n:
return p
b += 1
# q = factor(n)
q = 2667409485887452272770831798706991010944832728754072378737171107257239406526140122282372492002898629230454157958918945658178559315566157078990098518311104787
p = n // q
assert is_prime(p) and is_prime(q) and p * q == n
assert X % (p - 1) == 0 and X % (q - 1) == 0
d = inverse_mod(e, (p - 1) * (q - 1))
m = power_mod(c, d, n)
flag = long_to_bytes(m).decode().strip('@')
assert flag == 'crew{d15cr373_l06_15_r3duc710n_f0r_f4c70r1n6}'
print(flag)
```
## Flag
`crew{d15cr373_l06_15_r3duc710n_f0r_f4c70r1n6}`
## References
- [Pollard's p-1 algorithm](https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm)
- [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem))
