Rating: 5.0
# Revolutional Secure Angou - TokyoWesterns CTF 2018
## Introduction
In this challenge we are given a file containing a RSA public key as well as the flag encrypted with that same public key.
We are also given `generator.rb`, the Ruby script used to generate the public key and encrypt the flag:
```rb
require 'openssl'
e = 65537
while true
p = OpenSSL::BN.generate_prime(1024, false)
q = OpenSSL::BN.new(e).mod_inverse(p)
next unless q.prime?
key = OpenSSL::PKey::RSA.new
key.set_key(p.to_i * q.to_i, e, nil)
File.write('publickey.pem', key.to_pem)
File.binwrite('flag.encrypted', key.public_encrypt(File.binread('flag')))
break
end
```
## RSA
[RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) is a popular public-key cryptosystem whose security relies on the difficulty of factoring the product of two large prime numbers.
In order to generate a RSA key pair one must:
* **randomly** choose two distinct prime numbers, which are typically called $p$ and $q$;
* choose a number coprime to both $p - 1$ and $q - 1$, called $e$ or *public exponent*. We can see that the script uses $e = 65537$, which is a very common value of $e$;
* find a number $d$, the *private exponent*, such that $d \equiv e^{-1} \bmod (p - 1)(q - 1)$. This means that $de \equiv 1 \bmod (p - 1)(q - 1)$
* compute $n = qp$, the *modulus*;
Once this is done, $e$ and $n$ are published as the *public key* while $d$, $p$, and $q$ are kept secret.
Encrypting a message (an integer $m$) with a public key $(n, e)$ is simply done by computing $c \equiv m^{e} \bmod n$. Anyone who knows $d$ can decrypt the message by computing $m \equiv c^{d} \bmod n$.
However if $d$ is not known, the only way of decrypting the message is to factor $n$ into $p$ and $q$ and then use them to compute $d$. Since this is extremely hard if $p$ and $q$ are very large, we can consider the cryptosystem secure.
## Cracking the code
We can already see that the script deviates from the standard procedure in that only $p$ is chosen at random. Once $p$ is chosen, $q$ is computed as $q \equiv e^{-1} \bmod p$, meaning that it completely depends from the value of $p$. The script keeps trying new values of $p$ until it finds one such that $q$ is also prime; this is because RSA won't work correctly unless $p$ and $q$ are both prime.
It turns out that we can exploit this fact to decrypt the flag without knowing $d$ or factoring $n$.
$q \equiv e^{-1} \bmod p$ means that $qe \equiv 1 \bmod p$, which in turns means that $qe = kp + 1$ for some integer $k$ (which we don't know).
So far this is not very useful, since we don't know $p$ or $q$, but if we multiply both sides of the equality by $p$, we obtain $pqe = p(kp + 1)$.
Since $pq$ is equal to $n$ and $n$ is part of the RSA public key that we have, we can now compute the left side of the equality.
All that is left now is solving a quadratic equation for $p$.
Once we have $p$ we can use it to compute $q = \frac{n}{p}$, then $d \equiv e^{-1} \bmod (p - 1)(q - 1)$ and finally decrypt the key.
Even though we don't know the value of $k$, trying all even integers starting from 2 until we find one such that the equation has a solution only takes a few seconds. We don't need to try odd integers because $pqe$ is the product of three (odd) prime numbers and so it's odd, which means that $p(kp + 1)$ is also odd. This can only be true if $kp + 1$ is odd, and so $kp$ must be even. But since $p$ is odd (no primes other than 2 are even and p is very large), $k$ must be even.
```python
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
with open ('publickey.pem', 'r') as f:
pubkey = RSA.importKey(f.read())
with open('flag.encrypted', 'r') as f:
ciphertext = bytes_to_long(f.read())
var('p')
r = None
n = pubkey.n
e = pubkey.e
k = 2
# Try all even integers until we find one such that the equation has a solution
#
# The equation is written as a polynomial so we can force Sage to only look for
# integer solutions by using eq.roots and ring=ZZ
while not r:
eq = n * e - p * (k * p + 1)
r = eq.roots(p, ring=ZZ)
k += 2
# We have p, now we can use it to compute q and d
p = r[0][0]
q = n / p
d = inverse_mod(e, (p-1) * (q-1))
# Decrypt the flag
plaintext = power_mod(ciphertext, d, n)
# Discard junk at the beginning of the plaintext
print long_to_bytes(plaintext)[-48:]
```
TWCTF{9c10a83c122a9adfe6586f498655016d3267f195}
