PicoCTF19 b00tl3gRSA3

Challenge

Why use p and q when I can use more? Connect with nc 2019shell1.picoctf.com 47259.

Hints

There's more prime factors than p and q, finding d is going to be different.

Solution

c: 115907801461313158965377829999414983694947203616237913344000889317863736758531019893044675670470719016550935245498480076257808295666213250671705647052952985160750026716806648346149941402624934593771389255609760111103294960111447016315854679477953928170272549763616429741944532210423007533197499524142851496972167029509575747311697967407757038
n: 505186941595372767417204483069962456956876881699737700099184038281005218489284390560248445518556484612403558042307234530875326885844802849178814990909325938778660794800605676053790848757817436721133841429031968710360577866052273624130574100503249945336634715178677448719258396584686548296179014568446031310597909656036281488083645611195095047
e: 65537

Let's try RSACTFTool.

$ python RsaCtfTool.py -n 505186941595372767417204483069962456956876881699737700099184038281005218489284390560248445518556484612403558042307234530875326885844802849178814990909325938778660794800605676053790848757817436721133841429031968710360577866052273624130574100503249945336634715178677448719258396584686548296179014568446031310597909656036281488083645611195095047 -e 65537 --uncipher 115907801461313158965377829999414983694947203616237913344000889317863736758531019893044675670470719016550935245498480076257808295666213250671705647052952985160750026716806648346149941402624934593771389255609760111103294960111447016315854679477953928170272549763616429741944532210423007533197499524142851496972167029509575747311697967407757038
[+] Clear text : ,qDhpُQ>ML)e

I guess this tool doesn't support multi-prime RSA. So lets try to find some factors.

Integer factorization calculator

This website also gives us the totient(n)

phi = 505186940041440309962987635962658666379959200685840459741094888209162455093388423841205618560994296346081983144064357582395160227000498559919431103749690592351484252144388376192135608477301020357011256865836603207375248074893376070863434356494230539317810776913265268813717240782848195688483960936781393194407125679299624960000000000000000000

Let's just calculate this manually:

from pwn import *
from __future__ import print

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        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('modular inverse does not exist')
    else:
        return x % m

c = 115907801461313158965377829999414983694947203616237913344000889317863736758531019893044675670470719016550935245498480076257808295666213250671705647052952985160750026716806648346149941402624934593771389255609760111103294960111447016315854679477953928170272549763616429741944532210423007533197499524142851496972167029509575747311697967407757038
n = 505186941595372767417204483069962456956876881699737700099184038281005218489284390560248445518556484612403558042307234530875326885844802849178814990909325938778660794800605676053790848757817436721133841429031968710360577866052273624130574100503249945336634715178677448719258396584686548296179014568446031310597909656036281488083645611195095047
e = 65537
phi=505186940041440309962987635962658666379959200685840459741094888209162455093388423841205618560994296346081983144064357582395160227000498559919431103749690592351484252144388376192135608477301020357011256865836603207375248074893376070863434356494230539317810776913265268813717240782848195688483960936781393194407125679299624960000000000000000000    

d = modinv(e, phi) # c^d = m 
m = pow(c, d, n)
flag = unhex(hex(m)[2:])
print(flag)

Flag

picoCTF{too_many_fact0rs_3978938}