QCG

Challenge

Recover parameters of a quadratic congruential generator from outputs, then predict future values.

Solution

Key solve code:

from math import gcd

p = remote("localhost", 1337)
x = [int(p.recvline().decode()) for _ in range(10)]

# Build elimination expressions to recover m, then c, b, a
# (y, b_y, c_y, z, c_z omitted for brevity)
gcf = m_mults[0]
for val in m_mults:
	gcf = gcd(gcf, val)
m = gcf

c = pow(c_z[index] % m, -1, m) * z[index] % m
b = pow(b_y[index] % m, -1, m) * (y[index] - c * c_y[index]) % m
a = pow(x[index] ** 2 % m, -1, m) * (x[index + 1] - b * x[index] - c) % m

qcg = QCG(m, a, b, c, x[-1])
for _ in range(5):
	p.sendline(str(qcg()).encode())

Flag

gigem{lcg_but_h4rd3r_101}