pow pow

pow.sage

import random
import socket
import subprocess
import hashlib

p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
g = pow(2, 2*4759647095086827597559114855685975263112106458932414012998147177848303887783492510354911068366203455488902018600593880874117783509946030773587965941, p)

gens = [pow(g,3**(336-i),p) for i in range(336)]

s = socket.create_connection(('52.69.244.164', int(9003)))

def read_until(s, f):
    if not callable(f):
        f = lambda str, st=f: st in str
    buf = ""
    while not f(buf):
        c =  s.recv(1)
        assert c != None
        buf += c
    return buf

def solve_proof_of_work(s):
    proc = subprocess.Popen(['./a.out', s], stdout=subprocess.PIPE)
    out,_ = proc.communicate()
    res = proc.poll()
    assert proc.returncode == 0
    assert len(out) == 8
    assert out.startswith(s)
    assert hashlib.sha1(out).hexdigest()[:6] == '000000'
    return out

data = read_until(s,'zero?')
data = "".join(chr(int(x,16)) for x in data.split('begins with ')[1].split(',')[0].split(' '))
print repr(data)
proof = solve_proof_of_work(data)
s.send(proof)

def oracle(x):
    s.send(str(x) + '\n')
    res = int(read_until(s, '\n').strip())
    return res

start,digits,low = 1, [], 0
for i in range(start, 300):
    print "i=",i
    res = oracle(gens[i]) * inverse_mod(int(pow(gens[i], low, p)), p) % p
    poss = [pow(gens[i], j, p) for j in range(0, 3**i, 3**(i-1))]
    dig = poss.index(res)
    digits.append(dig)
    low += 3**(i-1) * dig
    print "start,digits,low=", i+1,",", digits,",", low

flag = 0
for d in digits[::-1]:
    flag *= 3
    flag += d

print "flag:", hex(flag)