# Super Safe RSA 3 - Crypto
On this RSA challenge, we get the following:```c: 2214959746368961374343866619773680463913808855252144119575578619282028038148568609891198127966225495311682540323131579203618894145626046974546075970616339033486317429461235324910794466410074881752239541146624247745072518241741204968025293372054661473208051944193745386532992238774551013797836031291096741n: 5564465787507426784189854287795264081761345977763964262369153883931335062166838686916377911069328789715623668583315372050520387414170383621534793892389463905512682152442890656361180400315699526374103389751180954335677791471685242043876553878553597343813515063304714971565013966010693181624796612216036537e: 65537```
Here we have a larger n so multiple primes RSA is the way here. We can get all factors on [Alpertron](https://www.alpertron.com.ar/ECM.HTM) 
Then we google multiple primes RSA and create this script```pythonc = 2214959746368961374343866619773680463913808855252144119575578619282028038148568609891198127966225495311682540323131579203618894145626046974546075970616339033486317429461235324910794466410074881752239541146624247745072518241741204968025293372054661473208051944193745386532992238774551013797836031291096741
n = 5564465787507426784189854287795264081761345977763964262369153883931335062166838686916377911069328789715623668583315372050520387414170383621534793892389463905512682152442890656361180400315699526374103389751180954335677791471685242043876553878553597343813515063304714971565013966010693181624796612216036537
e = 65537
p1 = 2175350609p2 = 2182560491p3 = 2196605027p4 = 2209029391p5 = 2466547367p6 = 2510616961p7 = 2588079563p8 = 2704140821p9 = 2736762829p10 = 2796597043p11 = 2809479437p12 = 2829659713p13 = 2837556643p14 = 2858051057p15 = 3032087491p16 = 3042267581p17 = 3063304267p18 = 3102491383p19 = 3219243151p20 = 3284737447p21 = 3392021827p22 = 3789952469p23 = 3812358577p24 = 3858988619p25 = 3864352469p26 = 3877179469p27 = 3910354507p28 = 3985847791p29 = 3990903569p30 = 4041031661p31 = 4069378073p32 = 4203209281
primes = [p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, \          p14, p15, p16, p17, p18, p19, p20, p21, p22, p23, p24, p25, \          p26, p27, p28, p29, p30, p31, p32]
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
# From https://crypto.stackexchange.com/questions/31109/rsa-enc-decryption-with-multiple-prime-modulus-using-crtts = []xs = []ds = []
for i in range(len(primes)):	ds.append(modinv(e, primes[i]-1))
m = primes[0]
for i in range(1, len(primes)):	ts.append(modinv(m, primes[i]))	m = m * primes[i]
for i in range(len(primes)):	xs.append(pow((c%primes[i]), ds[i], primes[i]))
x = xs[0]m = primes[0]
for i in range(1, len(primes)):	x = x + m * ((xs[i] - x % primes[i]) * (ts[i-1] % primes[i]))	m = m * primes[i]
print hex(x%n)[2:-1].decode("hex")```
This script prints the flag: picoCTF{p_&_q_n0_r_$_t!!_6725536}