TokyoWesterns CTF 2018: Revolutional Secure Angou

solve.py

from scryptos import *

# test parameters
# p, q = 14056259838232570373, 3909938154797744143
# p, q = 110641318332500553225796279828587613489797458859835222045512182391168598134167, 41341297333205266450910162205203983690711509110268167866251160754916102829081
# p, q = 10228796114311354522393980901045139447044341433203094817361313657771454169784897994605194490320353121541462445378267256058403046516520932633258044274994937, 9674880045377912387417155013106887773980875486540327472093521385140255139488018323841292644856768684836232571892336095160722768016023003373215125021261061

rsa = RSA.import_pem(open('publickey.pem').read())
e = rsa.e
n = rsa.n

'''
eq \equiv 1 (mod p)
<=> \exists k s.t. eq = 1 + kp
 => en = epq = p + kp^2

so equation `-kx^2 - x + epq = 0` holds and its solution is `x = p`.

Moreover, we know `k` is sufficiently small from `ex + py = 1 => e \approx y` so we can get it by brute-force.
'''

k = 1
d = -1
pqe = n * e
while d == -1:
  k += 1
  d = is_perfect_square(1 + 4 * k * pqe)

print '[+] k = %d' % k

# solve as quadratic equation
g1 = gcd((1 + d) / (2 * k), n)
g2 = gcd((1 - d) / (2 * k), n)

p = max(g1, g2)

assert p != n # non trivial solution?
assert n % p == 0

print '[+] p = %d' % p
q = n / p

a, b, g = egcd(e, p)
assert a % p == q # q = e^-1 mod p => q < p

rsa = RSA(e, n, p=p, q=q)

print [long_to_bytes(rsa.decrypt_PKCS15(bytes_to_long(open('flag.encrypted', 'rb').read())))]

solve_log

Tue Sep  4 10:32:26 JST 2018 ~/ctf/2018/twctf-2018/revolutional-secure-angou 100%
> python solve.py 
[+] k = 54080
[+] p = 142727552290123521017279182847387099553980176436653156686571005621360593567236973858972940588412513104338972342496604878974964273707518226570604980944855067127507753049804700855693115963197456876865788199179854448882972688495369967044453040443306336140280352904742571391288666823388345281672776486027914172087
['TWCTF{9c10a83c122a9adfe6586f498655016d3267f195}\n']