A linear congruential generator (LCG) is a deterministic pseudorandom number generator that updates its state with Xₙ₊₁ = (aXₙ + c) mod m. The seed determines the entire output stream, so identical seeds produce identical values. section 2.2.2
Equation 2.3
\[X_{n+1} = \left( a X_n + c \right)\bmod m \label{equation:lcg}\]Use the recurrence to follow each state transition; m is the modulus, a the multiplier, c the increment, and X₀ the seed. section 2.2.2
An LCG is useful for understanding PRNG state and implementation, but it is not suitable for security-sensitive applications. Its state and output are effectively the same, making future values predictable when the parameters or state are recovered. section 2.3
A practical implementation and attack proceed as follows:
- Store the multiplier, increment, modulus, and current value; update the current value with the recurrence and return the previous value. section 2.2.2
- Validate the implementation against C++ minstd_rand using multiplier 48271, increment 0, modulus 2³¹ − 1, and seed 42. section 2.2.2
- Recover the increment from two outputs when the modulus and multiplier are known, then recover the multiplier using modular inversion. section 2.2.2
- Recover the modulus from differences and greatest common divisors, then construct a clone that predicts subsequent outputs. section 2.2.2
Cloning an LCG
A clone can recover parameters from observed outputs, initialize a second generator, and match the original for 100 subsequent values. This demonstrates why an LCG must not protect cryptographic secrets or security decisions. section 2.2.2 section 2.3
