Notes

Cryptographic algorithms come in a variety of flavors. Some are strong (meaning difficult to crack)
but make substantial demands to processing power and key management. Others are weak (meaning
easier to crack) but generally less demanding and therefore better suited for some applications. All
strong cryptography requires true random numbers to generate keys, but how many depends on
the encryption scheme. The strongest possible method, One Time Pad (OTP for short) encryption,
is the most demanding of all; it requires as many random bits as there are bits of information to
be encrypted.
True random numbers are typically generated by sampling and processing a source of entropy
outside the computer. A source of entropy can be very simple, like the little variations in somebody’s
mouse movements or in the amount of time between keystrokes. In practice, however, it can be
tricky to use user input as a source of entropy. Keystrokes, for example, are often buffered by the
computer’s operating system, meaning that several keystrokes are collected before they are sent to
the program waiting for them. To the program, it will seem as though the keys were pressed almost
simultaneously.
A really good source of entropy is a radioactive source. The points in time at which a radioactive
source decays are completely unpredictable, and can be sampled and fed into a computer, avoiding
any buffering mechanisms in the operating system. In fact, this is what the HotBits people at
Fourmilab in Switzerland are doing. Another source of entropy could be atmospheric noise from a
radio, like that used here at random.org, or even just background noise from an office or laboratory.
The lavarand people at Silicon Graphics have been clever enough to use lava lamps to generate
random numbers, so their entropy source not only gives them entropy, it also looks good! The
latest random number generator to come online (both lavarand and HotBits precede random.org)
is Damon Hart-Davis’ Java EntropyPool which gathers random bits from a variety of sources
including HotBits and random.org, but also from web page hits received by the EntropyPool’s web
server.
Random.org
”This is the third time; I hope good luck lies in odd numbers The idea of using atmospheric noise to generate random numbers came up when some friends
and I were building a prototype of an online gambling system. Using noise in this way isn’t a
particularly original idea, though. Other people thought of it before us, and as mentioned above,
there are already several public random number services out there, some of which use more advanced
methods. So, why yet another? The most important reason is because it was fun to make. The
second most important reason is that existing services are mostly for educative purposes — and for
fun! I hope random.org will prove itself informative and fun but also useful for certain (non-critical)
applications that need random numbers. Random.org is the only service I know of which offers a
large (16K) block of numbers at once and which has a CORBA interfaceThe way the random.org random number generator works is quite simple. A radio is tuned into
a frequency where nobody is broadcasting. The atmospheric noise picked up by the receiver is fed
into a Sun SPARC workstation through the microphone port where it is sampled by a program
as an eight bit mono signal at a frequency of 8KHz. The upper seven bits of each sample are
discarded immediately and the remaining bits are gathered and turned into a stream of bits with
a high content of entropy. Skew correction is performed on the bit stream, in order to ensure that
there is an approximately even distribution of 0s and 1s.
The skew correction algorithm used is based on transition mapping. Bits are read two at a
time, and if there is a transition between values (the bits are 01 or 10) one of them - say the first -
is passed on as random. If there is no transition (the bits are 00 or 11), the bits are discarded and
the next two are read. This simple algorithm was originally due to Von Neumann and completely
eliminates any bias towards 0 or 1 in the data. It is only one of several ways of performing skew
correction, though, and has a number of drawbacks. First, it takes an indeterminate number of
input bits. Second, it is quite inefficient, resulting in the loss of 75% of the data, even when the bit
stream is already unbiased. RFC1750 discusses skew correction in general and lists this method as
well as three others. Paul Crowley discusses skew correction for use with Geiger counters and also
maintains a page with implementations of a number of skew correction algorithms. The quality of random numbers can be measured in a variety of ways. One common method is to
compute the information density, or entropy, in a series of numbers. The higher the entropy in a
series of numbers is, the more difficult it is to predict a given number on the basis of the preceding
numbers in the series. A sequence of good random numbers will have a high level of entropy,
although a high level of entropy does not guarantee randomness. (As an example, a file compressed
with a software compressor such as gzip or winzip has a high level of entropy, but the data is highly
structured and therefore not random.) Hence, for a thorough test of a random number generator,
computing the level of entropy in the numbers alone is not enough.
A number of basic tests, such as the entropy test described above, were implemented by John
Walker from Fourmilab in form of his ent program. Here is what John’s program said about one
megabyte of numbers from random.org: