Cryptography Reference
In-Depth Information
Chapter 9
Random Bit Generators
Random numbers should not be generated with a method chosen at
random.
— Donald E. Knuth
In this chapter, we elaborate on random bit generators. More specifically, we
introduce the topic in Section 9.1, overview and discuss some possible realizations
and implementations of random bit generators in Section 9.2, address statistical
randomness testing in Section 9.3, and conclude with final remarks in Section 9.4.
9.1
INTRODUCTION
The term randomness is commonly used to refer to nondeterminism. If we say
that something is random, then we mean that we cannot determine its outcome,
or—equivalently—that its outcome is nondeterministic. Whether randomness really
exists or not is primarily a philosophical question. Somebody who believed that
everything is determined or behaves in a deterministic way would typically argue
that randomness does not exist in the first place. According to the present knowl-
edge in physics, however, randomness exists inherently in physical processes. For
example, randomness is a prerequisite and plays a crucial role in quantum physics.
For the purpose of this topic, we don't address the philosophical question and simply
assume that randomness exists.
If we assume the existence of randomness, then we may ask whether it is
possible to measure it in one way or another. For example, we may ask for a given
value whether it is random. Is 13 random? Is 27 random? Is 13 more random than 27?
