# 5.1 Pseudorandom Bit Generation

The one-time pad and many other cryptographic applications require sequences of random bits. Before we can use a cryptographic algorithm, such as DES (Chapter 7) or AES (Chapter 8), it is necessary to generate a sequence of random bits to use as the key.

One way to generate random bits is to use natural randomness that occurs in nature. For example, the thermal noise from a semiconductor resistor is known to be a good source of randomness. However, just as flipping coins to produce random bits would not be practical for cryptographic applications, most natural conditions are not practical due to the inherent slowness in sampling the process and the difficulty of ensuring that an adversary does not observe the process. We would therefore like a method for generating randomness that can be done in software. Most computers have a method for generating random numbers that is readily available to the user. For example, the standard C library contains a function rand() that generates pseudorandom numbers between 0 and 65535. This pseudorandom function takes a seed as input and produces an output bitstream.

The rand() function and many other pseudorandom number generators are based on linear congruential generators. A linear congruential generator produces a sequence of numbers , where



The number  is the initial seed, while the numbers , , and  are parameters that govern the relationship. The use of pseudorandom number generators based on linear congruential generators is suitable for experimental purposes, but is highly discouraged for cryptographic purposes. This is because they are predictable (even if the parameters , , and  are not known), in the sense that an eavesdropper can use knowledge of some bits to predict future bits with fairly high probability. In fact, it has been shown that any polynomial congruential generator is cryptographically insecure.

In cryptographic applications, we need a source of bits that is nonpredictable. We now discuss two ways to create such nonpredictable bits.

The first method uses one-way functions. These are functions  that are easy to compute but for which, given , it is computationally infeasible to solve  for . Suppose that we have such a one-way function  and a random seed . Define  for . If we let  be the least significant bit of , then the sequence  will often be a pseudorandom sequence of bits (but see Exercise 14). This method of random bit generation is often used, and has proven to be very practical. Two popular choices for the one-way function are DES (Chapter 7) and SHA, the Secure Hash Algorithm (Chapter 11). As an example, the cryptographic pseudorandom number generator in the OpenSSL toolkit (used for secure communications over the Internet) is based on SHA.

Another method for generating random bits is to use an intractable problem from number theory. One of the most popular cryptographically secure pseudorandom number generators is the Blum-Blum-Shub (BBS) pseudorandom bit generator, also known as the quadratic residue generator. In this scheme, one first generates two large primes  and  that are both congruent to 3 mod 4. We set  and choose a random integer  that is relatively prime to . To initialize the BBS generator, set the initial seed to . The BBS generator produces a sequence of random bits  by

1. 

2.  is the least significant bit of .

# Example

Let




Take . The initial seed is



The values for  are



Taking the least significant bit of each of these, which is easily done by checking whether the number is odd or even, produces the sequence .

The Blum-Blum-Shub generator is very likely unpredictable. See [Blum-Blum-Shub]. A problem with BBS is that it can be slow to calculate. One way to improve its speed is to extract the  least significant bits of . As long as , this seems to be cryptographically secure.