Cryptography Reference
In-Depth Information
Each test determines whether the sequence possesses a certain attribute that a truly
random sequence would be likely to exhibit. An example of such an attribute is that
the sequence has roughly the same number of zeros as ones. The conclusion of each
test is not definite, but rather probabilistic. If the sequence is deemed to have failed
any one of the statistical tests, then the generator may be rejected as being non-
random. Otherwise, the generator may be subjected to further testing. On the other
hand, if the sequence passes all statistical randomness tests, then the generator is
accepted as being random.
3
Many statistical randomness tests are described in the literature, and we are not
going to delve into this topic for the purpose of this topic. Nevertheless, we want to
note that Ueli Maurer proposed a
universal statistical test
that can be used instead of
many statistical randomness tests [14]. The basic idea behind Maurer's universal sta-
tistical test is that it should not be possible to significantly compress (without loss of
information) the output sequence of a random bit generator. Alternatively speaking,
if a sample output sequence of a bit generator can be significantly compressed, then
the generator should be rejected as being defective. Instead of actually compressing
the sequence, Maurer's universal statistical test can be used to compute a quantity
that is related to the length of the compressed sequence. The universality of Maurer's
universal statistical test arises because it is able to detect any one of a very general
class of possible defects a bit generator may have. A drawback is that it requires
a much longer sample output sequence in order to be effective. Provided that the
required output sequence can be generated efficiently, however, this drawback is not
particularly worrisome.
9.4
FINAL REMARKS
Random bit generators are at the core of most systems that employ cryptographic
techniques in one way or another. If, for example, a secret key cryptosystem is used,
then a random bit generator should be used to generate and establish a shared secret
between the communicating peer entities. If a public key cryptosystem is used, then
a random bit generator should be used to generate a public key pair. Furthermore,
if the cryptosystem is probabilistic, then a random bit generator should be used for
each and every encryption or digital signature generation.
In this chapter, we elaborated on random bit generators and overviewed
and discussed some possible realizations and implementations thereof. There are
3
More precisely, the term
accepted
should be replaced by
not rejected
, because passing the tests
merely provides probabilistic evidence that the generator produces sequences that have specific
properties of random sequences.
