4.7 Generation of pseudorandom bit sequences

Many cryptographic systems use sequences of random (or pseudorandomly generated) bits. For example, if an e-mail message is digitally enveloped, an encryption key ”sometimes also called session key ”must be randomly selected by the sender of the message. This key is used to encrypt and digitally envelope the message. Also, random or pseudorandom numbers are required to initially generate public key pairs.

Randomness is a statistical property of a sequence of values. In the case of bit values, the requirement is for an adversary to be unable to predict the next bit in a sequence even when all previously generated bits are known. The problem is that if it is possible to predict some of the sequence of bits used, it may be possible to reduce the size of the domain from which the key being generated is selected. If the domain is significantly reduced, an exhaustive key search may become feasible .

Locating a source of unpredictable bits presents a unique challenge on most computer systems (because a hardware source of unpredictable bits is usually not available). Consequently, a whole branch of cryptographic research is dedicated to the problem of how to generate pseudorandom bit sequences using only software. In fact, there are various approaches to address this problem. For example, one software-based approach is to use a cryptographically strong OWHF to hash a large amount of information with limited unpredictability available. Such information can, for example, be derived from the current status of the computer system (using corresponding system commands) or the mouse movements and position of keyboard strokes. Because a OWHF generates a fixed size quantity, the process is iterated as many times as are necessary to get the required number of bits.

In 1994, an informational RFC was published that addresses the problem of how to randomly or pseudorandomly generate bit sequences [33]. It recommends the use of hardware and shows that the existing hardware on many systems can be used for this purpose. Also, it provides suggestions for ameliorating the problem when a hardware solution is not available.