**TL;DR**
1. Use the website [factordb.com](http://www.factordb.com/index.php) to calculate factors of N.
2. Using the primes calculate phi by using the formula phi *= (factors - 1)
3. Calculate d using Multiplicative Modulo Inverse
4. Use the formula M = (C ^ d) mod N

**flag{t0000_m4nyyyy_pr1m355555}**

-----

# THEORY

4K RSA was a Crypto challenge.
The name tells that **its an RSA problem**.

We get a file named **4k-rsa-public-key.txt** with the following contents:
```
n: 5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877

e: 65537

c: 3832859959626457027225709485375429656323178255126603075378663780948519393653566439532625900633433079271626752658882846798954519528892785678004898021308530304423348642816494504358742617536632005629162742485616912893249757928177819654147103963601401967984760746606313579479677305115496544265504651189209247851288266375913337224758155404252271964193376588771249685826128994580590505359435624950249807274946356672459398383788496965366601700031989073183091240557732312196619073008044278694422846488276936308964833729880247375177623028647353720525241938501891398515151145843765402243620785039625653437188509517271172952425644502621053148500664229099057389473617140142440892790010206026311228529465208203622927292280981837484316872937109663262395217006401614037278579063175500228717845448302693565927904414274956989419660185597039288048513697701561336476305496225188756278588808894723873597304279725821713301598203214138796642705887647813388102769640891356064278925539661743499697835930523006188666242622981619269625586780392541257657243483709067962183896469871277059132186393541650668579736405549322908665664807483683884964791989381083279779609467287234180135259393984011170607244611693425554675508988981095977187966503676074747171
```
By looking at the values, we can clearly see that the values are very large **4096 bits** and it seems like it is correctly implemented.

So lets start by solving it the formal way.

Wikipedia have decent information on [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation)

According to classical RSA, we need **two distinct primes** to start the process of encrpyting and decrypting.
Using the primes we calculate **N**.

```
Lets say the two primes are p and q
p and q are such that p, q !=0 and p != q
We calculate N using the formula
N = p * q
```

So the problem is we have N but dont have the primes p and q, and factorizing this large number is not feasible.

We got lucky on this one because it has small factors and **factordb** has factors of **N**

[factordb.com](http://www.factordb.com/index.php)

If we go to this website, and enter the value of N it did give us the factors (primes), which was totally unexpected considering the length N.

The output it gave was astonishing because it didnt gave us **2** but **64** factors (primes). But according to the classical RSA, we need two primes p & q.

A little research on the internet gave us that RSA can have multiple primes but it weakens the algorithm because of the fact that they can be factorized easily and hence makes the algorithm weak.

----

# SOLUTION

Lets solve the problem in classical way then:

1. Calculating phi
```
factors = ['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 i in factors:
phi = phi * (i-1)
```

2. Calculating d by using Multiplicative Modulo Inverse
```
def inverse(x, m):
a, b, u = 0, m, 1
while x > 0:
q = b // x
x, a, b, u = b % x, u, x, a - q * u
if b == 1:
return a % m

d = inverse(e, phi)
```

3. We now have everything, we can just decrypt the plaintext

Plaintext = (Ciphertext ^ d) mod N
^ is raised to the power of
```
Gives result in decimal (base 10)
M = pow(C, d, N)
706900059475106681301586714568958471062774799484906508017771377121899901

Converting it into hexadecimal (base 16) because it is easy to decrypt
M = hex(pow(c, d,n))
0x666c61677b74303030305f6d346e797979795f7072316d3335353535357d

Removing the '0x' from the starting using slicing
M = hex(pow(c, d,n))[2:]
666c61677b74303030305f6d346e797979795f7072316d3335353535357d

Decrypting M to ascii using bytes.fromhex
M = bytes.fromhex(hex(pow(c, d,n))[2:])
flag{t0000_m4nyyyy_pr1m355555}
```

The full code is given below

```
def inverse(x, m):
a, b, u = 0, m, 1
while x > 0:
q = b // x
x, a, b, u = b % x, u, x, a - q * u
if b == 1:
return a % m
n = 5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877
c = 3832859959626457027225709485375429656323178255126603075378663780948519393653566439532625900633433079271626752658882846798954519528892785678004898021308530304423348642816494504358742617536632005629162742485616912893249757928177819654147103963601401967984760746606313579479677305115496544265504651189209247851288266375913337224758155404252271964193376588771249685826128994580590505359435624950249807274946356672459398383788496965366601700031989073183091240557732312196619073008044278694422846488276936308964833729880247375177623028647353720525241938501891398515151145843765402243620785039625653437188509517271172952425644502621053148500664229099057389473617140142440892790010206026311228529465208203622927292280981837484316872937109663262395217006401614037278579063175500228717845448302693565927904414274956989419660185597039288048513697701561336476305496225188756278588808894723873597304279725821713301598203214138796642705887647813388102769640891356064278925539661743499697835930523006188666242622981619269625586780392541257657243483709067962183896469871277059132186393541650668579736405549322908665664807483683884964791989381083279779609467287234180135259393984011170607244611693425554675508988981095977187966503676074747171
e = 65537

factors = ['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 p in factors:
p = int(p)
phi *= (p - 1)

d = inverse(e, phi)
M = bytes.fromhex(hex(pow(c, d,n))[2:]).decode()
print(M)
```

```
flag{t0000_m4nyyyy_pr1m355555}
```

Also available on [my github](https://github.com/DaBaddest/CTF-Writeups/tree/master/RedPwn2020)