# Pseudorandom Bits and Sequences

Contents in Brief

- 5.1 Introduction.............................169
- 5.2 Random bit generation.......................171
- 5.3 Pseudorandom bit generation....................173
- 5.4 Statistical tests ...........................175
- 5.5 Cryptographically secure pseudorandom bit generation......185
- 5.6 Notes and further references....................187

## Introduction

The security of many cryptographic systems depends upon the generation of unpredictable quantities. Examples include the keystream in the one-tune pad (§1.5.4), the secret key in the DES encryption algorithm (§7.4.2), the primes *p, q* in the RSA encryption (§8.2) and digital signature (§11.3.1) schemes, the private key *a* in the DSA (§11.5.1), and the challenges used hi challenge-response identification systems (§10.3). In all these cases, the quantities generated must be of sufficient size and be “random” in the sense that the probability of any particular value being selected must be sufficiently small to preclude an adversary' from gaining advantage through optimizing a search strategy based on such probability. For example, the key space for DES has size 2^{56}. If a secret key *к* were selected using a true random generator, an adversary would on average have to try 2^{55} possible keys before guessing the correct key *k.* If, on the other hand, a key *к* were selected by first choosing a 16-bit random secret *s,* and then expanding it into a 56-bit key *к* using a complicated but publicly known function /, the adversary would on average only need to try 2^{15} possible keys (obtamed by running every possible value for s through the function /).

This chapter considers techniques for the generation of random and pseudorandom bits and numbers. Related techniques for pseudorandom bit generation that are generally discussed hi the literature in the context of stream ciphers, including linear and nonlinear feedback shift registers (Chapter 6) and the output feedback mode (OFB) of block ciphers (Chapter 7), are addressed elsewhere hi this book.

**Chapter outline**

The remainder of §5.1 introduces basic concepts relevant to random and pseudorandom bit generation. §5.2 considers techniques for random bit generation, while §5.3 considers some techniques for pseudorandom bit generation. §5.4 describes statistical tests designed to measure the quality of a random bit generator. Cryptographically secure pseudorandom bit generators are the topic of §5.5. §5.6 concludes with references and further chapter notes.