Cryptography Reference
In-Depth Information
These notions are all to do with ideas such as 'unpredictability' and 'uncertainty'.
We would like randomly generated numbers in general to be hard to predict
and appear to have no relationship with previous randomly generated numbers.
By the same measure, we would like randomly generated bits to be apparently
unpredictable sequences of bits.
Ironically, however, although randomness is hard to define, there are many
ways that we would like randomness to behave that are easily identifiable.
A random number generation process is often assessed by applying a series of
statistical tests. Many of these tests are fairly intuitive and include checks such as,
on average, over the generation of many random outputs:
• does 1 appear in the output of the process approximately as often as 0 does?
• does a 0 followa1intheoutput of the process approximately as often as a 1
follows a 1?
• does the string 000 occur in the output of the process approximately as often
as the string 111?
Human intuition often confuses randomness with evenly spaced distributions.
For example, many people believe that the binary string 10101010 is more likely
to have been produced by a truly uniform random source than the binary string
11111111. In fact, the probability that a uniform random source produces these
two outputs is exactly the same, and is equal to the probability that it produces a
string with no apparent pattern such as 11010001. By the same token, some bank
customers get concerned when the bank issues them with the PIN 3333, when in
fact this should be just as unlikely to occur as the PIN 7295. (Of course, a bank
customer is perhaps more likely to change a PIN to something like 3333, so there is
a genuine case for considering 3333 to be a less secure PIN in practice, but it is not
a failure of the bank's random PIN generation process!) Statistical tests provide
rigorous methods for assessing a random generation process that are much more
reliable than human intuition.
8.1.3
Non-deterministic generators
There are two general approaches to generating randomness. First we will
look at
non-deterministic
generation, which relies on unpredictable sources in
the physical world. This is a compelling, but often expensive, approach to
producing randomness. On the other hand, there are many situations where we
are willing to compromise and use a 'cheaper' source of randomness. In this case,
deterministic
generation techniques, which we examine in Section 8.1.4, can be
adopted.
A
non-deterministic generator
is based on the randomness produced by
physical phenomena and therefore provides a source of 'true randomness' in
the sense that the source is very hard to control and replicate. Non-deterministic
generators can be based on hardware or software.
