# TokyoWesterns CTF 4th 2018: Crypto - Revolutional Secure Angou

Posted on 04 Sep 2018, 08:23 in WriteUps

## Challenge description

The challenge was called **Revolutional Secure Angou**. A
zip
file was given to us. Inside we could find three file: an
RSA public key `publickey.pem`

(PEM formatted), the encrypted flag
`flag.encrypted`

and the `ruby`

script called `generator.rb`

used to
generate both the public key and the ciphertext. Our goal is obvious: decrypt
the file `flag.encrypted`

.

The source code of `generator.rb`

is quite simple:

1 2 3 4 5 6 7 8 9 10 11 12 13 | ```
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
``` |

As we can see line 6, `q`

is generated in a very peculiar way: it is set
to be the inverse of `e`

modulo `p`

. Line 7 ensures that `q`

is prime
in order to avoid a trivial factorisation. The rest of the script just encrypts
the flag and write the publickey.

This challenge is just another RSA-based challenge where the vulnerability is in the prime numbers generation.

## Solution

My approach when I need to face those RSA-based challenge is to write down the informations that I have as equations. Here we know:

- The public modulus \(n = p.q\);
- The public exponent \(e = 65537\);

We don't know the value of either \(p\) or \(q\) but we know that \(q = e^{-1} \mod p\), thus \(qe = 1\mod p\). We can also express this congruence as: \(\exists k, qe = kp + 1\). Since \(q\) is roughly the same size as \(p\), then \(k\) must be approximatly the same size as \(e\). Hence, even if we don't know the exact value of \(k\), it will be easy to brute-force if we have a correct criterion to validate its value.

Since \(qe = kp + 1\), then \(qep = ne = kp^2 + p\). Thus, \(p\) is a positive integer
root of the polynomial \(kX^2 + X - ne\). As a first step, and because we don't
know the value of all the coefficients of this polynomial, we use this property,
along with the standard method of resolution of a 2^{nd} degree polynomial,
to find \(k\) which is such that:

- \(\Delta = 1 + 4kne\) is a perfect square;
- \(2k\) is dividing \(\sqrt{\Delta} - 1\).

Once such a \(k\) is found, then we can compute \(p = \frac{\sqrt{\Delta} - 1}{2k}\). The modulus being factorised, we can compute the associated private key and decrypt the flag.

Here is the `python`

script used to solve the challenge:

## Python source code

```
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives.asymmetric.padding import PKCS1v15
import math
def isqrt(n):
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
with open("publickey.pem", "rb") as key_file:
pubkey = serialization.load_pem_public_key(
key_file.read(),
backend=default_backend())
e = pubkey.public_numbers().e
n = pubkey.public_numbers().n
for k in range(1, e):
delta = 1 + 4*k*n*e
sqr = isqrt(delta)
if not sqr*sqr == delta:
continue
if (sqr - 1)%(2*k) == 0:
p = (sqr - 1)//(2*k)
q = n//p
assert p*q == n
print("Factorisation found!")
break
d = modinv(e, (p-1)*(q-1))
iqmp = rsa.rsa_crt_iqmp(p, q)
dmp1 = rsa.rsa_crt_dmp1(d, p)
dmq1 = rsa.rsa_crt_dmq1(d, q)
public_numbers = rsa.RSAPublicNumbers(e, n)
private_numbers = rsa.RSAPrivateNumbers(p, q, d, dmp1, dmq1, iqmp,
public_numbers)
privkey = private_numbers.private_key(default_backend())
with open("flag.encrypted", "rb") as cipher:
print("Flag: {}".format(privkey.decrypt(cipher.read(),
PKCS1v15()).decode()))
```