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)
    File.binwrite('flag.encrypted', key.public_encrypt(File.binread('flag')))
    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")
key = RSA.importKey(f.read())
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)[0])/(2*e)
        k = k + 1
        if n%q == 0:
            return q

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

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)

Flag: TWCTF{9c10a83c122a9adfe6586f498655016d3267f195}
 

Cheers!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s