Cryptography – 244 pts (10 solves) – Chall author: N0xi0us

Importing the PEM key file we find a very short public key, which we trivially factorise using online tools.

## Challenge

The challenge provides us a long integer as flag and a public key in a PEM file format. Ding ding ding, RSA alert!

## Solution

The public key is too short, which allows us to crack it! The PEM file contains the public parts of RSA cryptography, namely ‘n’ and ‘e’, encoded in base64. *If you do not recognise these variables it might be nice to read up a little on RSA cryptography, the encoding itself is fairly straightforward.*

```
-----BEGIN PUBLIC KEY-----
MDEwDQYJKoZIhvcNAQEBBQADIAAwHQIWAN4vdj9ZJ337BgYayd9cb2tF0QoJAwID
AQAB
-----END PUBLIC KEY-----
```

However (!), I did not realise that the PEM file format has some additional encoding elements such that you cannot simply convert the two base64 strings to integers and call it a day. I naively found

```
n = 74174491295044795964181854285195495718964397093731395961824370391827799637138867436334319587298835673227084716446
e = 65537
```

Although the ‘e’ has a commonly used value, the ‘n’ does not factor nicely into two primes… So I used a Python library to do it for me properly

```
from Crypto.PublicKey import RSA
f = open('../public.pem')
key = RSA.importKey(f.read())
print(key.n)
print(key.e)
```

which gave the public RSA elements as

```
n = 324724323060034233289551751185171379596941511493891
e = 65537
```

This time around, the ‘n’ actually factors nicely (using factordb) into the two primes

```
p = 25001545096244227516337
q = 12988170203481337861511552243
```

Using these and an Euler inverse function, I was able to derive the private key, the private RSA component ‘d’ to be

```
def eulinv(x, m):
a, b, u = 0, m, 1
while x > 0:
q = b // x # integer division
x, a, b, u = b % x, u, x, a - q * u
if b == 1:
return a % m
else:
return None
d = eulinv(key.e,(p-1)*(q-1)); print(d)
```

```
323728403366806485896597412434387317854754383435009
```

Now we are able to decrypt the provided ‘flag’ using m = pow(c, d, n). In Python

```
# Get message from encrypted flag
pow(flag,d,key.n)
# Turn integer into binary (0 added in front )
mbit = bin(26634179113006760524799996616930504110973)[2:]
# Pad with 0s in front to make sure it is in byte format
while len(mbit) % 8 != 0:
mbit = '0' + mbit
# Bytes -> ASCII
m = ''.join([chr(int(mbit[i:i+8],2)) for i in range(0,len(mbit),8)])
print(m)
```

which happily returns

```
NETON{3z_F4ct0rs}
```