Cryptography Reference
In-Depth Information
Chapter 12
Pseudorandom Bit Generators
Anyone who considers arithmetical methods of producing random digits
is, of course, in a state of sin.
— John von Neumann
1
In Chapter 9, we concluded that it is often important to be able to generate truly
random bits (using, for example, a random bit generator), to use these bits to seed
a PRBG, and to use the PRBG to generate a potentially infinite pseudorandom bit
sequence. Consequently, PRBGs have many applications in practice. In this chapter,
we elaborate on PRBGs. More specifically, we introduce the topic in Section 12.1,
address cryptographically secure PRBGs in Section 12.2, and conclude with some
final remarks in Section 12.3.
12.1
INTRODUCTION
According to Section 2.2.3 and Definition 2.9, a PRBG is an efficient deterministic
algorithm that, given as input a truly random binary sequence of length
k
(i.e., the
seed), generates and outputs a binary sequence of length
l
k
(i.e., the pseudo-
random bit sequence) that appears to be random. Note that we require the algorithm
that represents the PRBG to be deterministic, and hence the existence of PRBGs
seems to contradict the quote of John von Neumann given above. If, however, one
understands von Neumann's quote to refer to the seed of a PRBG (and hence to a
random bit generator), it still applies. The seed for a PRBG must be generated non-
deterministically, and hence the existence and use of a PRBG does not eliminate the
1
In: Des MacHale,
Comic Sections: The Topic of Mathematical Jokes, Humour, Wit, and Wisdom
,
Boole Press, Dublin, Ireland, 1993.
