Plumstead, Joan B. “Inferring a sequence generated by a linear congruence.” Foundations of Computer Science, 1982. SFCS’08. 23rd Annual Symposium on. IEEE, 1982.

# Synopsis

Pseudo-random number generators of the form $X_{t + 1} = a X_t + b \mod m$ can be “easily” broken – i.e. $a$ and $b$ can be inferred by looking at at most $O(log_2(m))$ elements in the PRNG sequence. Inferring $m$ is a bit harder1, but all of $a$, $b$ and $m$ can be inferred with at most $O(log_2(m))$ errors where an error is a mismatch between a predicted and an actual element in the random sequence. It is assumed that the algorithm is “told” what the correct value is when it makes a mistake.

# What I Learned

Key insight for me was that an $ax+b$ PRNG is not as secure as its seed. Just by knowing (or guessing!) that the PRNG is of the form $ax+b$, an adversary can recover the seed.

1. Imagine $a = 1$ and $b = 1$ (i.e. the “random” sequence is just a monotonically increasing sequence). Then it may take a very long time for the sequence to “wrap” around $m$, and until it wraps there is no restriction on what $m$ can be.