The more primes, the safer.. right.?.?

Solution

[[email protected] ~]$ nc 2018shell2.picoctf.com 21287
c: 1502270067540582168135490012840047782756904783068135524843993702220926366234642335641388300790529230161860702348904380389703854838421121692340684743977820940090093146787371624268771643306290208433522223202459326062352197632712062330975345887473975853048893558270722775026945177841596730374395940322055080
n: 8615949487791905788045887618656853649638047501477168782685756183712817598053380517214551996471659194122819303530311756892395008784747091777913009665860241780314180175558463394654655475363004477135518349247137100115559282966039882512227641348608967831453063299853344627510524441049132953264610748870731729
e: 65537

In this challenge, vulnerability can be not seen at first just as easily as in the previous challenges. But coming back to the basics, it’s usally a good way to start with factoring the modulus.

But in this challenge, I had to use different online factorization service as factordb gave me results that could not be used in decrypting. Still dont’t know why but another great website called alpertron factorized that number with ease.

8615 949487 791905 788045 887618 656853 649638 047501 477168 782685 756183 712817 598053 380517 214551 996471 659194 122819 303530 311756 892395 008784 747091 777913 009665 860241 780314 180175 558463 394654 655475 363004 477135 518349 247137 100115 559282 966039 882512 227641 348608 967831 453063 299853 344627 510524 441049 132953 264610 748870 731729 (304 digits) = 2303 304037 × 2317 421797 × 2320 203709 × 2342 921479 × 2426 287307 × 2645 588083 × 2675 391923 × 2681 783659 × 2708 665613 × 2775 070201 × 2791 815493 × 2848 935121 × 2877 140711 × 3017 927131 × 3058 251061 × 3181 993957 × 3194 929861 × 3364 701581 × 3443 239043 × 3464 131343 × 3469 427699 × 3570 877441 × 3592 062391 × 3593 246621 × 3674 007221 × 3781 708729 × 3902 654027 × 3914 447699 × 3986 127601 × 4067 776589 × 4216 713047 × 4289 160541

But wait, doesn’t RSA only need two primes, p and q. No, it doesn’t, you can use as many prime numbers as you want and the only thing that changes in algorithm is that you use all of these primes in calculating phi. I learned that from this post made by p4 team. Their challenge was much harder, but essentials are still there.

So what do we do now? Let’s calculate the phi.

>>> phi = (2303304037 - 1) * (2317421797 - 1) * (2320203709 - 1) * (2342921479 - 1) * (2426287307 -1) * (2645588083 - 1) * (2675391923-1) * (2681783659 - 1) * (2708665613 -1) * (2775070201-1) * (2791815493-1) * (2848935121-1) * (2877140711-1) * (3017927131-1) * (3058251061 - 1) * (3181993957-1) * (3194929861-1) * (3364701581-1) * (3443239043-1) * (3464131343-1) * (3469427699-1) * (3570877441 - 1) * (3592062391-1) * (3593246621-1) * (3674007221-1) * (3781708729-1) * (3902654027-1) * (3914447699-1) * (3986127601 - 1) * (4067776589-1) * (4216713047-1) * (4289160541-1)

Rest of the decryption is the same as in the ‘normal’ RSA.

>>> e = 65537
>>> n = 8615949487791905788045887618656853649638047501477168782685756183712817598053380517214551996471659194122819303530311756892395008784747091777913009665860241780314180175558463394654655475363004477135518349247137100115559282966039882512227641348608967831453063299853344627510524441049132953264610748870731729
>>> def egcd(a, b):
...     if a == 0:
...         return (b, 0, 1)
...     g, y, x = egcd(b%a,a)
...     return (g, x - (b//a) * y, y)
... 
>>> def modinv(a, m):
...     g, x, y = egcd(a, m)
...     if g != 1:
...         raise Exception('No modular inverse')
...     return x%m
... 
>>> d = modinv(e, phi)
>>> c = 1502270067540582168135490012840047782756904783068135524843993702220926366234642335641388300790529230161860702348904380389703854838421121692340684743977820940090093146787371624268771643306290208433522223202459326062352197632712062330975345887473975853048893558270722775026945177841596730374395940322055080
>>> plain = str(hex(pow(c, d, n)))[2::]
>>> print(''.join([chr(int(''.join(c), 16)) for c in zip(plain[0::2],plain[1::2])]))
picoCTF{p_&_q_n0_r_$_t!!_3924142}

Another RSA flag!