Click Here! |

Brief Full Advanced Search Search Tips
|  |  | To access the contents, click the chapter and section titles. 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 Search this book:
Previous | Table of Contents | Next
## Chapter 16 Pseudo-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
Previous | Table of Contents | Next
[an error occurred while processing this directive]

| Products | Contact Us | About Us | Privacy | Ad Info | Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.