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