### Not Your Average RSA - 100 points (65 solves)
>  Somebody told me this RSA factoring is MP complete... or was it NP?
For this RSA problem, we are only given the modulus and the ciphertext as follows:
```c: 9074407119435549226216306717104313210750146895081726439798095976354600576814818348656600684713830051655944443364224597709641982342039946659987121376590618828822446965847273448794324003758131816407702456966504389655568712152599077538994030379567217702587542326383955580601916478060973206347266442527564009737910n: 18086135173395641986123054725350673124644081001065528104355398467069161310728333370888782472390469310073117314933010148415971838393130403883412870626619053053672200815153337045022984003065791405742151350233540671714100052962945261324862393058079670757430356345222006961306738393548705354069502196752913415352527```
First thing I did was to insert the modulus into factordb to see if it could be easily factored but, the database didn't have all the factors. So, next thing I did was to run yafu on the modulus and voilá:
```# Factored with yafup1 = 27289543p2 = 27409927p3 = 33322589p4 = 17730961p5 = 27138691p6 = 22576643p7 = 27606707p8 = 21647243p9 = 18313601p10 = 23554169p11 = 24525821p12 = 31703933p13 = 25671797p14 = 24996157p15 = 27739163p16 = 20013121p17 = 17673199p18 = 29488469p19 = 30580789p20 = 21321539p21 = 31881917p22 = 25808239p23 = 22685197p24 = 30342329p25 = 24946057p26 = 16904777p27 = 18646361p28 = 19459483p29 = 31696261p30 = 22050221p31 = 20010041p32 = 25963459p33 = 20197313p34 = 21891889p35 = 33098557p36 = 31737131p37 = 29511773p38 = 28863719p39 = 20390129p40 = 17901463p41 = 18145913p42 = 33381329```
What I didn't expect was to see so many primes. Multiple prime RSA can decrypt messsages using the Chinese Remainder Theorem as explained in this StackOverflow [question](https://crypto.stackexchange.com/questions/31109/rsa-enc-decryption-with-multiple-prime-modulus-using-crt). To solve this problem, I simple implemented the solution given by the top answer:
```python# 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")```
Running the above script we get the flag:
```timctf{mUlt1_PriM3_rS4_c0ULD_B3_DAngEr0us}```