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 can be “easily” broken – i.e. and can be inferred by looking at at most elements in the PRNG sequence. Inferring is a bit harder1, but all of , and can be inferred with at most 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 PRNG is not as secure as its seed. Just by knowing (or guessing!) that the PRNG is of the form , an adversary can recover the seed.

  1. Imagine and (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 , and until it wraps there is no restriction on what can be.