Tags: crypto rsa
Rating:
# 4k-rsa
**Category:** Crypto
**Points:** 389
**Description:**
> Only n00bz use 2048-bit RSA. True gamers use keys that are at least 4k bits
long, no matter how many primes it takes...
>
> **Author:** Boolean
>
> **Given:** 4k-rsa-public-key.txt
## Writeup
Opening up the attachment given, we see we have a modulus **(n)**, public exponent
**(e)**, and a ciphertext **(c)**.
```
n: 5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877
e: 65537
c: 3832859959626457027225709485375429656323178255126603075378663780948519393653566439532625900633433079271626752658882846798954519528892785678004898021308530304423348642816494504358742617536632005629162742485616912893249757928177819654147103963601401967984760746606313579479677305115496544265504651189209247851288266375913337224758155404252271964193376588771249685826128994580590505359435624950249807274946356672459398383788496965366601700031989073183091240557732312196619073008044278694422846488276936308964833729880247375177623028647353720525241938501891398515151145843765402243620785039625653437188509517271172952425644502621053148500664229099057389473617140142440892790010206026311228529465208203622927292280981837484316872937109663262395217006401614037278579063175500228717845448302693565927904414274956989419660185597039288048513697701561336476305496225188756278588808894723873597304279725821713301598203214138796642705887647813388102769640891356064278925539661743499697835930523006188666242622981619269625586780392541257657243483709067962183896469871277059132186393541650668579736405549322908665664807483683884964791989381083279779609467287234180135259393984011170607244611693425554675508988981095977187966503676074747171
```
The description provides us with a decent hint here. Saying that there are
multiple primes involved probably means that **n** is made from more than just
**p** and **q**!
There is a really nice website for factoring large **n** values. The website is
called **FactorDB** and they have a python module for the website as well.
Plugging our **n** in the website gives us a lot of primes, but the important
thing here is that it is fully factored!
```
Result:
status (?) digits number
FF 1225 (show) 5028492424...77<1225> =
9353689450544968301<19> · 9431486459129385713<19> · 9563871376496945939<19> · 9734621099746950389<19> · 9736426554597289187<19> · 10035211751896066517<20> · 10040518276351167659<20> · 10181432127731860643<20> · 10207091564737615283<20> · 10435329529687076341<20> · 10498390163702844413<20> · 10795203922067072869<20> · 11172074163972443279<20> · 11177660664692929397<20> · 11485099149552071347<20> · 11616532426455948319<20> · 11964233629849590781<20> · 11992188644420662609<20> · 12084363952563914161<20> · 12264277362666379411<20> · 12284357139600907033<20> · 12726850839407946047<20> · 13115347801685269351<20> · 13330028326583914849<20> · 13447718068162387333<20> · 13554661643603143669<20> · 13558122110214876367<20> · 13579057804448354623<20> · 13716062103239551021<20> · 13789440402687036193<20> · 13856162412093479449<20> · 13857614679626144761<20> · 14296909550165083981<20> · 14302754311314161101<20> · 14636284106789671351<20> · 14764546515788021591<20> · 14893589315557698913<20> · 15067220807972526163<20> · 15241351646164982941<20> · 15407706505172751449<20> · 15524931816063806341<20> · 15525253577632484267<20> · 15549005882626828981<20> · 15687871802768704433<20> · 15720375559558820789<20> · 15734713257994215871<20> · 15742065469952258753<20> · 15861836139507191959<20> · 16136191597900016651<20> · 16154675571631982029<20> · 16175693991682950929<20> · 16418126406213832189<20> · 16568399117655835211<20> · 16618761350345493811<20> · 16663643217910267123<20> · 16750888032920189263<20> · 16796967566363355967<20> · 16842398522466619901<20> · 17472599467110501143<20> · 17616950931512191043<20> · 17825248785173311981<20> · 18268960885156297373<20> · 18311624754015021467<20> · 18415126952549973977<20>
```
This is easy from here on out. In order
to find our private exponent **(d)**, we need to find **phi**, which is the
product of (every prime - 1). After finding phi, we can take the modular
multiplicative inverse of **e** and **phi** to find **d**.
*Note: I didn't feel like copying the 60-something primes into my script so I
used the python module for FactorDB :)*
**Script:**
```
import gmpy
from pwn import *
from Crypto.Util.number import long_to_bytes
import binascii
from factordb.factordb import FactorDB
n = int(open("n", "r").read())
c = int(open("c", "r").read())
e = 65537
f = FactorDB(n)
f.connect()
arr = f.get_factor_list()
phi = 1
for a in arr:
phi *= (a-1)
d = gmpy.invert(e, phi)
flag = long_to_bytes(pow(c,d,n)).decode()
log.success("Flag: {}".format(flag))
```
**Output:**
```
$ python3 4k_rsa.py
[+] Flag: flag{t0000_m4nyyyy_pr1m355555}
```
## Flag
flag{t0000_m4nyyyy_pr1m355555}
## Resources
[FactorDB](http://factordb.com/index.php)
[RSA Info](https://en.wikipedia.org/wiki/RSA_(cryptosystem))
