HITCON 2018 - Lost Key (Crypto)

lostkey.py

#-*- coding:utf-8 -*-

from sock import Sock
from libnum import invmod, n2s, s2n, gcd

f = Sock("18.179.251.168 21700")
f.read_until("flag!")
f.read_line()
ENC = int(f.read_line().strip(), 16)
print "ENC = 0x%X" % ENC

NQ = [0, 0]
def oracle_enc(x):
    NQ[0] += 1
    print "oracle enc"
    f.send_line("A")
    f.send_line(n2s(x).encode("hex"))
    f.read_until("input:")
    return int(f.read_line().strip(), 16)

def oracle_dec(y):
    NQ[1] += 1
    print "oracle dec"
    f.send_line("B")
    f.send_line(n2s(y).encode("hex"))
    f.read_until("input:")
    return int(f.read_line().strip(), 16)

n = 0
a = 2
e = oracle_enc(a)
while gcd(n, 614889782588491410) > 1:
    ee = oracle_enc(a**2)
    n = gcd(n, ee - e**2)
    e, a = ee, a**2

print n

pt8 = oracle_dec(ENC)
E28 = oracle_enc(2**8)
in8 = invmod(n % 2**8, 2**8)

t = 1
tc = 1
k = 0
itr = 0
for i in xrange(128):
    print i

    t = t * 2**8
    tc = tc * E28 % n
    k = k * 2**8

    res = oracle_dec(ENC * tc % n)
    klow = (t - k * pt8 - res) * in8 % 2**8

    k += klow

    pt = k * n / t + 1 # ceil
    print `n2s(pt)`

# hitcon{1east_4ign1f1cant_BYTE_0racle_is_m0re_pow3rfu1!}
print "Queries:", NQ