This is a short snippet to solve the LCG on Polictf’17. The basic idea is to reduce the problem to . This problem is quite easy to solve.

The basic idea is to view the problem as the latter and correct the discrepancies (). So, for instance, if we sample

then these values contain the implicit discrepancies. By performing correction of the values (subtracting from the corresponding 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 .

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()