Linear Congruential Generator

A Linear Congruential Generator (LCG) is one of the oldest and simplest pseudo-random number generators. It is fast but not cryptographically secure, so finding one in a challenge is usually a sign of a weakness.

Definition

An LCG is defined by a modulus $m$ , a multiplier $a$ , an increment $b$ and a seed $x_0$ . It produces its sequence with the recurrence:

x_{i+1} = a \cdot x_i + b \mod m

The closed form after $i$ steps is:

x_i = a^i \cdot x_0 + b \cdot \sum_{j=0}^{i-1} a^j \mod m

The generator reaches its maximal period (length $m$ ) only when $a$ , $b$ and $m$ satisfy the Hull-Dobell theorem conditions. Otherwise the period can be much shorter and the output can degenerate.

Attacks

Known or guessable parameters
The whole sequence is predictable once $a$ , $b$ and $m$ are known. A frequent mistake is deriving them from a low-entropy source, for example the current time (a = int(time.time())), which can be brute-forced over a small window. When the parameters are unknown but several consecutive outputs are available, they can also be recovered by solving the recurrence.
Degenerate state collapsing to a constant
If the radical of $m$ divides $a$ (i.e. $a$ is a multiple of the product of the distinct prime factors of $m$ ), then $a^i \equiv 0 \mod m$ for $i$ large enough. The first term of the closed form vanishes and the state becomes a constant fixed point:
$x_i = -b \cdot (a-1)^{-1} \mod m$
A stream cipher built on such a generator then reuses the same keystream block, and is broken with a single known-plaintext (for example the flag format).