Cryptography Reference
In-Depth Information
(e.g., during a crash), it can be manipulated (e.g., by spreading rumors or by placing
a large stock transaction), and it is never secret.
In [2], it is argued that the best overall strategy for meeting the requirement
for unguessable random bits in the absence of a single reliable source is to obtain
random input from a large number of uncorrelated sources and to mix them with
a strong mixing function. A strong mixing function, in turn, is one that combines
two or more inputs and produces an output where each output bit is a different
complex nonlinear function of all input bits. On average, changing an input bit will
change about half of the output bits. But because the relationship is complex and
nonlinear, no particular output bit is guaranteed to change when any particular input
bit is changed. A trivial example for such a function is addition modulo 2 32 .More
general strong mixing functions (for more than two inputs) can be constructed using
other cryptographic systems, such as cryptographic hash functions or symmetric
encryption systems.
9.2.3
Deskewing Techniques
Any source of random bits may be defective in that the output bits may be biased
(i.e., the probability of the source emitting a one is not equal to 1 / 2)orcorrelated
(i.e., the probability of the source emitting a one depends on previously emitted bits).
There are many deskewing techniques for generating truly random bit sequences
from the output bits of such a defective random bit generator. For example, if a
random bit generator outputs biased but uncorrelated bits, then one can group the
output sequence into pairs of bits, with a 10 pair transformed to a 1 ,a 01 pair
transformed to a 0 ,and 00 and 11 pairs discarded. The resulting binary sequence is
both unbiased and uncorrelated. This simple technique is due to John von Neumann
[11]. It was later generalized to achieve an output rate near the source entropy [12].
Handling a correlated bit source is more involved. Manuel Blum showed how to
produce unbiased uncorrelated bits from a biased correlated source [13]. 2
These
results were later generalized in many respects.
9.3
STATISTICAL RANDOMNESS TESTING
While it is impossible to give a mathematical proof that a generator is indeed a ran-
dom bit generator, statistical randomness tests may help detect certain kinds of weak-
nesses in the generator. This is accomplished by taking a sample output sequence of
the random bit generator and subjecting it to various (statistical randomness) tests.
2
Note, however, that this does not imply that the resulting bits have good randomness properties; it
only means that they are unbiased and uncorrelated.
Search WWH ::




Custom Search