Super_Safe_RSA_3

Super Safe RSA 3

Cryptography - 600 points

Challenge

The more primes, the safer.. right.?.? Connect with nc 2018shell2.picoctf.com 54915.

Hint

How would you find d if there are more than 2 prime factors of n?

Solution

Get the values from the server

$ nc 2018shell2.picoctf.com 54915

c: 7455329383143038957429716815165500715158261560971896601396739132805957525166191202455760978408719432329362021224459206704248836452011818476672175430764537075040063368230228365358727043987687964871609661287101362363672847396656546249922690106513698797211955466172034302181014173372680092234399540927971670
n: 8520637787114918832237015248786294009169540917255965331119398471430390846334537463412527582570236972202263403305377799932127000612183588324716119238697948964827609505124731694163461569741661957620860552493085730019676068317580085380871714045570573263756460672395119961317987254629107413356208040537606803
e: 65537

Using YAFU took about 2 seconds to factor. We see that it consists of many primes.

>> factor(8520637787114918832237015248786294009169540917255965331119398471430390846334537463412527582570236972202263403305377799932127000612183588324716119238697948964827609505124731694163461569741661957620860552493085730019676068317580085380871714045570573263756460672395119961317987254629107413356208040537606803)
P10 = 2995933781
P10 = 3834414293
C29 = 29016696161674138919369908219
C19 = 9572493988312872677
P10 = 2165051023
C29 = 42605294858361493736155069859
P10 = 2917169771
P10 = 4105673113
P10 = 2705398837
P10 = 4136392301
P10 = 2700707419
P10 = 3734994139
P10 = 2349776251
P10 = 2625712321
P10 = 4007479051
P10 = 2636514667
P10 = 4048500331
P10 = 4012465003
P10 = 3234818243
P10 = 3639907571
P10 = 2597208121
P10 = 3435673511
P10 = 2674573939
P10 = 2960117663
P10 = 4075003727
P10 = 2758927781
P10 = 2162211553

And apparently it wasted a lot of my time but the Cxx results are not fully factored...

>> factor(29016696161674138919369908219)
P10 = 2768743379
P10 = 3827198227
P10 = 2738320643

>> factor(9572493988312872677)
P10 = 2985009899
P10 = 3206855023

>> factor(42605294858361493736155069859)
P10 = 4128749161
P10 = 3382545863
P10 = 3050713213

---

Multi-prime RSA

Reference:

• https://crypto.stackexchange.com/questions/44110/rsa-with-3-primes
• https://crypto.stackexchange.com/questions/31109/rsa-enc-decryption-with-multiple-prime-modulus-using-crt/31112#31112
• https://github.com/sonickun/ctf-crypto-writeups/blob/master/2015/security-camp/broken-rsa/solver.py
• https://crypto.stackexchange.com/questions/5382/is-it-safer-to-encrypt-twice-with-rsa

Using this formula, we can calculate phi

phi = (p-1) * (q-1) * (r-1) * ...

And then plug it into any typical RSA script to solve for d and decrypt.

Flag

$ python3 solve.py 
c = 7455329383143038957429716815165500715158261560971896601396739132805957525166191202455760978408719432329362021224459206704248836452011818476672175430764537075040063368230228365358727043987687964871609661287101362363672847396656546249922690106513698797211955466172034302181014173372680092234399540927971670
n = 8520637787114918832237015248786294009169540917255965331119398471430390846334537463412527582570236972202263403305377799932127000612183588324716119238697948964827609505124731694163461569741661957620860552493085730019676068317580085380871714045570573263756460672395119961317987254629107413356208040537606803
e = 65537
d = 5569351009401155004021134575034747412724800331071788237792455916993059969100653421690306814783304136482570904211645932870481010062507457964736086404517576097218368770802637081903944838845215362790927908559086265403376004771299754446528510566482335725137312781766327307946613560836063821291008132810473473
m = 0x7069636f4354467b705f265f715f6e305f725f245f7421215f333632303736327d
picoCTF{p_&_q_n0_r_$_t!!_3620762}