---
# System prepended metadata

title: (solved) Crypto/4k-rsa

---

# (solved) Crypto/4k-rsa
> Only n00bz use 2048-bit RSA. True gamers use keys that are at least 4k bits long, no matter how many primes it takes...

Provided file: `4k-rsa-public-key.txt`
```
n: 5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877
e: 65537
c: 3832859959626457027225709485375429656323178255126603075378663780948519393653566439532625900633433079271626752658882846798954519528892785678004898021308530304423348642816494504358742617536632005629162742485616912893249757928177819654147103963601401967984760746606313579479677305115496544265504651189209247851288266375913337224758155404252271964193376588771249685826128994580590505359435624950249807274946356672459398383788496965366601700031989073183091240557732312196619073008044278694422846488276936308964833729880247375177623028647353720525241938501891398515151145843765402243620785039625653437188509517271172952425644502621053148500664229099057389473617140142440892790010206026311228529465208203622927292280981837484316872937109663262395217006401614037278579063175500228717845448302693565927904414274956989419660185597039288048513697701561336476305496225188756278588808894723873597304279725821713301598203214138796642705887647813388102769640891356064278925539661743499697835930523006188666242622981619269625586780392541257657243483709067962183896469871277059132186393541650668579736405549322908665664807483683884964791989381083279779609467287234180135259393984011170607244611693425554675508988981095977187966503676074747171
```

Standard RSA problem with weak prime probably. Should be solvable with [RsaCtfTool](https://github.com/Ganapati/RsaCtfTool).

Tool gives output on ECM, but the output looks garbled?

``` sh 
# python3 RsaCtfTool.py -n 5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877 -e 65537 --uncipher 3832859959626457027225709485375429656323178255126603075378663780948519393653566439532625900633433079271626752658882846798954519528892785678004898021308530304423348642816494504358742617536632005629162742485616912893249757928177819654147103963601401967984760746606313579479677305115496544265504651189209247851288266375913337224758155404252271964193376588771249685826128994580590505359435624950249807274946356672459398383788496965366601700031989073183091240557732312196619073008044278694422846488276936308964833729880247375177623028647353720525241938501891398515151145843765402243620785039625653437188509517271172952425644502621053148500664229099057389473617140142440892790010206026311228529465208203622927292280981837484316872937109663262395217006401614037278579063175500228717845448302693565927904414274956989419660185597039288048513697701561336476305496225188756278588808894723873597304279725821713301598203214138796642705887647813388102769640891356064278925539661743499697835930523006188666242622981619269625586780392541257657243483709067962183896469871277059132186393541650668579736405549322908665664807483683884964791989381083279779609467287234180135259393984011170607244611693425554675508988981095977187966503676074747171 --private --attack ecm

[*] Testing key /tmp/tmp1daqlcf4.
[*] Performing ecm attack on /tmp/tmp1daqlcf4.
[*] ECM Method can run forever and may never succeed, timeout set to 30sec. Hit Ctrl-C to bail out.

Results for /tmp/tmp1daqlcf4:

Private key :
-----BEGIN RSA PRIVATE KEY-----
MIIIGwIBAAKCAf0UreVRwhwfMmTkP34vgfV0qA/11vvH2wsPlDDksuVbIq5vQUqZ
CJrBstWLAXR7apc+ywpHNwOgCzmgfEKK9qkKTpy2qd641t6TL6rw43VX59uN+4UL
RudMeKZEXLRKlK+Mf3Q4UDXmuzQXb/IT9r7KWr7fOMbks3KGullul6qXKgmaVV/A
EIXyH8OL0BGCKd2Z77fPHVDvoaj7J5VcRgF+/8OYH01wi3EEtSEIXteLkcsU+dx9
30oUkiURfMGiVi+MEbJ2bcT5ftusm62L1fe3GtGnQ+TiUFZCn4c0THxT9o5p1tXA
LuCS1M9WhNttcH1h4PBGQa9Q1NHGZfUfP1RkyNmO5VPjI+PqWNWFMYN6C3CB+AXk
4/qp1MEUiGqSQsY++4cdOxONgQUGm0znHz5cSlPTDPFMgGH3faGASNv9KDOmiwxj
7JRi1S6deY3Yg47nvlEUEfKWkt+uba3WM+n8RZ+zqed/Q9d+iCvCwyAgg9HdPX1X
nGy7GuVSAfvFfwCmVC2oJNUoRVQwMuEXy9sSdZ55AmG9SE9f0gGBY6AXl3yEPbkR
RUFle2w8zG2+9I9TvNn93hd7kW+X4kl8TZJmbsIVzkRvl0AFxGYcltjxpuu8k1jr
jFJ/i7s+VectRoTxlxLN6GzAPSo5KRflFwdtZ1dIk9ufcLgfyM5fdQIDAQABAoIB
/RBMd0AXZB7afTJ/gh2ckyR2lWGyR5oCqlQW1ccsqcpxeKbBZO2pHCj5HyRp6bp6
EarStThFfLIu3XJgGU9bBanY+ia9n7R+YfLGKFipbE5CyY8pEwYO14l1VoWK8A37
vwZCFgtXHB1PDhKbM6CaRBIKG8Bq2o+kGco2CA/ZLjQBg38PBh3ewcgARvKcJSrn
jVdohj4daheQ6aMPRC5o9eGdNouabPCWP+HmalUAc6saVT2kTukuyBIX84MI6rYY
ScSMpSPVF0S1/yESk5QuJljdZJR+3MAnMbMWmiOzAnYzpCLt9GDaFFb8wGwYuMDd
uMC/416VZBbo/tLf8DaXUHHSskIg8nLrX3PRY9sijE5W2Xg/Wgbd417VUTdQhhdx
1Guc1QDRx3ty4av5RASYDtMADQSROsbWmWv4chulLh7mhEyRwT0/N/7fWW/Onlx5
1so3wsmJGermA0MCT3EZSZ70qJJ/0Zr2MQgu2B32bb0dbxsaF0ajJagZmwK8F/oM
9rmk8TGvYK/vWIqgQqf1Wu3fwpQEGyleRfKPkkgbiw2MTSd46LLEmAOTOi4iOC9p
4595MeVti8Qu018BzXg/Hj705o3oQ4/lEqICDDIgXLiE6RaF0WXQ15RoCWi3oet9
EhU3y32xNjUYK5Ytm/yNBxeW9M5g7ccm0iD1RfyJAgkAvHKBINKj0T8CggH1HBeZ
Yf1wLDmP1oIjLm4cLxPlEIU2mmzF1EmtkqTHfiZelzAvi6yrrtJfZPqhZWFIVcfy
nzlGtJftl6tvKxWWJCRtg4Q2mzMEb2TaoWMWyECkTXC2Kbw+cgY7nTCGzyPxURYN
nclQ+MtqB/YTe5Qm4ve6EgkiyFSx7NC1b7RN8Lwung3dNoPa3WsK+mAmcbXl/Pn1
7/0KzKRSmUaATLiPZ2w329HAOaCxM/tdiOK1qYeUuVGd1ZeTuw5P6r2+yRlYxs3Q
rLrM/BJROCewcf9n99iU+b9CxV/MMz+7a+e9dP3+3rKRKexryxdG52GFYZVgyiSw
OTm8ILxugq80C/nAJx+e0zfT0TP9duAwc4flRDzGT+F8n7NMXC3oXVimZK1hKBSo
SQms3uRKP4Bka5B4zvy5mUYLalOMPRx6JjJNRqelVbZxcfUjmk3LtoCoZXMeU48J
9gUGIuZJGGzwWV+bU3kZxz9+U7jHZkF3KpKQ72Vg/6UsvaREHGF7IPdZRA6wACdQ
QycAXZ5OU0A1pDFYm+RCJbS+ofC4O4Yk17oqm5sNCGpzpPVLCbH6W/nYkx4kwHoX
nKDJXJtT8Dtg481OgKTkjYBkONvqpvgffroJNTi5yLNNnQTRuiFyRrTn9Z2kz/3c
QP1cFBoVDv9v+3oweQgQWW5LAghdoreuy3tCmQKCAfUPSaR2GCcAWj71vJKKxO9f
i1MgH26ssT8jnQjxgezysMzPODDXsRspI2E4odBNTJjB3fMiRVg+FWP+IxR3fOLd
Plm+tafF5Aio2ljEdRlD1zHS1uC7a68L/Gpay7rBZU0BFKBKWvFOw9wrAvZtTR2w
bKH9CK2+GaFOP/JNHPFBbhdseh0FetITpxotUT/6p8PGXP1DIhDLdy1gLmbJ2bJo
1RK89LPIaLOml0e6o6262YbNJyZew4Noy4wgMixuYfXXEtBZ/7pn/0vl5Gt4Tkb1
MQ85rqUWpmCJD0jemxmWXldiOAkZqIis2DkE2CRvC4zF1Rt1uP6xTfpR8ii/z6WL
ZQDY70u9UK7CD5UueikBbpV5iTt56WhHzc/jZMgAh/4UgtFmFfbWwaPKVQPRKakk
85HJYL37mgX6h9HNkZhOOBOYxpWML5y1b1rKMc/yjahWTsRb9zX0rh/fRAG0kXwE
/CVUMjB8PVV+R2gjaemn7iLQXMIxXgCW9VG9if4xNFEBdGOQd9wSFoGHeqz2cshG
5fw9atRHaqnH8uN/5tcjIUkBaHUQs1CnsQyPGzOKNGBJwuewnCuY0wrl9Fpw/hyX
k6SxgMqJytwzC1qQa4txRDKOj01QgvvjcCoxYmfNWYIEkqFXWMnQQrVtGQOG9mME
qqfDE2sCCA/sA6+spNDE
-----END RSA PRIVATE KEY-----

Unciphered data :
HEX : 0x07b163c0bf66d28a67c88db5450f12a5fdffdf44514bd6f2fe42f05007bc850ac3e26e7eb5f7705b0653fee502dd349711467e7946d580db20ca5b25578fd2e8706ed73f15eae2147e98b0b77f7fafb9db3c0e49ecef94f8bfc1a6c2ae034ee07c5d9c970eb45566c0b6c3a14d39b81b6bf042a60ab386387796b0a852815b2c590c233ca1158ef07136bded0a3fdac95a90303df947541dd04a7a07ea5251c9c1469d7054252d65bd7b893c4d0cb42c6a8dc1026830b50139df72cfa0133870a8d4d29b33f5b8292dd869a8f98c258b976b9dba3f789b4aafbf827dbdb8cd6728f134d5eca3371f60f213884fdba2a4c5ff8c4e27d2f98b4ffe3552fbf0053214933854d32e12fe51b7c82ca15acc4c09dd66b81cfc73e29511776b85ceb5347b4c7b2e1e0b660cdd47ae93665f954c95b3e8fa62bc9b72dcc5a6cb31f1243b3009000aeee8c2e755c0822b568df33d97776efbae3471979503369551930a5145e0e244991b3aa8408b649c7bb20c5906a75b021ab93df74c7e59e101bd19bd240d7f445d88cda27f17edef9a3a710bc9d5089932758dbc4f8513106bceb3248f0d9e7f2e6ecaab557f7d12b17c48dc6afd68871e0228ad98a84d236c4b370220667bacec4d3da61fc2fd301ccde590449907093bbca69aebc335e58bab600948a47dc20d17e1207887193d5185bc4d873dd49a36fe364f53436f06f8
INT (big endian) : 1870656582389635319522490775681765556967033133375421817063580030728457230593569595131414277398150710605951256691851698607014346038293991115636475696890922999508248407125632913851022035568888312544660588318724416692819645970053246786214085233985018865610198082255731541614556037411568462902780963401259747249593241949572443995162110156272474492229702893170705537632617121620053409146544673453962485701871570816327976160510980709914322953860551681934553962130725463442951958511078343731761563980410426271077921497206430520148136641602942250025980666361809922277401906583051677740925742464684134696582849741398675332021222559619095993735383708900244871501427790769116964093831442766422704600286955989703255467385667324051816825678500364199592213660232549494940656315913289471193657150966190096392560117749636861246366524938199506669220698738729864231613015979805819538364722998690859404055290427668556077514632294070025157987587482664205390223677703558173312591277536453835019988033658697837804743300350491703518799745274195488115845961085516710580956246073099970177631140239688387784226734851541596141888949854089135954307535850320246064797940874210909258994651054665773084165308581469099061612356900397340528332812699520927480
INT (little endian) : 60311214428878565102247812539787501070204913583090576392691487440133176758070697462553257120757916862788771663389293946023248316596602127569564871367850224400480145908833613415562359788656099076882601146441452839440406130694595083218010338472872462208718771323238265431591733445464121900940657860541500842934964039058348885352372365419275069041165169914640676678457661016112443646301311198122284979559358676380966968491040340224467076366541748686430950939927727229461631730868870879407728819518903691147508525524607642140876984672780509701802925869138922403130238785391815466604220553459218336275202437703929210056251070112660764637928200231328942469621961328354604395450771796521342909002021606408862443406105136900854293735690233705992277215524875922754633289337601248133511007584342943394261373823449663870680927969805986151860089822822571293823122333051665636122250254142140233507051337199145914402980093605113126528220427337206158268694367489749068337092563191005611159355315897398859695890673715568835537739460686252198016834074160891415546998385389599384176358498540712726618967735318519600227864998048769117592865201468904434005028798787851821836940014086518833034263652725441814122602993646949441498014268405766664455
STR : b"\x07\xb1c\xc0\xbff\xd2\x8ag\xc8\x8d\xb5E\x0f\x12\xa5\xfd\xff\xdfDQK\xd6\xf2\xfeB\xf0P\x07\xbc\x85\n\xc3\xe2n~\xb5\xf7p[\x06S\xfe\xe5\x02\xdd4\x97\x11F~yF\xd5\x80\xdb \xca[%W\x8f\xd2\xe8pn\xd7?\x15\xea\xe2\x14~\x98\xb0\xb7\x7f\x7f\xaf\xb9\xdb<\x0eI\xec\xef\x94\xf8\xbf\xc1\xa6\xc2\xae\x03N\xe0|]\x9c\x97\x0e\xb4Uf\xc0\xb6\xc3\xa1M9\xb8\x1bk\xf0B\xa6\n\xb3\x868w\x96\xb0\xa8R\x81[,Y\x0c#<\xa1\x15\x8e\xf0q6\xbd\xed\n?\xda\xc9Z\x900=\xf9GT\x1d\xd0Jz\x07\xeaRQ\xc9\xc1F\x9dpT%-e\xbd{\x89<M\x0c\xb4,j\x8d\xc1\x02h0\xb5\x019\xdfr\xcf\xa0\x138p\xa8\xd4\xd2\x9b3\xf5\xb8)-\xd8i\xa8\xf9\x8c%\x8b\x97k\x9d\xba?x\x9bJ\xaf\xbf\x82}\xbd\xb8\xcdg(\xf14\xd5\xec\xa37\x1f`\xf2\x13\x88O\xdb\xa2\xa4\xc5\xff\x8cN'\xd2\xf9\x8bO\xfe5R\xfb\xf0\x052\x14\x938T\xd3.\x12\xfeQ\xb7\xc8,\xa1Z\xccL\t\xddf\xb8\x1c\xfcs\xe2\x95\x11wk\x85\xce\xb54{L{.\x1e\x0bf\x0c\xddG\xae\x93f_\x95L\x95\xb3\xe8\xfab\xbc\x9br\xdc\xc5\xa6\xcb1\xf1$;0\t\x00\n\xee\xe8\xc2\xe7U\xc0\x82+V\x8d\xf3=\x97wn\xfb\xae4q\x97\x95\x036\x95Q\x93\nQE\xe0\xe2D\x99\x1b:\xa8@\x8bd\x9c{\xb2\x0cY\x06\xa7[\x02\x1a\xb9=\xf7L~Y\xe1\x01\xbd\x19\xbd$\r\x7fD]\x88\xcd\xa2\x7f\x17\xed\xef\x9a:q\x0b\xc9\xd5\x08\x992u\x8d\xbcO\x85\x13\x10k\xce\xb3$\x8f\r\x9e\x7f.n\xca\xabU\x7f}\x12\xb1|H\xdcj\xfdh\x87\x1e\x02(\xad\x98\xa8M#lK7\x02 f{\xac\xecM=\xa6\x1f\xc2\xfd0\x1c\xcd\xe5\x90D\x99\x07\t;\xbc\xa6\x9a\xeb\xc35\xe5\x8b\xab`\tH\xa4}\xc2\r\x17\xe1 x\x87\x19=Q\x85\xbcM\x87=\xd4\x9a6\xfe6OSCo\x06\xf8"
```

Solved by looking at the factorization of n on [factordb](http://factordb.com/index.php?query=5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877). Copied all the numbers into my script and obtained flag:

```python=
from Crypto.Util.number import inverse

n=5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877
c=3832859959626457027225709485375429656323178255126603075378663780948519393653566439532625900633433079271626752658882846798954519528892785678004898021308530304423348642816494504358742617536632005629162742485616912893249757928177819654147103963601401967984760746606313579479677305115496544265504651189209247851288266375913337224758155404252271964193376588771249685826128994580590505359435624950249807274946356672459398383788496965366601700031989073183091240557732312196619073008044278694422846488276936308964833729880247375177623028647353720525241938501891398515151145843765402243620785039625653437188509517271172952425644502621053148500664229099057389473617140142440892790010206026311228529465208203622927292280981837484316872937109663262395217006401614037278579063175500228717845448302693565927904414274956989419660185597039288048513697701561336476305496225188756278588808894723873597304279725821713301598203214138796642705887647813388102769640891356064278925539661743499697835930523006188666242622981619269625586780392541257657243483709067962183896469871277059132186393541650668579736405549322908665664807483683884964791989381083279779609467287234180135259393984011170607244611693425554675508988981095977187966503676074747171
e=65537
# Factors of n
k="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"

phy=1
k=k.split(" ")
for i in k:
    phy*=int(i)-1

def get_RSA_flag(c,n,e,z):
    d = inverse(e,z)
    m = pow(c,d,n)
    return bytes.fromhex(format(m,'x')).decode('utf-8')

print(get_RSA_flag(c,n,e,phy))
```

`flag{t0000_m4nyyyy_pr1m355555}`