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 $x_1\text{,}{x}_2\text{,}\cdots$, where

The number $x_0$ is the initial seed, while the numbers $a$, $b$, and $m$ 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 $a$, $b$, and $m$ 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 $f(x)$ that are easy to compute but for which, given $y$, it is computationally infeasible to solve $y=f(x)$ for $x$. Suppose that we have such a one-way function $f$ and a random seed $s$. Define $x_j=f(s+j)$ for $j=1\text{,}2\text{,}3\text{,}\dots$. If we let $b_j$ be the least significant bit of $x_j$, then the sequence $b_0\text{,}{b}_1\text{,}\cdots$ 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 $p$ and $q$ that are both congruent to 3 mod 4. We set $n=pq$ and choose a random integer $x$ that is relatively prime to $n$. To initialize the BBS generator, set the initial seed to $x_0\equiv x^2(\text{mod }n)$. The BBS generator produces a sequence of random bits $b_1\text{,}{b}_2\text{,}\cdots$ by

1. $x_j\equiv x_{j-1}^2(\text{mod }n)$

2. $b_j$ is the least significant bit of $x_j$.

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 $k$ least significant bits of $x_j$. As long as $k\le {\log }_2{\log }_{2}n\text{,}$, this seems to be cryptographically secure.