Sign up ×
Information Security Stack Exchange is a question and answer site for information security professionals. It's 100% free, no registration required.

I was recently listening to the security now podcast, and they mentioned in passing that the linear congrunential generator (LCG) is trivial to crack. I use the LCG in a first year stats computing class and thought that cracking it would make a nice "extra" problem.

Are there any nice ways of cracking the LCG that doesn't involve brute force?

I'm not sure if this question is OT, but I wasn't sure where else to post the question. Also, my tags aren't very helpful since I don't have enough rep to create new tags.

share|improve this question
I think your question does fit here. I think your question may have a better chance of being answered at Cross-posting is generally frowned upon, but I'd encourage ignoring that convention in this particular case. I don't think anybody will bark at you. –  Jeff Ferland Jun 2 '11 at 13:47
@jeff I'm sure there are experts on this one here also, and this site focuses on the right mindset for the question. Note also that wikipedia notes "If a linear congruential generator is seeded with a character and then iterated once, the result is a simple classical cipher called an affine cipher; this cipher is easily broken by standard frequency analysis." –  nealmcb Jun 2 '11 at 15:14

3 Answers 3

up vote 21 down vote accepted

Yes. There are extremely efficient ways to break a linear congruential generator.

A linear congruential generator is defined by sn+1 = a sn + b mod m, where m is the modulus. In its simplest form, the generator just outputs sn as the nth pseudorandom number. If m is known to the attacker and a, b are not known, then Thomas described how to break it.

If none of a, b, m are known, one can still break a linear congruential generator, by first recovering m. It is an interesting exercise to derive how to do so efficiently; it can be done. I'll show how below; don't read on if you prefer to try to figure it out for yourself.

To recover m, define tn = sn+1 - sn and un = |tn+2 tn - t2n+1|; then with high probability you will have m = gcd(u1, u2, ..., u10). 10 here is arbitrary; if you make it k, then the probability that this fails is exponentially small in k. I can share a pointer to why this works, if anyone is interested.

The important lesson is that the linear congruential generator is irredeemably insecure and completely unsuitable for cryptographic use.

Added: @AviD will hate me even more :), but here's the math for why this works, for those who requested it.

The key idea: tn+1 = sn+1 - sn = (a sn - b) - (a sn-1 - b) = a sn - a sn-1 = a tn mod m, and tn+2 = a2 tn mod m, and tn+3 = a3 tn mod m. Therefore tn+2 tn - tn+12 = 0 mod m, i.e., |tn+2 tn - tn+12| is a random multiple of m. Nifty number theory fact: the gcd of two random multiples of m will be m with probability 6/π2 = 0.61; and if you take the gcd of k of them, this probability gets very close to 1 (exponentially fast in k). Is that cool, or what?

share|improve this answer
Also, a linear congruential generator is often bad at producing statistically good randomness. If m is even, a and b are odd, then the least significant bits of the successive values of s follow the very non-random pattern 010101010101... –  Thomas Pornin Jun 3 '11 at 15:35
aaagghh, too much math! +1, anyway... ;) –  AviD Jun 6 '11 at 22:44
@csgillespie, OK, I added the math. @AviD, avert your eyes! :) –  D.W. Jun 7 '11 at 19:19

A linear congruential generator is linear, which should say it all.

Namely, you have a state s, which is updated with: s ← as + b mod w, for two constants a and b, and a convenient modulus w (typically 232: s, a and b are 32-bit words); the output consists in the successive values of s. If you have three successive outputs (s0, s1 and s2), then you get two linear equations in two unknowns (a and b), which are easily solved with elementary arithmetics.

This can be extended to variants where you only get parts of the values s, possibly not consecutive. If a and b are two 32-bit constants, you only need about 96 bits worth of output to recompute the constants.

share|improve this answer

Another method of solving for m comes from this paper.

Essentially, this method exploits the fact that the linear congruential generator dramatically fails the planes test. The determinant of a 3x3 matrix using 4 outputs is a multiple of m.

The gcd of two multiples (n_1 and n_2 of m is m if x_1 = n_1/m and x_2 = n_2/m are co-prime.

The probability that k integers are co-prime is given by 1/ζ(k) so the probability that x_1 and x_2 are co-prime is 1/ζ(2) or 6/π^2, about 61%.

Like @Thomas said, once m is found the remainder of the problem is easy.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.