# Polictf 2017 – Lucky Consecutive Guessing

This is a short snippet to solve the LCG on Polictf’17. The basic idea is to reduce the problem $aX_i + b = X_{i+1} \bmod M$ to $aX_i = X_{i+1} \bmod M$. This problem is quite easy to solve.

The basic idea is to view the problem as the latter and correct the discrepancies ($\delta = (b, ab, a^2b,\dots)$). So, for instance, if we sample

$V = \texttt{1310585136, 1634517111, 2548394614, 745784911},$

then these values contain the implicit discrepancies. By performing correction of the values (subtracting $\sum_k^i \delta_k$ from the corresponding $V_i$ we obtain a corrected value).

So, now we can use LLL to solve the simpler problem. Once a solution is found, we use the discrepancies to correct it to the case $aX_i + b = X_{i+1} \bmod M$.

import random

class LinearCongruentialGenerator:

def __init__(self, a, b, nbits):
self.a = a
self.b = b
self.nbits = nbits
self.state = random.randint(0, 1 << nbits)

def nextint(self):
self.state = ((self.a * self.state) + self.b) % (1 << self.nbits)
return self.state >> (self.nbits - 32)

def break_lcg(a,b,p,i,j,outputs):
deltas = [b % p, (a*b + b) % p, (a^2*b + a*b + b) % p, (a^3*b + a^2*b + a*b + b) % p]
Y = [((val << (i - j)) ) for val, delta in zip(outputs, deltas)]
L = matrix([
[p,    0,  0, 0 ],
[a^1, -1,  0, 0 ],
[a^2,  0, -1, 0 ],
[a^3,  0,  0, -1]
])
B = L.LLL()
Y = vector([x - y for x, y in zip(Y, deltas)])
target = vector([ round(RR(w) / p) * p - w for w in B * vector(Y) ])
states = list(B.solve_right(target))
return [x + y + z for x, y, z in zip(Y, states, deltas)]

# parameters
p = 2^85
a = 0x66e158441b6995
b = 0xb
n = 85
r = 32
sequence = [1310585136, 1634517111, 2548394614, 745784911]

# break the LCG
start_seed = break_lcg(a,b,p,n,r,sequence)

# run it to sample required values
lcg = LinearCongruentialGenerator(a, b, n)
lcg.state = start_seed[0]
for i in range(0, 104):
print lcg.nextint()