Hardware random number generator

So-called "random numbers" generated by computers are usually pseudo-random numbers generated by an arithmetic algorithm.

There are several different informal definitions of randomness, usually based on either a lack of discernable patterns, or their unpredictability. Although pseudo-random numbers may appear to lack a discernable pattern, they always have a pattern -- the pattern given by the algorithm that generates them, and its starting state. Nor are they unpredictable; given the knowledge of the original state of the generator, and its algorithm, they are totally predictable.

As John von Neumann put it, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin".

This article is about the attempts to generate and use "random numbers" generated from apparently random physical phenomena.

Uses of physically generated "random" numbers

Unpredictable random numbers were first used in gambling, and many randomizing devices such as dice, shuffling of playing cards, and roulette wheels, were first developed for use in gambling. More recently developed uses of unpredictable random numbers include their uses in statistics and cryptography.

Note that in cryptography the random bits generally need to be not only unpredictable, but also secret: public or third-party sources of random values, or random values computed from publically observable phenomena, are not generally of any use for cryptographic purposes.

Utility

The big industrial use of true random numbers is to make unpredictable keys for encryption. Since most keys are a few thousand bits at most, simple slow random number generators are good enough. This use is important-enough that many designers believe every computer should have a way to generate true random numbers.

A particular strength is that true random numbers are needed for absolutely unbreakable encryption, to generate one-time pads.

Occasionally people need them for statistical research, noise resonance studies, or other scientific or technical uses.

Cheap random numbers (if available) are handy for erasing files, and similar technical tasks.

Physical phenomena used for random number generation

People have successfully used a radiation source (some from a smoke-alarm) to drive Geiger counters attached to a PC, as at HotBits.

They have also measured atmospheric noise with a radio receiver attached to a PC, as at random.org.

Optical quantum random number generators have been prototyped. A group at Silicon Graphics even used digital cameras to watch Lava Lamps (TM) to generate random numbers.

However, the most common form of hardware random number generator uses a varying voltage source, either generated from a reverse-biased zener diode or from thermal noise, such as in a resistor.

Generating random numbers from a random voltage

The generated noise signal is amplified and filtered, then run through a high-speed voltage comparator to make a randomly varying logic signal.

In some simple implementations, this logic value is converted to an "RS-232" level signal and sent directly to a computer's serial port. Software then sees this series of logic values as bursts of "line noise" characters on its I/O port. More sophisticated systems may digitise the noise value directly with an analog to digital convertor before feeding it to software, or format the thresholded and sampled bit values before passing them to the computer as a data stream.

The bit-stream from such a system is prone to be biased, with 1s or 0s predominating. One of the commonest methods to adjust for this applies feedback based on low-pass filtering the generated bits to adjust the threshold of the comparator that is used to discriminate between zero and one bits. By the central limit theorem, the feedback loop will tend to be well-adjusted almost all the time. Ultra-high speed random number generators use this method. Even then, the numbers generated will still be biased.

A quality device might use two diodes and eliminate signals that are common to both - this eliminates interference from outside electric and magnetic fields. This is recommended for gambling devices, to prevent cheating.

The Intel RNG (supplied in their board-level chip sets for a PC), uses most of the above tricks and adds another: The non-common-mode noise from two diodes controls a voltage-controlled oscillator, which clocks bits from a rapid oscillator (the new trick), which then go through a von Neumann decorrelator.

Another method uses two uncoupled oscillators, and counts events in one from the time-base of another. This method has been used on PCs to generate pure-software true-random number generators. It requires a PC with two clock crystals, one for the real-time clock, and another for the processor. The program loops, counting the time that one of the bits of the counter of the real-time clock is a 1. The least significant bit of the loop-counter is quite random.

Cleaning up the bit-stream

Even after all these measures have been taken, the bit-stream should still be assumed to contain bias and correlation.

John von Neumann invented a simple algorithm to fix simple bias, and somewhat reduce correlation: it considers bits two at a time. When two successive bits are the same, they are not used as a random bit. A sequence of 1,0 becomes a 1. A sequence of 0,1 becomes a zero. This eliminates simple bias, and is easy to implement in a computer program or digital logic, although it reduces the bit rate available by a factor of four, on average.

This technique words regardless of whether the bits have been generated by watching a random voltage or a stream of events such as radioactive decay.

Hashing the bit-stream

to be written

Software implementation of random number generators from observed events

to be written -- mention:

/dev/random
/dev/urandom

Problems

It is very easy to mis-construct such devices. Also, they break silently, often having increasingly less-random numbers before failing.

Because they are quite fragile, and fail silently, statistical tests should be performed constantly. Many such devices build the tests into the software that reads the device.

Checking the performance of hardware random number generators