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