LostKey.py

from pwn import *
from sympy import *

r = remote('18.179.251.168',21700)
r.recvline()
flag = int(r.recvline().strip(),16)

def enc(v):
  r.sendline('A')
  data = hex(v)[2:].strip('L')
  if len(data)%2 == 1: data = '0'+data
  r.sendline(data)
  r.recvuntil('cmd: input: ')
  return int(r.recvline().strip(),16)

def dec(v):
  r.sendline('B')
  data = hex(v)[2:].strip('L')
  if len(data)%2 == 1: data = '0'+data
  r.sendline(data)
  r.recvuntil('cmd: input: ')
  return int(r.recvline().strip(),16)

e2 = enc(2)
e4 = enc(4)
e8 = enc(8)
e16 = enc(16)

n = gcd(e2*e2-e4,e2*e2*e2-e8)
n = gcd(n,e4*e4-e16)
n = int(n)
print n

x = e2
step = pow(2,2**20,n)
data1 = []
tbl = {}
v = 1
for i in xrange(2**20):
  data1.append(v)
  tbl[v] = i
  v = v*2
  if v>=n: v-=n
data1 = set(data1)
inv = invert(step,n)
data2 = []
tbl2 = {}
for i in xrange(2**20):
  data2.append(x)
  tbl2[x] = i
  x = (x*inv)%n
data2 = set(data2)
midl = list(data1&data2)
mid = midl[0]
e = tbl2[mid]*(2**20)+tbl[mid]
print e

v = (-n)%256
tbl = {}
for i in xrange(256):
  z = (v*i)%256
  tbl[z] = i
upper = n
lower = 0


b = flag
step = pow(256,e,n)
for i in xrange(128):
  b = (b*step)%n
  q = dec(b)
  ii = tbl[q]
  gap = (upper-lower)/256
  lower += ii*gap
  upper = lower+gap

g = upper-upper%256+dec(flag)
print hex(g)[2:].strip('L').decode('hex')