> For the complete documentation index, see [llms.txt](https://maurvan.gitbook.io/ctf-writeups/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maurvan.gitbook.io/ctf-writeups/bluehens-ctf-2024/index/intro-to-rsa.md).

# Intro to RSA

## Challenge

```py
In [9]: p = getPrime(128)
In [10]: q = getPrime(128)
In [11]: N = p*q
In [12]: bytes_to_long(flag) < N
Out[12]: True
In [13]: print(pow(bytes_to_long(flag), 65537, N), N)
9015202564552492364962954854291908723653545972440223723318311631007329746475 51328431690246050000196200646927542588629192646276628974445855970986472407007
```

## Solution

First, we need to find out the values of p and q. You could try making a small Python script for this, using SymPy's factorint for example. But considering N is such a huge number, it will take some time to run (at least it did for me). So I tried to find an online calculator and ended up once again, on [dCode](https://www.dcode.fr/prime-factors-decomposition).

<figure><img src="https://1102212211-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fa46Jmz9dIuFnWcXn3ooO%2Fuploads%2FkVJbRwt0ti0iWf8PcBJV%2Fp_q.PNG?alt=media&amp;token=3fab6cb1-931d-4d3f-8ec7-da062fc881c3" alt=""><figcaption></figcaption></figure>

Now that we know p and q, we can calculate phi and also d. And then we can decrypt the message !

<figure><img src="https://1102212211-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fa46Jmz9dIuFnWcXn3ooO%2Fuploads%2FS9KlYqvpkp6EQuKy2V7s%2Fflag_rsa.PNG?alt=media&amp;token=d3ce3822-5036-4c29-a97c-3c8df0fc839d" alt=""><figcaption></figcaption></figure>

This is what my Python code looks like:

```python
p = 186574907923363749257839451561965615541
q = 275108975057510790219027682719040831427
N = 51328431690246050000196200646927542588629192646276628974445855970986472407007
ciphertext = 9015202564552492364962954854291908723653545972440223723318311631007329746475

phi_N = (p - 1) * (q - 1)
d = pow(65537, -1, phi_N)
decrypted_message = pow(ciphertext, d, N)
flag_bytes = decrypted_message.to_bytes(50, byteorder='big')

print(flag_bytes.decode())
```