import string
import hashlib
import itertools
from pwn import *

conn = remote("167.71.62.250", "23549")

def proof():
	conn.recvuntil("such that ")
	hashfunc = conn.recvuntil("(X)").replace(b"(X)", b"").decode()
	conn.recvuntil(" = ")
	tailhash = conn.recvuntil("\n").strip(b"\n").decode()

	if 'md5' == hashfunc: func = hashlib.md5 
	elif 'sha1' == hashfunc: func = hashlib.sha1
	elif 'sha224' == hashfunc: func = hashlib.sha224
	elif 'sha256' == hashfunc: func = hashlib.sha256
	elif 'sha384' == hashfunc: func = hashlib.sha384
	elif 'sha512' == hashfunc: func = hashlib.sha512

	for length in range(1, 10):
		for x in itertools.product(string.digits + string.ascii_lowercase + string.ascii_uppercase, repeat=length):
			h = func(''.join(x).encode()).hexdigest()
			if h[-6:] == tailhash:
				conn.sendline(''.join(x))
				return

# *********************************************************************************
# | hey! I have developed an efficient pseudorandom function, PRF, but it needs   |
# | deep tests for security points!! Try hard to break this PRF and get the flag! |
# | In each step I will compute the f_a(n), f_a(n + 1), f_a(n + 2), f_a(n+3), and |
# | f_a(n + 4) for secret verctor a, and for your given positive number 0 < n < p |
# *********************************************************************************
# | for n = 204366076522761421740344309052550160766, and with these PRF parameters: 
# | (p, g) = (0x99f9bfeb9e24d0d67f9835ec76463e6d, 0x27764cb821cfd40be6d2bcc154c68267) 
# | the five consecutive random numbers generated by our secure PRF are: 
# | f_a(n + 0) = 24227912477635704600552330979591220694
# | f_a(n + 1) = 155755022996680125162331709638821052763
# | f_a(n + 2) = 145613352150928625123608084077187500519
# | f_a(n + 3) = 183631895347248003527563950301181110442
# | f_a(n + 4) = 52454138916494863185011143716008002151 
# | Options: 
# |    [G]uess next number! 
# |    [P]RF function 
# |    [N]ew numbers
# |    [Q]uit

def gg(tup, a, x):
    (_, p, g), n = tup, len(a)
    assert len(bin(x)[2:]) <= n
    X = bin(x)[2:].zfill(n)
    f_ax = g
    for i in range(1, n):
        f_ax *= pow(g, a[i] * int(X[i]), p)
    return f_ax % p

from sympy import invert

def new(n):
	conn.recvuntil("[Q]uit")
	conn.sendline("N")
	conn.recvuntil("[N]o")
	conn.sendline("Y")
	conn.recvuntil("n: ")
	conn.sendline(str(n))
	conn.recvuntil("f_a(n + 0) = ")
	f0 = int(conn.recvuntil("\n").strip(b"\n").decode())
	conn.recvuntil("f_a(n + 1) = ")
	f1 = int(conn.recvuntil("\n").strip(b"\n").decode())
	conn.recvuntil("f_a(n + 4) = ")
	f4 = int(conn.recvuntil("\n").strip(b"\n").decode())
	return f0, f1, f4

if __name__ == '__main__':
	proof()

	# n = (1 << 128) - 3
	# conn.recvuntil("for n = ")
	# n = int(conn.recvuntil(",").strip(b",").decode())
	conn.recvuntil("= (")
	p = int(conn.recvuntil(",").strip(b",").strip(b"0x").decode(), 16)

	# binary = bin(n)[2:].zfill(128)
	# p1 = new(int(binary[:32], 2) * 2 ** 96)
	# p2 = new(int(binary[32:], 2))
	p0, p1, _ = new((1 << 128) - 6)
	_, _ , p4 = new(int("10" * 64, 2) - 4)
	# new(n - 5)
	conn.recvuntil("[Q]uit")
	conn.sendline("G")
	conn.recvuntil(": ")
	conn.sendline(str(p4 * p1 * int(invert(p0, p)) % p))

	conn.interactive()