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)
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:

with open('flag.encrypted', 'r') as f:

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:]