## PicoCTF 2018 - Super Safe RSA

Dr. Xernon made the mistake of rolling his own crypto.. Can you find the bug and decrypt the message?

### Solution

```
[[email protected] ~]$ nc 2018shell2.picoctf.com 59208
c: 7030597768026774310122104133160676217061526490101791811961111564793541177307659
n: 15275860861038824209873749378641369526079415895246568701858306343944764452502111
e: 65537
```

First thing that comes to my mind in RSA challenges, especially with these variables is to try and factorize the public modulus `n`

. We can simply do that with factordb, that stores huge database of factorized numbers.

Here we can find that `n`

is a product of 2 prime numbers.

Now we know that both these numbes are our `p`

and `q`

. With that information we can easily calculate `d`

and then decrypt the ciphertext.

```
>>> p = 138873400617639818142290700050114985179
>>> q = 109998464739103330461289147649384134274509
>>> phi = (p - 1) * (q - 1)
>>> 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
...
>>> e = 65537
>>> d = modinv(e, phi)
```

As we have the `d`

, just raise the `c`

to the power of `d`

modulo `n`

.

```
>>> c = 7030597768026774310122104133160676217061526490101791811961111564793541177307659
>>> n = 15275860861038824209873749378641369526079415895246568701858306343944764452502111
>>> hex(pow(c, d, n))
'0x7069636f4354467b7573335f6c40726733725f7072316d33245f323436317d'
>>> txt = '7069636f4354467b7573335f6c40726733725f7072316d33245f323436317d'
>>> ''.join([chr(int(''.join(c), 16)) for c in zip(txt[0::2],txt[1::2])])
'picoCTF{[email protected]_pr1m3$_2461}'
```

There we have our flag!