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.