# Revolutional Secure Angou

## Task
This task had us receive a 3 files: a key.pem, an ecrypted flag and a ruby script. We can quickly see that this is avery crude RSA implementation using Ruby SSL' BigNum. Extracting the key gives us ```e = 65537```and a 2048-bit modulus. I quickly tried a few basic things (factordb, ROCA vuln, fermat) and relatively soon realized all this being secure, it had to be some prime-generation weakness.

## The Weakness

Taking a closer look at the ruby script:

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

We see that while p is generated randomly, q is generated based on p. More exactly, q is generated so that ```q * e % p == 1```. THis is as fishy as it gets, you should never, under any circumstance, generate primes that way.

## The Solving

From here on it's a walk in the park. Using a bit of modular arithmetic:
q * e % p = 1
(q*e) - 1 = p*j
p = ((q*e)-1)/j
where j is an integer and j < e. Now since ```n = p * q```:
n = ((q*e)-1)/j * q
n*j = e*q^2 - q
e*q^2 - q - n*j = 0
The last is just a simple quadratic equation. All we need to do now is to solve it for 0 < j < 65537, check if the solution is prime, and check if the solution is a divisor of n. On a decent i7 using sympy it takes around 10 seconds / 1000 (7000 if you parallelize), whic makes bruteforcing a very convenient way of solving this.

Original writeup (https://github.com/Gdasl/CTFs/blob/master/TokyoWesterns-2018/Revolutional%20Secure%20Angou.md).