Rating: 4.0

## BreakMe - 500

Description

`I encrypted important information and lost my private key! Can you help me to recover the content of the file?`

Moreover, we have two files

* `encrypted.txt` the encrypted text we have to decrypt

* `public.pem` the public key

```

-----BEGIN PUBLIC KEY-----

MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAL5fZwx838wL00ES071xIp/T5EblMb81

FgNsElgzb2xRAgMBAAE=

-----END PUBLIC KEY-----

```

#### Solution

The goal is to decrypt the encrypted text, that probably contains the flag. The first thing I notice is that the public key is very short, and this could be the vulnerability to exploit. As a first attempt, I suppose that the message was encrypted with the RSA algorithm. As we know the encryption in RSA requires the public key which means `modulus N` and a public exponent `e`. Let’s extract `public.pem` file to find modulus *N* and *e*.

```shell

$ openssl rsa -noout -text -inform PEM -in public.pem -pubin

RSA Public-Key: (256 bit)

Modulus:

00:be:5f:67:0c:7c:df:cc:0b:d3:41:12:d3:bd:71:

22:9f:d3:e4:46:e5:31:bf:35:16:03:6c:12:58:33:

6f:6c:51

Exponent: 65537 (0x10001)

$ python3 -c 'print(int("00be5f670c7cdfcc0bd34112d3bd71229fd3e446e531bf3516036c1258336f6c51", 16))'

86108002918518428671680621078381724386896258624262971787023054651438740237393

```

This result tell us that:

* `N = 86108002918518428671680621078381724386896258624262971787023054651438740237393`

* `e = 65537`

Now the decryption in RSA requires the private key which means modulus *N* and private exponent `d`. We have *N* as shown above, and we have to calculate *d*, ie compute the inverse modular of *e* and Euler’s totient function `phi`.

**phi** is unknown because we need the prime numbers **p** and **q**. Also these prime numbers are unknown and to compute them we have to factorize N, which usually is very hard. But in this case we have a public key of 256 bit (too short) and the modulus *N* is probably factorizable.

I try to factorize *N* with this site: www.alpertron.com.ar. It took about 3 minutes to compute the result:

* `p = 286748798713412687878508722355577911069`

* `q = 300290718931931563784555212798489747397`

Now we have all we need to compute the decryption.

```python

import gmpy

from Crypto.Util.number import *

N = 86108002918518428671680621078381724386896258624262971787023054651438740237393

e = 65537

p = 286748798713412687878508722355577911069

q = 300290718931931563784555212798489747397

phi = (p - 1) * (q - 1)

d = gmpy.invert(e, phi)

c = open("encrypted.txt", "rb").read()

c = c.hex()

c = int(c, 16)

decrypted = pow(c, d, N)

print("[+] N = "+str(N))

print("[+] e = "+str(e))

print("[+] p = "+str(p))

print("[+] q = "+str(q))

print("[+] phi = "+str(phi))

print("[+] d = "+str(d))

print()

print("[+] Decrypted ciphertext and Found the message m " + str(decrypted))

print("[+] FLAG is ", end=' ')

print(long_to_bytes(decrypted))

```

This simple script gives us the flag:

```shell

$ python3 rsa_attack.py

[+] N = 86108002918518428671680621078381724386896258624262971787023054651438740237393

[+] e = 65537

[+] p = 286748798713412687878508722355577911069

[+] q = 300290718931931563784555212798489747397

[+] phi = 86108002918518428671680621078381724386309219106617627535359990716284672578928

[+] d = 52563235496868154743721179285926106867856121268586368115409795819089744895137

[+] Decrypted ciphertext and Found the message m: 3998731487633352107852441255033768239881091376738602013454220231226719498

[+] FLAG is: b'\x02Ca1\xbc\xe8\xad\x165\xe4\xfc\x00AFFCTF{PermRecord}\n'

```

* **Flag**: `AFFCTF{PermRecord}`

Original writeup (https://github.com/valecor95/Crypto_CTF_writeups/blob/master/AffinityCTF2020/BreakMe/breakme.md).