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 zipfile 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 

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 RSAbased challenge where the vulnerability is in the prime numbers generation.
Solution
My approach when I need to face those RSAbased 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 bruteforce 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, (p1)*(q1))
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()))