Hardware random number generator

Lore & Background

Physical devices have been used to generate random numbers for thousands of years, primarily for gambling. Dice have been known for more than 5000 years, found in locations in modern Iraq and Iran, and coin flipping dates at least to ancient Rome. The first documented scientific use of a physical random number generator was by Francis Galton in 1890, who sampled a probability distribution using a common gambling die by looking at both the top digit and the face closest to him, creating 24 outcomes. In 1938, Kendall and Babington-Smith used a fast-rotating 10-sector disk illuminated by periodic bursts of light, with a human writing the number under the light beam, to produce a 100,000-digit random number table.

On 29 April 1947, the RAND Corporation began generating random digits with an 'electronic roulette wheel' consisting of a random frequency pulse source gated once per second and fed into a five-bit binary counter. Douglas Aircraft built the equipment, implementing Cecil Hasting's suggestion for a noise source, likely the behavior of the 6D4 miniature gas thyratron tube in a magnetic field. The results were converted into a table, originally existing as a deck of punched cards, later published in 1955 as the book 'A Million Random Digits with 100,000 Normal Deviates'. Since the early 1950s, research into TRNGs has been highly active, with thousands of research works published and about 2000 patents granted by 2017.

Multiple TRNG designs have been proposed using various physical phenomena, classified into four groups: electrical noise, free-running oscillators, chaos, and quantum effects. Noise-based RNGs typically feed a noise source into a comparator, with sources including Johnson–Nyquist thermal noise, Zener noise, and avalanche breakdown. Chaos-based RNGs use complex systems like lasers in chaos mode, though this technique has been characterized as 'most objectionable' because chaotic behavior is usually controlled by a differential equation, potentially limiting output strings. Free-running oscillator-based RNGs are also common.

Reader's Guide

Hardware random number generators are primarily used in cryptography, where their unpredictability and impossibility to re-run sequences are crucial. They create random cryptographic keys and nonces needed to encrypt and sign data. Cryptographic applications require forward secrecy (past output should not enable prediction of future data) and backward secrecy (future output should not divulge preceding data), typically fulfilled by using a TRNG to seed a cryptographically secure pseudorandom number generator. TRNGs generally produce limited random bits per second, so they are often used to generate seeds for faster PRNGs, which also help with noise source anonymization and entropy extraction. With a proper CSPRNG algorithm, the combination can satisfy Federal Information Processing Standards and Common Criteria standards.

TRNGs have drawbacks for data science and statistical applications: sequences cannot be re-run unless stored, and reliance on an analog physical entity can obscure source failure. Therefore, they are primarily used in cryptography and gambling machines. The RAND table from 1955 was a significant breakthrough, providing a large and carefully prepared source for simulations, modeling, and deriving arbitrary constants in cryptographic algorithms to demonstrate that constants were not selected maliciously. Practical considerations for TRNG designs include use of inexpensive silicon processes, exclusive digital design techniques for easier system-on-chip integration, compact and low-power design discouraging analog components, and mathematical justification of entropy collection mechanisms.

Did You Know?

• Dice have been used for random number generation for more than 5000 years, found in modern Iraq and Iran.
• The RAND Corporation began generating random digits on 29 April 1947 using an 'electronic roulette wheel'.
• Francis Galton in 1890 created 24 outcomes from a single die by reading both the top and side faces.
• About 2000 patents for TRNGs had been granted by 2017.