# Revolutional Secure Angou WriteUp

CTF: TWCTF 2018

CATEGORY: CRYPTO

POINTS: 154

This blog post is for discussing the exploit of the challenge Revolutional Secure Angou.

We were given the following 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)
break
end
```

When we go through the above code, we can see that the prime q is generated in a different way rather than usual.

q = OpenSSL::BN.new(e).mod_inverse(p)

On re-arranging the above line

eq = 1 + kp  where 1 < k < 65537

(eq – 1)/k = p  —  (1)

We also know that

n = pq  —  (2)

Substituting (1) in (2), we get

n = ((eq – 1)/k)q

n = (eq2 – q)/k

kn = eq2 – q      and this gives a quadratic eq in q

eq2 – q – kn = 0

We simply need to find the roots of the above quadratic to get the value of q. This factorises n and we can calculate the decryption key d to find the flag.

Total exploit script is attached below

```from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from math import sqrt
import gmpy
import sys
sys.setrecursionlimit(60000)

f = open("publickey.pem","r")
n = key.n
e = key.e

def exploit():
k = 10
while True:
Q = gmpy.mpz(1 + 4*n*k*e)
q = (1 + Q.root(2))/(2*e)
k = k + 1
if n%q == 0:
return q

with open("flag.encrypted", "rb") as f:

q = exploit()
p = n/q
phi = (p-1)*(q-1)
d = inverse(e,phi)
c = bytes_to_long(c)
m = pow(c,d,n)
print long_to_bytes(m)
```