Rating: 5.0
# 4k-rsa:crypto:389pts
Only n00bz use 2048-bit RSA. True gamers use keys that are at least 4k bits long, no matter how many primes it takes...
[4k-rsa-public-key.txt](4k-rsa-public-key.txt)
# Solution
RSAを解くだけの問題に思われる。
与えられたnを[FactorDB](http://factordb.com/)で素因数分解すると以下のようになった。
```text
9353689450544968301・9431486459129385713・9563871376496945939・9734621099746950389・9736426554597289187・10035211751896066517・10040518276351167659・10181432127731860643・10207091564737615283・10435329529687076341・10498390163702844413・10795203922067072869・11172074163972443279・11177660664692929397・11485099149552071347・11616532426455948319・11964233629849590781・11992188644420662609・12084363952563914161・12264277362666379411・12284357139600907033・12726850839407946047・13115347801685269351・13330028326583914849・13447718068162387333・13554661643603143669・13558122110214876367・13579057804448354623・13716062103239551021・13789440402687036193・13856162412093479449・13857614679626144761・14296909550165083981・14302754311314161101・14636284106789671351・14764546515788021591・14893589315557698913・15067220807972526163・15241351646164982941・15407706505172751449・15524931816063806341・15525253577632484267・15549005882626828981・15687871802768704433・15720375559558820789・15734713257994215871・15742065469952258753・15861836139507191959・16136191597900016651・16154675571631982029・16175693991682950929・16418126406213832189・16568399117655835211・16618761350345493811・16663643217910267123・16750888032920189263・16796967566363355967・16842398522466619901・17472599467110501143・17616950931512191043・17825248785173311981・18268960885156297373・18311624754015021467・18415126952549973977
```
Multi-prime RSAというやつらしい。
以下のmpdec.pyで復号する。
```python:mpdec.py
# -*- coding: utf-8 -*-
# https://satto.hatenadiary.com/entry/picoctf-2018-cryptography#Super-Safe-RSA-3---Points-600より
import gmpy
import codecs
n = 5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877
e = 65537
c = 3832859959626457027225709485375429656323178255126603075378663780948519393653566439532625900633433079271626752658882846798954519528892785678004898021308530304423348642816494504358742617536632005629162742485616912893249757928177819654147103963601401967984760746606313579479677305115496544265504651189209247851288266375913337224758155404252271964193376588771249685826128994580590505359435624950249807274946356672459398383788496965366601700031989073183091240557732312196619073008044278694422846488276936308964833729880247375177623028647353720525241938501891398515151145843765402243620785039625653437188509517271172952425644502621053148500664229099057389473617140142440892790010206026311228529465208203622927292280981837484316872937109663262395217006401614037278579063175500228717845448302693565927904414274956989419660185597039288048513697701561336476305496225188756278588808894723873597304279725821713301598203214138796642705887647813388102769640891356064278925539661743499697835930523006188666242622981619269625586780392541257657243483709067962183896469871277059132186393541650668579736405549322908665664807483683884964791989381083279779609467287234180135259393984011170607244611693425554675508988981095977187966503676074747171
multi_primes = [9353689450544968301,9431486459129385713,9563871376496945939,9734621099746950389,9736426554597289187,10035211751896066517,10040518276351167659,10181432127731860643,10207091564737615283,10435329529687076341,10498390163702844413,10795203922067072869,11172074163972443279,11177660664692929397,11485099149552071347,11616532426455948319,11964233629849590781,11992188644420662609,12084363952563914161,12264277362666379411,12284357139600907033,12726850839407946047,13115347801685269351,13330028326583914849,13447718068162387333,13554661643603143669,13558122110214876367,13579057804448354623,13716062103239551021,13789440402687036193,13856162412093479449,13857614679626144761,14296909550165083981,14302754311314161101,14636284106789671351,14764546515788021591,14893589315557698913,15067220807972526163,15241351646164982941,15407706505172751449,15524931816063806341,15525253577632484267,15549005882626828981,15687871802768704433,15720375559558820789,15734713257994215871,15742065469952258753,15861836139507191959,16136191597900016651,16154675571631982029,16175693991682950929,16418126406213832189,16568399117655835211,16618761350345493811,16663643217910267123,16750888032920189263,16796967566363355967,16842398522466619901,17472599467110501143,17616950931512191043,17825248785173311981,18268960885156297373,18311624754015021467,18415126952549973977]
phi = 1
for x in multi_primes:
phi *= (x - 1)
d = gmpy.invert(e, phi)
m = pow(c, d, n)
print(m)
print(codecs.decode(('%x'%m),'hex_codec'))
```
実行するとflagが得られる。
```bash
$ python2 mpdec.py
706900059475106681301586714568958471062774799484906508017771377121899901
flag{t0000_m4nyyyy_pr1m355555}
```
## flag{t0000_m4nyyyy_pr1m355555}
