[TokyoWesterns CTF 4th 2018] Revolutional Secure Angou

flag.enc, key.pub, generator가 주어진다.

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

ruby 언어이다. 해석하자면, p는 1024bit 소수이며, q는 inverse(e, p)이며 소수여야한다.

$ openssl rsa -pubin -inform PEM -text -noout -in key.pub

Exploit Code

from Crypto.Util.number import *
from gmpy2 import *

n = 0x8529063ea0ad3b46296f92f72356772ea4e703f7b79220c18de1b7e3ca0a7728d19e69dc48b8685cd604f5887a4f8f3a945a1ca1593cf086d348ec4dc92142083fc9e2203c6530311ee510be50a42aee4a63e7fa66bfce3512fc2fb117402a55cdf0897770c1bb86f2d9306da5b899d294edbcb17ad87e17592ccc3f62b1305724181732ac7474cf23beb722833373ef07b6a92188cf28bcfef26b2368ada38f7f4fd8921dbe3b6488e4b92028ffbd46ae26d8b43c9a86dbbc63f0b51398bb54098ff7004b646afb42f24354ab6a2d30efeee8b333473abe1cc92eb68a465819d9e9a0ff58feaf2c722ae65b7cedc9e30be915029d69342523b981ad8395cdf7
e = 65537

for k in range(1, e):
    s = 1+4*k*n*e
    if not is_square(s):
        continue

    A = -1+int(isqrt(s))
    B = 2*k
    if not A % B == 0:
        continue

    p = A // B
    q = n // p
    break

if p*q != n:
    print "ERROR"
    exit(0)

phi = (p-1)*(q-1)
d = inverse(e, phi)

flag = open('flag.encrypted', 'r').read()
flag = bytes_to_long(flag)
flag = pow(flag, d, n)
print long_to_bytes(flag)

Capture the Flag

---