PCG

Challenge

A polynomial congruential generator leaks enough outputs to recover coefficients over a finite field.

Solution

Key solve code:

from sage.all import *

p = remote("localhost", 1337)
vals = []
m = int(p.recvline())
SIZE = 256
for _ in range(SIZE * 3):
	vals.append(int(p.recvline()))

F = GF(m)
A = Matrix(F, [[x ** (SIZE - 1 - i) for i in range(SIZE)] for x in vals[:-1]])
y = vector(F, vals[1:])
arr = A.solve_right(y)
coeff = [int(x) for x in arr]

pcg.x = vals[-1]
pcg.coeff = coeff
for _ in range(SIZE // 2):
	p.sendline(str(pcg()).encode())
p.interactive()

Flag

gigem{p0lyn0m1al5_4r3_funny}