![Sun-crypto-accelerator-1000](https://upload.wikimedia.org/wikipedia/commons/7/74/Sun-crypto-accelerator-1000.jpg)
In
computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
, a hardware random number generator (HRNG) or true random number generator (TRNG) is a device that
generates random numbers from a
physical process
Physical changes are changes affecting the form of a chemical substance, but not its chemical composition. Physical changes are used to separate mixtures into their component compounds, but can not usually be used to separate compounds into chem ...
, rather than by means of an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
. Such devices are often based on microscopic phenomena that generate low-level,
statistically random "
noise
Noise is unwanted sound considered unpleasant, loud or disruptive to hearing. From a physics standpoint, there is no distinction between noise and desired sound, as both are vibrations through a medium, such as air or water. The difference arise ...
" signals, such as
thermal noise
A thermal column (or thermal) is a rising mass of buoyant air, a convective current in the atmosphere, that transfers heat energy vertically. Thermals are created by the uneven heating of Earth's surface from solar radiation, and are an example ...
, the
photoelectric effect
The photoelectric effect is the emission of electrons when electromagnetic radiation, such as light, hits a material. Electrons emitted in this manner are called photoelectrons. The phenomenon is studied in condensed matter physics, and solid st ...
, involving a
beam splitter
A beam splitter or ''beamsplitter'' is an optical device that splits a beam of light into a transmitted and a reflected beam. It is a crucial part of many optical experimental and measurement systems, such as interferometers, also finding wide ...
, and other
quantum
In physics, a quantum (plural quanta) is the minimum amount of any physical entity (physical property) involved in an interaction. The fundamental notion that a physical property can be "quantized" is referred to as "the hypothesis of quantizati ...
phenomena. These
stochastic
Stochastic (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselv ...
processes are, in theory, completely unpredictable for as long as an equation governing such phenomena is unknown or uncomputable. This is in contrast to the paradigm of
pseudo-random number generation commonly implemented in
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components.
A computer program ...
s.
A hardware random number generator typically consists of a
transducer
A transducer is a device that converts energy from one form to another. Usually a transducer converts a signal in one form of energy to a signal in another.
Transducers are often employed at the boundaries of automation, measurement, and contr ...
to convert some aspect of the physical phenomena to an electrical signal, an
amplifier
An amplifier, electronic amplifier or (informally) amp is an electronic device that can increase the magnitude of a signal (a time-varying voltage or current). It may increase the power significantly, or its main effect may be to boost the v ...
and other electronic circuitry to increase the amplitude of the random fluctuations to a measurable level, and some type of
analog-to-digital converter
In electronics, an analog-to-digital converter (ADC, A/D, or A-to-D) is a system that converts an analog signal, such as a sound picked up by a microphone or light entering a digital camera, into a digital signal. An ADC may also provide ...
to convert the output into a digital number, often a simple binary digit 0 or 1. By repeatedly sampling the randomly varying signal, a series of random numbers is obtained.
The main application for electronic hardware random number generators is in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, where they are used to generate random
cryptographic key
A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key c ...
s to transmit data securely. They are widely used in Internet encryption protocols such as
Transport Layer Security
Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securi ...
(TLS).
Random number generators can also be built from "random" macroscopic processes, using devices such as
coin flipping
Coin flipping, coin tossing, or heads or tails is the practice of throwing a coin in the air and checking obverse and reverse, which side is showing when it lands, in order to choose between two alternatives, heads or tails, sometimes used to res ...
,
dice
Dice (singular die or dice) are small, throwable objects with marked sides that can rest in multiple positions. They are used for generating random values, commonly as part of tabletop games, including dice games, board games, role-playing g ...
,
roulette
Roulette is a casino game named after the French word meaning ''little wheel'' which was likely developed from the Italian game Biribi''.'' In the game, a player may choose to place a bet on a single number, various groupings of numbers, the ...
wheels and
lottery machine
A lottery is a form of gambling that involves the drawing of numbers at random for a prize. Some governments outlaw lotteries, while others endorse it to the extent of organizing a national or state lottery. It is common to find some degree of ...
s. The presence of unpredictability in these phenomena is supported by the theory of
unstable
In numerous fields of study, the component of instability within a system is generally characterized by some of the outputs or internal states growing without bounds. Not all systems that are not stable are unstable; systems can also be mar ...
dynamical system
In mathematics, a dynamical system is a system in which a Function (mathematics), function describes the time dependence of a Point (geometry), point in an ambient space. Examples include the mathematical models that describe the swinging of a ...
s and
chaos theory
Chaos theory is an interdisciplinary area of scientific study and branch of mathematics focused on underlying patterns and deterministic laws of dynamical systems that are highly sensitive to initial conditions, and were once thought to have co ...
. Even though macroscopic processes are deterministic under
Newtonian mechanics
Newton's laws of motion are three basic laws of classical mechanics that describe the relationship between the motion of an object and the forces acting on it. These laws can be paraphrased as follows:
# A body remains at rest, or in motion ...
, the output of a well-designed device can be impractical to predict in practice, because it depends on the sensitive, micro-details of the
initial conditions
In mathematics and particularly in dynamic systems, an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted ''t'' = 0). For ...
of each use.
Although dice have been mostly used in
gambling
Gambling (also known as betting or gaming) is the wagering of something of value ("the stakes") on a random event with the intent of winning something else of value, where instances of strategy are discounted. Gambling thus requires three el ...
, and as "randomizing" elements in games (e.g.
role playing game
A role-playing game (sometimes spelled roleplaying game, RPG) is a game in which players assume the roles of characters in a fictional setting. Players take responsibility for acting out these roles within a narrative, either through literal a ...
s), the
Victorian scientist
Francis Galton
Sir Francis Galton, FRS FRAI (; 16 February 1822 – 17 January 1911), was an English Victorian era polymath: a statistician, sociologist, psychologist, anthropologist, tropical explorer, geographer, inventor, meteorologist, proto- ...
described a way to use dice to explicitly generate random numbers for scientific purposes in 1890.
Hardware random number generators generally produce only a limited number of random bits per second. In order to increase the available output data rate, they are often used to generate the "
seed
A seed is an embryonic plant enclosed in a protective outer covering, along with a food reserve. The formation of the seed is a part of the process of reproduction in seed plants, the spermatophytes, including the gymnosperm and angiospe ...
" for a faster
cryptographically secure pseudorandom number generator
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely kno ...
, which then generates a
pseudorandom
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic
Determinism is a philosophical view, where all events are determined completely by previously exi ...
output sequence at a much higher data rate.
With random number generators based on a noisy classical system or an elementary quantum measurement, assertions of unpredictability should be based on a careful model describing the underlying physics. Yet any such model must make a number of assumptions that may not be valid, and are difficult to verify. But starting in 2010, "Einstein-certified" quantum physics experiments have been able to demonstrate, sometimes even to remote observers, that the bits they produce are unpredictable, requiring only very mild assumptions about signals not being able to travel faster than the speed of light.
Uses
Unpredictable random numbers were first investigated in the context of
gambling
Gambling (also known as betting or gaming) is the wagering of something of value ("the stakes") on a random event with the intent of winning something else of value, where instances of strategy are discounted. Gambling thus requires three el ...
, and many randomizing devices such as
dice
Dice (singular die or dice) are small, throwable objects with marked sides that can rest in multiple positions. They are used for generating random values, commonly as part of tabletop games, including dice games, board games, role-playing g ...
,
shuffling playing cards
Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.
__TOC__
Techniques
Over ...
, and
roulette
Roulette is a casino game named after the French word meaning ''little wheel'' which was likely developed from the Italian game Biribi''.'' In the game, a player may choose to place a bet on a single number, various groupings of numbers, the ...
wheels, were first developed for such use. Fairly produced random numbers are vital to electronic gambling and ways of creating them are sometimes regulated by governmental gaming commissions.
Random numbers are also used for non-gambling purposes, both where their use is mathematically important, such as sampling for
opinion poll
An opinion poll, often simply referred to as a survey or a poll (although strictly a poll is an actual election) is a human research survey of public opinion from a particular sample. Opinion polls are usually designed to represent the opinions ...
s, and in situations where fairness is approximated by
randomization Randomization is the process of making something random. Randomization is not haphazard; instead, a random process is a sequence of random variables describing a process whose outcomes do not follow a deterministic pattern, but follow an evolution d ...
, such as
military draft lotteries and selecting
juror
A jury is a sworn body of people (jurors) convened to hear evidence and render an impartiality, impartial verdict (a Question of fact, finding of fact on a question) officially submitted to them by a court, or to set a sentence (law), penalty o ...
s.
Cryptography
The major use for hardware random number generators is in the field of
data encryption
In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can deci ...
, for example to create random
cryptographic key
A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key c ...
s and
nonces needed to encrypt and sign data. They are a more secure alternative to
pseudorandom number generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
s (PRNGs), software programs commonly used in computers to generate "random" numbers. PRNGs use a
deterministic algorithm
In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far ...
to produce numerical sequences. Although these pseudorandom sequences pass
statistical pattern tests for randomness, by knowing the algorithm and the conditions used to initialize it, called the "seed", the output can be predicted. Data encrypted with pseudorandom numbers is thus potentially vulnerable to
cryptanalysis
Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...
. Hardware random number generators produce sequences of numbers that can be very hard to predict, and therefore can provide the greatest security when used to encrypt data.
Early work
One early way of producing random numbers was by a variation of the same machines used to play
keno
Keno is a lottery-like gambling game often played at modern casinos, and also offered as a game in some lotteries.
Players wager by choosing numbers ranging from 1 through (usually) 80. After all players make their wagers, 20 numbers (some va ...
or select
lottery
A lottery is a form of gambling that involves the drawing of numbers at random for a prize. Some governments outlaw lotteries, while others endorse it to the extent of organizing a national or state lottery. It is common to find some degree of ...
numbers. These involved mixed, numbered ping-pong balls with blown air, perhaps combined with mechanical agitation, and used some method to withdraw balls from the mixing chamber (). This method can give reasonable results in some senses, but the random numbers generated by this means are expensive, and sometimes statistically flawed. The method is inherently slow, and is unusable for most computing applications.
On 29 April 1947,
RAND Corporation
The RAND Corporation (from the phrase "research and development") is an American nonprofit global policy think tank created in 1948 by Douglas Aircraft Company to offer research and analysis to the United States Armed Forces. It is financed ...
began generating random digits with an "electronic roulette wheel", consisting of a random frequency pulse source of about 100,000 pulses per second gated once per second with a constant frequency pulse and fed into a five-bit binary counter.
Douglas Aircraft
The Douglas Aircraft Company was an American aerospace manufacturer based in Southern California. It was founded in 1921 by Donald Wills Douglas Sr. and later merged with McDonnell Aircraft in 1967 to form McDonnell Douglas; it then operated as ...
built the equipment, implementing Cecil Hasting's suggestion (RAND P-113) for a noise source (most likely the well known behavior of the 6D4 miniature gas
thyratron
A thyratron is a type of gas-filled tube used as a high-power electrical switch and controlled rectifier. Thyratrons can handle much greater currents than similar hard-vacuum tubes. Electron multiplication occurs when the gas becomes ionized, pro ...
tube, when placed in a magnetic field). Twenty of the 32 possible counter values were mapped onto the 10 decimal digits and the other 12 counter values were discarded.
The results of a long run from the RAND machine, filtered and tested, were converted into a table, which was published in 1955 in the book ''
A Million Random Digits with 100,000 Normal Deviates
''A Million Random Digits with 100,000 Normal Deviates'' is a random number book by the RAND Corporation, originally published in 1955. The book, consisting primarily of a random number table, was an important
20th century work in the field of ...
''. The RAND table was a significant breakthrough in delivering random numbers because such a large and carefully prepared table had never before been available. It has been a useful source for simulations, modeling, and for deriving the arbitrary constants in cryptographic algorithms to demonstrate that the constants had not been selected maliciously. The block ciphers
Khufu and Khafre
In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Khuf ...
are among the applications which use the RAND table. ''See:''
Nothing up my sleeve number
In cryptography, nothing-up-my-sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need rand ...
s.
Physical phenomena with random properties
Quantum random properties
There are two fundamental sources of practical
quantum mechanical
Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, qua ...
physical randomness: quantum mechanics at the atomic or sub-atomic level and
thermal noise
A thermal column (or thermal) is a rising mass of buoyant air, a convective current in the atmosphere, that transfers heat energy vertically. Thermals are created by the uneven heating of Earth's surface from solar radiation, and are an example ...
(some of which is quantum mechanical in origin). Quantum mechanics predicts that certain physical phenomena, such as the
nuclear decay
Radioactive decay (also known as nuclear decay, radioactivity, radioactive disintegration, or nuclear disintegration) is the process by which an unstable atomic nucleus loses energy by radiation. A material containing unstable nuclei is consid ...
of atoms, are
fundamentally random and cannot, in principle, be predicted (for a discussion of empirical verification of quantum unpredictability, see
Bell test experiments
A Bell test, also known as Bell inequality test or Bell experiment, is a real-world physics experiment designed to test the theory of quantum mechanics in relation to Albert Einstein's concept of local realism. Named for John Stewart Bell, the e ...
). And, because the world exists at a temperature above
absolute zero
Absolute zero is the lowest limit of the thermodynamic temperature scale, a state at which the enthalpy and entropy of a cooled ideal gas reach their minimum value, taken as zero kelvin. The fundamental particles of nature have minimum vibration ...
, every system has some random variation in its state; for instance, molecules of gases composing air are constantly bouncing off each other in a random way (''see''
statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
.) This randomness is a quantum phenomenon as well (''see''
phonon
In physics, a phonon is a collective excitation in a periodic, Elasticity (physics), elastic arrangement of atoms or molecules in condensed matter physics, condensed matter, specifically in solids and some liquids. A type of quasiparticle, a phon ...
).
Because the outcome of quantum-mechanical events cannot be predicted even in principle, they are the ‘
gold standard
A gold standard is a monetary system in which the standard economic unit of account is based on a fixed quantity of gold. The gold standard was the basis for the international monetary system from the 1870s to the early 1920s, and from the la ...
’ for random number generation. Some quantum phenomena used for random number generation include:
*
Shot noise
Shot noise or Poisson noise is a type of noise which can be modeled by a Poisson process.
In electronics shot noise originates from the discrete nature of electric charge. Shot noise also occurs in photon counting in optical devices, where shot ...
, a quantum mechanical noise source in electronic circuits. A simple example is a lamp shining on a photodiode. Due to the
uncertainty principle
In quantum mechanics, the uncertainty principle (also known as Heisenberg's uncertainty principle) is any of a variety of mathematical inequalities asserting a fundamental limit to the accuracy with which the values for certain pairs of physic ...
, arriving photons create noise in the circuit. Collecting the noise for use poses some problems, but this is an especially simple random noise source. However, shot noise energy is not always well distributed throughout the bandwidth of interest. Gas diode and thyratron electron tubes in a crosswise magnetic field can generate substantial noise energy (10 volts or more into high impedance loads) but have a very peaked energy distribution and require careful filtering to achieve flatness across a broad spectrum.
* A
nuclear decay
Radioactive decay (also known as nuclear decay, radioactivity, radioactive disintegration, or nuclear disintegration) is the process by which an unstable atomic nucleus loses energy by radiation. A material containing unstable nuclei is consid ...
radiation source, detected by a
Geiger counter
A Geiger counter (also known as a Geiger–Müller counter) is an electronic instrument used for detecting and measuring ionizing radiation. It is widely used in applications such as radiation dosimetry, radiological protection, experimental ph ...
attached to a PC.
*
Photon
A photon () is an elementary particle that is a quantum of the electromagnetic field, including electromagnetic radiation such as light and radio waves, and the force carrier for the electromagnetic force. Photons are massless, so they always ...
s travelling through a
semi-transparent mirror. The
mutually exclusive events
In logic and probability theory, two events (or propositions) are mutually exclusive or disjoint if they cannot both occur at the same time. A clear example is the set of outcomes of a single coin toss, which can result in either heads or tails ...
(reflection/transmission) are detected and associated to ‘0’ or ‘1’ bit values respectively.
*
Amplification of the signal produced on the base of a
reverse-biased transistor
upright=1.4, gate (G), body (B), source (S) and drain (D) terminals. The gate is separated from the body by an insulating layer (pink).
A transistor is a semiconductor device used to Electronic amplifier, amplify or electronic switch, switch e ...
. The emitter is saturated with electrons and occasionally they will
tunnel
A tunnel is an underground passageway, dug through surrounding soil, earth or rock, and enclosed except for the entrance and exit, commonly at each end. A pipeline is not a tunnel, though some recent tunnels have used immersed tube cons ...
through the
band gap
In solid-state physics, a band gap, also called an energy gap, is an energy range in a solid where no electronic states can exist. In graphs of the electronic band structure of solids, the band gap generally refers to the energy difference (in ...
and exit via the base. This signal is then
amplified through a few more
transistor
upright=1.4, gate (G), body (B), source (S) and drain (D) terminals. The gate is separated from the body by an insulating layer (pink).
A transistor is a semiconductor device used to Electronic amplifier, amplify or electronic switch, switch e ...
s and the result fed into a
Schmitt trigger
In electronics, a Schmitt trigger is a comparator circuit with hysteresis implemented by applying positive feedback to the noninverting input of a comparator or differential amplifier. It is an active circuit which converts an analog input ...
.
*
Spontaneous parametric down-conversion
Spontaneous parametric down-conversion (also known as SPDC, parametric fluorescence or parametric scattering) is a nonlinear instant optical process that converts one photon of higher energy (namely, a pump photon), into a pair of photons (namely, ...
leading to binary phase state selection in a degenerate
optical parametric oscillator
An optical parametric oscillator (OPO) is a parametric oscillator that oscillates at optical frequencies. It converts an input laser wave (called "pump") with frequency \omega_p into two output waves of lower frequency (\omega_s, \omega_i) by mean ...
.
* Fluctuations in
vacuum energy
Vacuum energy is an underlying background energy that exists in space throughout the entire Universe. The vacuum energy is a special case of zero-point energy that relates to the quantum vacuum.
The effects of vacuum energy can be experiment ...
measured through
homodyne detection
In electrical engineering, homodyne detection is a method of extracting information encoded as modulation of the phase and/or frequency of an oscillating signal, by comparing that signal with a standard oscillation that would be identical to the si ...
.
Classical random properties
Thermal phenomena are easier to detect. They are somewhat vulnerable to attack by lowering the temperature of the system,
though most systems will stop operating at temperatures low enough to reduce noise by a factor of two (e.g., ~150 K). Some of the thermal phenomena used include:
*
Thermal noise
A thermal column (or thermal) is a rising mass of buoyant air, a convective current in the atmosphere, that transfers heat energy vertically. Thermals are created by the uneven heating of Earth's surface from solar radiation, and are an example ...
from a
resistor
A resistor is a passive two-terminal electrical component that implements electrical resistance as a circuit element. In electronic circuits, resistors are used to reduce current flow, adjust signal levels, to divide voltages, bias active el ...
, amplified to provide a random voltage source.
*
Avalanche noise generated from an
avalanche diode
In electronics, an avalanche diode is a diode (made from silicon or other semiconductor) that is designed to experience avalanche breakdown at a specified reverse bias voltage. The junction of an avalanche diode is designed to prevent current co ...
, or
Zener breakdown
In electronics, the Zener effect (employed most notably in the appropriately named Zener diode) is a type of electrical breakdown, discovered by Clarence Melvin Zener. It occurs in a reverse biased p-n diode when the electric field enables tunn ...
noise from a reverse-biased
Zener diode
A Zener diode is a special type of diode designed to reliably allow current to flow "backwards" (inverted polarity) when a certain set reverse voltage, known as the ''Zener voltage'', is reached.
Zener diodes are manufactured with a great varie ...
.
*
Atmospheric noise
Atmospheric noise is radio noise caused by natural atmospheric processes, primarily lightning discharges in thunderstorms. On a worldwide scale, there are about 40 lightning flashes per second – ≈3.5 million lightning discharges ...
, detected by a radio receiver attached to a PC (though much of it, such as lightning noise, is not properly thermal noise, but most likely a
chaotic
Chaotic was originally a Danish trading card game. It expanded to an online game in America which then became a television program based on the game. The program was able to be seen on 4Kids TV (Fox affiliates, nationwide), Jetix, The CW4Kid ...
phenomenon).
In the absence of quantum effects or thermal noise, other phenomena that tend to be random, although in ways not easily characterized by laws of physics, can be used. When several such sources are combined carefully (as in, for example, the
Yarrow algorithm
The Yarrow algorithm is a family of cryptographic pseudorandom number generators (CPRNG) devised by John Kelsey, Bruce Schneier, and Niels Ferguson and published in 1999. The Yarrow algorithm is explicitly unpatented, royalty-free, and open sour ...
or
Fortuna
Fortuna ( la, Fortūna, equivalent to the Greek goddess Tyche) is the goddess of fortune and the personification of luck in Roman religion who, largely thanks to the Late Antique author Boethius, remained popular through the Middle Ages until at ...
CSPRNGs), enough entropy can be collected for the creation of cryptographic keys and
nonces, though generally at restricted rates. The advantage is that this approach needs, in principle, no special hardware. The disadvantage is that a sufficiently knowledgeable attacker can surreptitiously modify the software or its inputs, thus reducing the randomness of the output, perhaps substantially. The primary source of randomness typically used in such approaches is the precise timing of the
interrupt
In digital computers, an interrupt (sometimes referred to as a trap) is a request for the processor to ''interrupt'' currently executing code (when permitted), so that the event can be processed in a timely manner. If the request is accepted, ...
s caused by mechanical input/output devices, such as keyboards and
disk drive
Disk storage (also sometimes called drive storage) is a general category of storage mechanisms where data is recorded by various electronic, magnetic, optical, or mechanical changes to a surface layer of one or more rotating disks. A disk drive is ...
s, various system information counters, etc.
This last approach must be implemented carefully and may be subject to attack if it is not. For instance, the forward-security of the generator in Linux 2.6.10 kernel could be broken with 2
64 or 2
96 time complexity.
Clock drift
Another variable physical phenomenon that is easy to measure is clock drift.
There are several ways to measure and use clock drift as a source of randomness.
The
Intel
Intel Corporation is an American multinational corporation and technology company headquartered in Santa Clara, California. It is the world's largest semiconductor chip manufacturer by revenue, and is one of the developers of the x86 seri ...
82802 Firmware Hub (FWH) chip included a hardware RNG using two free running oscillators, one fast and one slow. A thermal noise source (non-commonmode noise from two diodes) is used to modulate the frequency of the slow oscillator, which then triggers a measurement of the fast oscillator. That output is then debiased using a
von Neumann Von Neumann may refer to:
* John von Neumann (1903–1957), a Hungarian American mathematician
* Von Neumann family
* Von Neumann (surname), a German surname
* Von Neumann (crater), a lunar impact crater
See also
* Von Neumann algebra
* Von Ne ...
type decorrelation step (see below). The output rate of this device is somewhat less than 100,000 bit/s. This chip was an optional component of the 840 chipset family that supported an earlier Intel bus. It is not included in modern PCs.
All
VIA C3
The VIA C3 is a family of x86 central processing units for personal computers designed by Centaur Technology and sold by VIA Technologies. The different CPU cores are built following the design methodology of Centaur Technology.
In addition to ...
microprocessors have included a hardware RNG on the processor chip since 2003. Instead of using thermal noise, raw bits are generated by using four freerunning oscillators which are designed to run at different rates. The output of two are XORed to control the bias on a third oscillator, whose output clocks the output of the fourth oscillator to produce the raw bit. Minor variations in temperature, silicon characteristics, and local electrical conditions cause continuing oscillator speed variations and thus produce the entropy of the raw bits. To further ensure randomness, there are actually two such RNGs on each chip, each positioned in different environments and rotated on the silicon. The final output is a mix of these two generators. The raw output rate is tens to hundreds of megabits per second, and the whitened rate is a few megabits per second. User software can access the generated random bit stream using new non-privileged machine language instructions.
A software implementation of a related idea on ordinary hardware is included in CryptoLib, a cryptographic routine library. The algorithm is called ''
truerand''. Most modern computers have two crystal oscillators, one for the real-time clock and one for the primary CPU clock; truerand exploits this fact. It uses an operating system service that sets an alarm, running off the real-time clock. One subroutine sets that alarm to go off in one clock tick (usually 1/60th of a second). Another then enters a while loop waiting for the alarm to trigger. Since the alarm will not always trigger in exactly one tick, the least significant bits of a count of loop iterations, between setting the alarm and its trigger, will vary randomly, possibly enough for some uses. Truerand doesn't require additional hardware, but in a multi-tasking system great care must be taken to avoid non-randomizing interference from other processes (e.g., in the suspension of the counting loop process as the operating system scheduler starts and stops assorted processes).
The
RDRAND
RDRAND (for "read random"; known as Intel Secure Key Technology, previously known as Bull Mountain) is an instruction for returning random numbers from an Intel on-chip hardware random number generator which has been seeded by an on-chip entropy s ...
opcode will return values from an onboard hardware random number generator. It is present in Intel
Ivy Bridge processors and AMD64 processors since 2015.
Dealing with bias
The bit-stream from such systems can be prone to be biased, with either 1s or 0s predominating. There are two approaches to dealing with bias and other artifacts. The first is to design the RNG to minimize bias inherent in the operation of the generator. One method to correct this feeds back the generated bit stream, filtered by a low-pass filter, to adjust the bias of the generator. By the
central limit theorem
In probability theory, the central limit theorem (CLT) establishes that, in many situations, when independent random variables are summed up, their properly normalized sum tends toward a normal distribution even if the original variables themselv ...
, the feedback loop will tend to be well-adjusted '
almost all the time'. Ultra-high speed random number generators often use this method. Even then, the numbers generated are usually somewhat biased.
Software whitening
A second approach to coping with bias is to reduce it after generation (in software or hardware). There are several techniques for reducing bias and correlation, often called "
whitening" algorithms, by analogy with the related problem of producing white noise from a correlated signal.
John von Neumann
John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest cove ...
invented a simple algorithm to fix simple bias and reduce correlation. It considers two bits at a time (non-overlapping), taking one of three actions: when two successive bits are equal, they are discarded; a sequence of 1,0 becomes a 1; and a sequence of 0,1 becomes a zero. It thus represents a
falling edge with a 1, and a
rising edge with a 0. This eliminates simple bias, and is easy to implement as a computer program or in digital logic. This technique works no matter how the bits have been generated. It cannot assure randomness in its output, however. What it can do (with significant numbers of discarded bits) is transform a biased random bit stream into an unbiased one.
Another technique for improving a near random bit stream is to
exclusive-or
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , ...
the bit stream with the output of a high-quality
cryptographically secure pseudorandom number generator
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely kno ...
such as
Blum Blum Shub
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.
__TOC__
Blum Blum Shub takes the form
:x_ = x_n^2 \bmod M,
where ...
or a strong
stream cipher
stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
. This can improve decorrelation and digit bias at low cost; it can be done by hardware, such as a
field-programmable gate array
A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware d ...
, which is faster than doing it by software.
A related method which reduces bias in a near random bit stream is to take two or more uncorrelated near random bit streams, and
exclusive or
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
them together. Let the probability of a bit stream producing a 0 be 1/2 + ''e'', where −1/2 ≤ ''e'' ≤ 1/2. Then ''e'' is the bias of the bitstream. If two uncorrelated bit streams with bias ''e'' are exclusive-or-ed together, then the bias of the result will be 2''e''
2. This may be repeated with more bit streams (see also the
Piling-up lemma
In cryptanalysis, the piling-up lemma is a principle used in linear cryptanalysis to construct linear approximation, linear approximations to the action of block ciphers. It was introduced by Mitsuru Matsui (1993) as an analytical tool for linear c ...
).
Some designs apply cryptographic
hash function
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually u ...
s such as
MD5,
SHA-1
In cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecima ...
, or
RIPEMD-160 or even a
CRC function to all or part of the bit stream, and then use the output as the random bit stream. This is attractive, partly because it is relatively fast.
Many physical phenomena can be used to generate bits that are highly biased, but each bit is independent from the others.
A Geiger counter (with a sample time longer than the tube recovery time) or a semi-transparent mirror photon detector both generate bit streams that are mostly "0" (silent or transmission) with the occasional "1" (click or reflection).
If each bit is independent from the others, the Von Neumann strategy generates one random, unbiased output bit for each of the rare "1" bits in such a highly biased bit stream.
Whitening techniques such as the Advanced Multi-Level Strategy (AMLS) can extract more output bits – output bits that are just as random and unbiased – from such a highly biased bit stream.
PRNG with periodically refreshed random key
Other designs use what are believed to be true random bits as the
key
Key or The Key may refer to:
Common meanings
* Key (cryptography), a piece of information that controls the operation of a cryptography algorithm
* Key (lock), device used to control access to places or facilities restricted by a lock
* Key (map ...
for a high quality
block cipher
In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
algorithm, taking the encrypted output as the random bit stream. Care must be taken in these cases to select an appropriate
block mode, however. In some implementations, the PRNG is run for a limited number of digits, while the hardware generating device produces a new seed.
Using observed events
Software engineers without true random number generators often try to develop them by measuring physical events available to the software. An example is measuring the time between user keystrokes, and then taking the least significant bit (or two or three) of the count as a random digit. A similar approach measures task-scheduling, network hits, disk-head seek times and other internal events. One Microsoft design includes a very long list of such internal values, a form of
cryptographically secure pseudorandom number generator
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely kno ...
.
Lava lamp
A lava lamp is a decorative lamp, invented in 1963 by British entrepreneur Edward Craven Walker, the founder of the lighting company Mathmos. It consists of a bolus of a special coloured wax mixture inside a glass vessel, the remainder of which ...
s have also been used as the physical devices to be monitored, as in the
Lavarand system.
The method is risky when it uses computer-controlled events because a clever, malicious attacker might be able to predict a cryptographic key by controlling the external events. It is also risky because the supposed user-generated event (e.g., keystrokes) can be
spoofed by a sufficiently ingenious attacker, allowing control of the "random values" used by the cryptography.
However, with sufficient care, a system can be designed that produces cryptographically secure random numbers from the sources of randomness available in a modern computer. The basic design is to maintain an "entropy pool" of random bits that are assumed to be unknown to an attacker. New randomness is added whenever available (for example, when the user hits a key) and an estimate of the number of bits in the pool that cannot be known to an attacker is kept. Some of the strategies in use include:
* When random bits are requested, return that many bits derived from the entropy pool (by a cryptographic hash function, say) and decrement the estimate of the number of random bits remaining in the pool. If not enough unknown bits are available, wait until enough are available. This is the top-level design of the "
/dev/random" device in Linux, written by
Theodore Ts'o
Theodore (Ted) Yue Tak Ts'o (曹子德) (born 1968) is an American software engineer mainly known for his contributions to the Linux kernel, in particular his contributions to file systems. He is the Secondary developer and maintainer of e2fs ...
and used in many other Unix-like operating systems. It provides high-quality random numbers so long as the estimates of the input randomness are sufficiently cautious. The Linux "/dev/urandom" device is a simple modification which disregards estimates of input randomness, and is therefore rather less likely to have high entropy as a result.
* Maintain a
stream cipher
stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
with a key and
initialization vector
In cryptography, an initialization vector (IV) or starting variable (SV) is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to ...
(IV) obtained from an entropy pool. When enough bits of entropy have been collected, replace both key and IV with new random values and decrease the estimated entropy remaining in the pool. This is the approach taken by the
yarrow
''Achillea millefolium'', commonly known as yarrow () or common yarrow, is a flowering plant in the family Asteraceae. Other common names include old man's pepper, devil's nettle, sanguinary, milfoil, soldier's woundwort, and thousand seal.
The ...
library. It provides resistance against some attacks and conserves hard-to-obtain entropy.
Online systems
A true random number generator can be offered as a centralized online service. One example is the ''randomness beacon service'' from the
National Institute of Standards and Technology
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sci ...
; another example is
Random.org, a service that uses atmospheric noise to generate random
binary digits (bits).
Such online services can also be decentralized. For example, the Cardano platform uses the participants of their decentralized
proof-of-stake
Proof-of-stake (PoS) protocols are a class of consensus mechanisms for blockchain
A blockchain is a type of distributed ledger technology (DLT) that consists of growing lists of records, called ''blocks'', that are securely linked togethe ...
protocol to generate random numbers.
Another decentralized service was launched in 2019 via the ''
League of Entropy.'' It combines random inputs from a variety of sources, via open source ''drand'' software which minimizes the amount of trust users need to have.
Problems
It is very easy to misconstruct hardware or software devices which attempt to generate random numbers. Also, most 'break' silently, often producing decreasingly random numbers as they degrade. A physical example might be the rapidly decreasing radioactivity of the smoke detectors mentioned earlier, if this source were used directly. Failure modes in such devices are plentiful and are complicated, slow, and hard to detect. Methods that combine multiple sources of entropy are more robust.
Because many entropy sources are often quite fragile, and fail silently, statistical tests on their output should be performed continuously. Many, but not all, such devices include some such tests into the software that reads the device.
Attacks
Just as with other components of a cryptography system, a software random number generator should be designed to resist
certain attacks. Defending against these attacks is difficult without a hardware entropy source.
Estimating entropy
There are mathematical techniques for estimating the
entropy
Entropy is a scientific concept, as well as a measurable physical property, that is most commonly associated with a state of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodynam ...
of a sequence of symbols. None are so reliable that their estimates can be fully relied upon; there are always assumptions which may be very difficult to confirm. These are useful for determining if there is enough entropy in a seed pool, for example, but they cannot, in general, distinguish between a true random source and a pseudorandom generator. This problem is avoided by the conservative use of hardware entropy sources.
Performance test
Hardware random number generators should be constantly monitored for proper operation. RFC 4086,
FIPS Pub 140-2 and
NIST
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sci ...
Special Publication 800-90b
Elaine Barker and John Kelsey,'' Recommendation for the Entropy Sources Used for Random Bit Generation,'' NIST SP 800-90b
/ref> include tests which can be used for this. Also see the documentation for the New Zealand cryptographic software library cryptlib
cryptlib is an open-source cross-platform software security toolkit library. It is distributed under the Sleepycat License, a free software license compatible with the GNU General Public License. Alternatively, cryptlib is available under a pr ...
.
Since many practical designs rely on a hardware source as an input, it will be useful to at least check that the source is still operating. Statistical tests can often detect failure of a noise source, such as a radio station transmitting on a channel thought to be empty, for example. Noise generator output should be sampled for testing before being passed through a "whitener." Some whitener designs can pass statistical tests with no random input. While detecting a large deviation from perfection would be a sign that a true random noise source has become degraded, small deviations are normal and can be an indication of proper operation. Correlation of bias in the inputs to a generator design with other parameters (e.g., internal temperature, bus voltage) might be additionally useful as a further check. Unfortunately, with currently available (and foreseen) tests, passing such tests is not enough to be sure the output sequences are random. A carefully chosen design, verification that the manufactured device implements that design and continuous physical security to insure against tampering may all be needed in addition to testing for high value uses.
See also
* AN/CYZ-9
* Bell test experiments
A Bell test, also known as Bell inequality test or Bell experiment, is a real-world physics experiment designed to test the theory of quantum mechanics in relation to Albert Einstein's concept of local realism. Named for John Stewart Bell, the e ...
* /dev/random
* ERNIE
Ernie is a masculine given name, frequently a short form (hypocorism) of Ernest, Ernald, Ernesto, or Verner. It may refer to:
People
* Ernie Accorsi (born 1941), American football executive
* Ernie Adams (disambiguation)
* Ernie Afaganis (born c ...
* List of random number generators
Random number generators are important in many kinds of technical applications, including physics, engineering or mathematical computer studies (e.g., Monte Carlo simulations), cryptography and gambling (on game servers).
This list includes many c ...
* Lottery machine
A lottery is a form of gambling that involves the drawing of numbers at random for a prize. Some governments outlaw lotteries, while others endorse it to the extent of organizing a national or state lottery. It is common to find some degree of ...
* Randomness extractor A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random information entropy, entropy source, together with a short, uniformly random seed, generates a highly random output that ap ...
* RDRAND
RDRAND (for "read random"; known as Intel Secure Key Technology, previously known as Bull Mountain) is an instruction for returning random numbers from an Intel on-chip hardware random number generator which has been seeded by an on-chip entropy s ...
* Trusted Platform Module
Trusted Platform Module (TPM, also known as ISO/IEC 11889) is an international standard for a secure cryptoprocessor, a dedicated microcontroller designed to secure hardware through integrated cryptographic keys. The term can also refer to a ch ...
References
General references
* .
* .
* .
* .
* .
* .
External links
* .
* .
ProtegoST SG100
ProtegoST, "Hardware Random Number Generator "Based on quantum physics random number source from a zener diode".
{{DEFAULTSORT:Hardware Random Number Generator
Cryptography
Random number generation
Computer peripherals
de:Zufallszahlengenerator#Physikalischer Zufallszahlengenerator