**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 Inverse4. 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 qp and q are such that p, q !=0 and p != qWe calculate N using the formulaN = 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 = 1for 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 decryptM = hex(pow(c, d,n))0x666c61677b74303030305f6d346e797979795f7072316d3335353535357d
Removing the '0x' from the starting using slicingM = 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 % mn = 5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877c =  3832859959626457027225709485375429656323178255126603075378663780948519393653566439532625900633433079271626752658882846798954519528892785678004898021308530304423348642816494504358742617536632005629162742485616912893249757928177819654147103963601401967984760746606313579479677305115496544265504651189209247851288266375913337224758155404252271964193376588771249685826128994580590505359435624950249807274946356672459398383788496965366601700031989073183091240557732312196619073008044278694422846488276936308964833729880247375177623028647353720525241938501891398515151145843765402243620785039625653437188509517271172952425644502621053148500664229099057389473617140142440892790010206026311228529465208203622927292280981837484316872937109663262395217006401614037278579063175500228717845448302693565927904414274956989419660185597039288048513697701561336476305496225188756278588808894723873597304279725821713301598203214138796642705887647813388102769640891356064278925539661743499697835930523006188666242622981619269625586780392541257657243483709067962183896469871277059132186393541650668579736405549322908665664807483683884964791989381083279779609467287234180135259393984011170607244611693425554675508988981095977187966503676074747171e = 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 = 1for 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)