Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

## Chapter 16Pseudo-Random-Sequence Generators and Stream Ciphers

### 16.1 Linear Congruential Generators

Linear congruential generators are pseudo-random-sequence generators of the form

Xn = (aXn-1 + b) mod m

in which Xn is the nth number of the sequence, and Xn-1 is the previous number of the sequence. The variables a, b, and m are constants: a is the multiplier, b is the increment, and m is the modulus. The key, or seed, is the value of X0.

This generator has a period no greater than m. If a, b, and m are properly chosen, then the generator will be a maximal period generator (sometimes called maximal length) and have period of m. (For example, b should be relatively prime to m.) Details on choosing constants to ensure maximal period can be found in [863,942]. Another good article on linear congruential generators and their theory is [1446].

Table 16.1, taken from [1272], gives a list of good constants for linear congruential generators. They all produce maximal period generators and even more important, pass the spectral test for randomness for dimensions 2, 3, 4, 5, and 6 [385,863]. They are organized by the largest product that does not overflow a specific word length.

The advantage of linear congruential generators is that they are fast, requiring few operations per bit.

Unfortunately, linear congruential generators cannot be used for cryptography; they are predictable. Linear congruential generators were first broken by Jim Reeds [1294,1295,1296] and then by Joan Boyar [1251]. She also broke quadratic generators:

Xn = (aXn-12 + bXn-1 + c) mod m

and cubic generators:

Xn = (aXn-13 + bXn-12 + cXn-1 + d) mod m

Other researchers extended Boyar’s work to break any polynomial congruential generator [923,899,900]. Truncated linear congruential generators were also broken [581,705,580], as were truncated linear congruential generators with unknown parameters [1500,212]. The preponderance of evidence is that congruential generators aren’t useful for cryptography.

Table 16.1
Constants for Linear Congruential Generators

Overflow At: a b m

220 106 1283 6075
221 211 1663 7875
222 421 1663 7875
223 430 2531 11979
936 1399 6655
1366 1283 6075
224 171 11213 53125
859 2531 11979
419 6173 29282
967 3041 14406
225 141 28411 134456
625 6571 31104
1541 2957 14000
1741 2731 12960
1291 4621 21870
205 29573 139968
226 421 17117 81000
1255 6173 29282
281 28411 134456
227 1093 18257 86436
421 54773 259200
1021 24631 116640
1021 25673 121500
228 1277 24749 117128
741 66037 312500
2041 25673 121500
229 2311 25367 120050
1807 45289 214326
1597 51749 244944
1861 49297 233280
2661 36979 175000
4081 25673 121500
3661 30809 145800
230 3877 29573 139968
3613 45289 214326
1366 150889 714025
231 8121 28411 134456
4561 51349 243000
7141 54773 259200
232 9301 49297 233280
4096 150889 714025
233 2416 374441 1771875
234 17221 107839 510300
36261 66037 312500
235 84589 45989 217728

[an error occurred while processing this directive]