Cryptography Reference
In-Depth Information
Figure 2.3
A random bit generator.
has no input (i.e., it only generates an output), and that because the output of
the random bit generator is a sequence of statistically independent and unbiased
bits, the bits occur with the same probability (i.e., Pr[0] =Pr[1] = 1
/
2), or—
more generally—all 2
k
different
k
-tuples occur approximately equally often for all
+
. There are many statistical tests that can be used to verify the (randomness)
properties of a given random bit generator.
There is no known deterministic (i.e., computational) realization or imple-
mentation of a random bit generator. There are, however, many nondeterministic
realizations and implementations. Many of these realizations and implementations
make use of physical events and phenomena. In fact, it is fair to say that a (true) ran-
dom bit generator requires a naturally occuring source of randomness.
2
Designing
and implementing a device or algorithm that exploits this source of randomness to
generate binary sequences that are free of biases and correlations is a challenging
and highly demanding (engineering) task. As further addressed in Chapter 9, there
are solutions for this task. To be useful for cryptographic applications, the resulting
random bit generators must also be resistant to various types of passive and active
attacks.
k
∈
N
2.2
SECRET KEY CRYPTOSYSTEMS
According to Definition 1.6, secret key cryptosystems use secret parameters that are
shared between the participating entities. Examples include symmetric encryption
systems, MACs, PRBGs, and PRFs. Again, let us have a preliminary look at these
systems.
2
See, for example, the leading quote of John von Neumann in Chapter 12.
