text: 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()
  Advertisements