633 APPENDIX K Random Number Generator Cryptography and randomness are closely related. In Appendix F, Information Theory , we mentioned that perfect secrecy can be achieved if the key of the encipherment algo- rithm is truly a random number. There are two approaches to generating a long stream of random bits: using a natural random process, such as fl ipping a coin many times and interpreting heads and tails as 0-bits and 1-bits, or using a deterministic process with feedback. The fi rst approach is called a true random number generator (TRNG) ; the second is called a pseudorandom number generator (PRNG). Figure K.1 shows these two approaches. K.1TRNG Although fl ipping a fair coin continuously creates a perfect stream of bits, it is not prac- tical. There are many natural sources that can produce true random numbers, such as sampling thermal noise produced in an electric resistor or measuring the response time of a mechanical or electrical process. These natural resources have been used in the past, and some of them have been commercialized. However, there are several drawbacks to this approach. The process is normally slow, and the same random stream cannot be repeated if needed. Figure K.1 TRNG and PRNG Deterministic process Feedback Long stream Short stream a. TRGNb. PRNG Long stream Repeated experiments Random process for70220_appK.fm Page 633 Tuesday, January 30, 2007 3:22 AM 634 APPENDIX KRANDOM NUMBER GENERATOR K.2PRNG A reasonably random stream of bits can be achieved using a deterministic process with a short random stream as the input (seed). A pseudorandom number generator uses this approach. The generated number is not truly random because the process that creates it is deterministic. PRNGs can be divided into two broad categories: congruential genera- tors and generators using cryptographic ciphers. We discuss some generators in each category. Congruential Generators Several methods use some congruential relations. Linear Congruential Generator In computer science, the most common technique for generating pseudorandom num- bers is the linear congruential method, introduced by Lehmer. As Figure K.2 shows, this method recursively creates a sequence of pseudorandom numbers using a linear congruence equation of the form x i + 1 = ( ax i + b ) mod n , where x 0 , called the seed, is a number between 0 and n 1. The sequence is periodic, where the period depends one how carefully the coeffi - cients, a and b , are selected. The ideal is to make the period as large as the modulus n . Example K.1 Assume that a = 4, b = 5, n = 17, and x 0 = 7. The sequence is 16, 1, 9, 7, 16, 1, 9, 7, , which is defi nitely a poor pseudorandom sequence; the period is only 4. Criteria Several criteria for an acceptable PRNG have been developed during the last few decades: 1. The period must be equal to n (the modulus). This means that, before the integers in the sequence are repeated, all integers between 0 and n 1 must be generated. 2. The sequence in each period must be random. 3. The generating process must be effi cient. Most computers today are effi cient when arithmetic is done using 32-bit words. Figure K.2 Linear congruential pseudorandom number generator Feedback SeedRandom number x0 xi + 1 = (axi + b) mod n na b for70220_appK.fm Page 634 Tuesday, January 30, 2007 3:22 AM SECTION K.2PRNG 635 Recommendation Based on the previous criteria, the following are recommended for selecting the coeffi cients of the congruence equation and the value of the modulus. 1. A good choice for the modulus, n , is the largest prime number close to the size of a word in the computer being used. The recommendation is to use the thirty-fi rst Mersenne prime as the modulus: n = M 31 = 2 31 1. 2. To create a period as long as the modulus, the value of the fi rst coeffi cient, a , should be a primitive root of the prime modulus. Although the integer 7 is a primi- tive root of M 31 , it is recommended to use 7 k , where k is an integer coprime with (M 31 1). Some recommended values for k are 5 and 13. This means that ( a = 7 5 ) or ( a = 7 13 ). 3. For the second recommendation to be effective, the value of the second coeffi cient, b , should be zero. Security A sequence generated by a linear congruential equation shows reasonable randomness if the previous recommendations are followed. The sequence is useful in some applications where only randomness is required (such as simulation); it is useless in cryptography where both randomness and secrecy are desired. Because n is public, the sequence can be attacked by Eve using one of the two strategies: a. If Eve knows the value of the seed ( x 0 ) and the coeffi cient a , she can easily regener- ate the whole sequence. b. If Eve does not know the value of x 0 and a , she can intercept the fi rst two integers and use the following two equations to fi nd x 0 and a : Quadratic Residue Generator To make the pseudorandom sequence less predictable, a quadratic residue generator has be