TokyoWesterns CTF 2018

This has been an Interesting CTF, we had a lot of fun in solving these question.

Revolutional Secure Angou

This was a pretty easy question to solve and we were able to do it quickly. This is a ruby script given of how the encryption took place.

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

After examining the script we find that the Key generation is a bit weird here. The second prime is equal to the modular inverse of the public key exponent e to the first prime p ,

\begin{align} q & = e ^ {-1} \bmod p \newline eq & = 1 \bmod p \newline eq & = 1 + kp \newline p & = ((eq) - 1) * k \newline \end{align}

we know that , $ n = p * q$ substituting p in this equation, $ q*((e * q) - 1)/k = n$ simplifying the equation, $ eq ^ 2 - q - kn =0 $

Now this becomes a simple linear equation which can be simplified to get q . After getting q, a matter of time before you could just decrypt it. Here is the python code I used to solve this challenge.

from Crypto.PublicKey import RSA
import gmpy2


ct = bytes_to_long(open('flag.encrypted').read())

f = open('publickey.pem').read()
n = RSA.importKey(f).n
e = RSA.importKey(f).e
i = 0

while(True):
	if GCD(n,gmpy2.iroot(1+(4*e*n*i),2)[0])!=1:
		q = GCD(n,gmpy2.iroot(1+(4*e*n*i),2)[0])
		break
	i=i+1
p = n / q

phin = (p-1)*(q-1)
d = inverse(e,phin)
print long_to_bytes(pow(ct,d,n))

TWCTF{9c10a83c122a9adfe6586f498655016d3267f195}