Modern cryptoRuns locallyNo account

Linear congruential generator predictor

Recover the modulus, multiplier, and increment of an LCG from a handful of consecutive outputs, then predict every future value.

Open in ctfpal

An LCG produces s[n+1] = (a * s[n] + c) mod m. Three unknowns, and each output is an equation - so with enough consecutive outputs the parameters are recoverable by arithmetic alone, even when none of a, c, or m were disclosed.

Recovering the parameters in order

Modulus first. Build differences t[n] = s[n+1] - s[n]. Then t[n+2]*t[n] - t[n+1]^2 is a multiple of m for every n. The GCD of several such values is m (or a small multiple of it).
Multiplier next. With m known, a = (s[2] - s[1]) * inverse(s[1] - s[0], m) mod m.
Increment last. c = (s[1] - a * s[0]) mod m.

Six consecutive outputs is comfortably enough. Fewer will do when some parameters are already known - and challenges often disclose m as a familiar constant like 2**32 or 2**48, which removes the hardest step.