![Two red dice 01](https://upload.wikimedia.org/wikipedia/commons/3/36/Two_red_dice_01.svg)
Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of
number
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers c ...
s or
symbols that cannot be reasonably predicted better than by
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual ra ...
chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but unpredictable to foresight. True random number generators can be ''
hardware random-number generators'' (HRNGS) that generate random numbers, wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by ''
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) that generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.
Various
applications of randomness
Randomness has many uses in science, art, statistics, cryptography, gaming, gambling, and other fields. For example, random assignment in randomized controlled trials helps scientists to test hypotheses, and random numbers or pseudorandom numb ...
have led to the development of several different methods for generating
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual ra ...
data. Some of these have existed since ancient times, among whose ranks are well-known "classic" examples, including the rolling of
dice,
coin flipping
Coin flipping, coin tossing, or heads or tails is the practice of throwing a coin in the air and checking which side is showing when it lands, in order to choose between two alternatives, heads or tails, sometimes used to resolve a dispute betwe ...
, the
shuffling
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 ...
of
playing card
A playing card is a piece of specially prepared card stock, heavy paper, thin cardboard, plastic-coated paper, cotton-paper blend, or thin plastic that is marked with distinguishing motifs. Often the front (face) and back of each card has a f ...
s, the use of
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 ...
stalks (for
divination) in the
I Ching, as well as countless other techniques. Because of the mechanical nature of these techniques, generating large quantities of sufficiently random numbers (important in statistics) required much work and time. Thus, results would sometimes be collected and distributed as
random number table
Random number tables have been used in statistics for tasks such as selected randomness, random samples. This was much more effective than manually selecting the random samples (with dice, cards, etc.). Nowadays, tables of random numbers have been ...
s.
Several computational methods for pseudorandom number generation exist. All fall short of the goal of true randomness, although they may meet, with varying success, some of the
statistical tests for randomness intended to measure how unpredictable their results are (that is, to what degree their patterns are discernible). This generally makes them unusable for applications such as
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 ...
. However, carefully designed
''cryptographically secure pseudorandom number generators'' (CSPRNGS) also exist, with special features specifically designed for use in cryptography.
Practical applications and uses
Random number generators have applications 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 ...
,
statistical sampling,
computer simulation,
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 ...
,
completely randomized design In the design of experiments, completely randomized designs are for studying the effects of one primary factor without the need to take other nuisance variables into account. This article describes completely randomized designs that have one primar ...
, and other areas where producing an unpredictable result is desirable. Generally, in applications having unpredictability as the paramount feature, such as in security applications,
hardware generators are generally preferred over pseudorandom algorithms, where feasible.
Pseudorandom number generators are very useful in developing
Monte Carlo-method simulations, as
debugging is facilitated by the ability to run the same sequence of random numbers again by starting from the same ''
random seed
A random seed (or seed state, or just seed) is a number (or vector) used to initialize a pseudorandom number generator.
For a seed to be used in a pseudorandom number generator, it does not need to be random. Because of the nature of number gene ...
''. They are also used in cryptography – so long as the ''seed'' is secret. Sender and receiver can generate the same set of numbers automatically to use as keys.
The generation of
pseudorandom number
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process.
Background
The generation of random numbers has many uses, such as for random ...
s is an important and common task in computer programming. While cryptography and certain numerical algorithms require a very high degree of ''apparent'' randomness, many other operations only need a modest amount of unpredictability. Some simple examples might be presenting a user with a "random quote of the day", or determining which way a computer-controlled adversary might move in a computer game. Weaker forms of ''randomness'' are used in
hash algorithm
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 ...
s and in creating
amortized
In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case ...
searching
Searching or search may refer to:
Computing technology
* Search algorithm, including keyword search
** :Search algorithms
* Search and optimization for problem solving in artificial intelligence
* Search engine technology, software for findin ...
and
sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important ...
s.
Some applications which appear at first sight to be suitable for
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 ...
are in fact not quite so simple. For instance, a system that "randomly" selects music tracks for a background music system must only ''appear'' random, and may even have ways to control the selection of music: a true random system would have no restriction on the same item appearing two or three times in succession.
"True" vs. pseudo-random numbers
There are two principal methods used to generate random numbers. The first method measures some physical phenomenon that is expected to be random and then compensates for possible biases in the measurement process. Example sources include measuring
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 ...
, thermal noise, and other external electromagnetic and quantum phenomena. For example, cosmic background radiation or radioactive decay as measured over short timescales represent sources of natural
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 ...
.
The speed at which entropy can be obtained from natural sources is dependent on the underlying physical phenomena being measured. Thus, sources of naturally occurring "true" entropy are said to be
blocking they are rate-limited until enough entropy is harvested to meet the demand. On some Unix-like systems, including most
Linux distributions, the pseudo device file will block until sufficient entropy is harvested from the environment. Due to this blocking behavior, large bulk reads from , such as filling a
hard disk drive
A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magne ...
with random bits, can often be slow on systems that use this type of entropy source.
The second method uses computational
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s that can produce long sequences of apparently random results, which are in fact completely determined by a shorter initial value, known as a seed value or
key. As a result, the entire seemingly random sequence can be reproduced if the seed value is known. This type of random number generator is often called a
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 ...
. This type of generator typically does not rely on sources of naturally occurring entropy, though it may be periodically seeded by natural sources. This generator type is non-blocking, so they are not rate-limited by an external event, making large bulk reads a possibility.
Some systems take a hybrid approach, providing randomness harvested from natural sources when available, and falling back to periodically re-seeded software-based
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 ...
s (CSPRNGs). The fallback occurs when the desired read rate of randomness exceeds the ability of the natural harvesting approach to keep up with the demand. This approach avoids the rate-limited blocking behavior of random number generators based on slower and purely environmental methods.
While a pseudorandom number generator based solely on deterministic logic can never be regarded as a "true" random number source in the purest sense of the word, in practice they are generally sufficient even for demanding security-critical applications. Carefully designed and implemented pseudorandom number generators can be certified for security-critical cryptographic purposes, as is the case with the
yarrow algorithm and
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 ...
. The former is the basis of the source of entropy on
FreeBSD,
AIX
Aix or AIX may refer to:
Computing
* AIX, a line of IBM computer operating systems
*An Alternate Index, for a Virtual Storage Access Method Key Sequenced Data Set
* Athens Internet Exchange, a European Internet exchange point
Places Belgi ...
,
OS X,
NetBSD, and others.
OpenBSD uses a pseudorandom number algorithm known as
arc4random
In cryptography, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, ren ...
.
Generation methods
Physical methods
The earliest methods for generating random numbers, such as dice, coin flipping and roulette wheels, are still used today, mainly in games and gambling as they tend to be too slow for most applications in statistics and cryptography.
A physical random number generator can be based on an essentially random atomic or subatomic physical phenomenon whose unpredictability can be traced to the laws of
quantum mechanics
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 chemistr ...
. Sources of
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 ...
include
radioactive decay,
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 ...
,
shot noise, avalanche noise in
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 var ...
s,
clock drift, the timing of actual movements of a
hard disk read-write head, and
radio noise
In radio reception, radio noise is unwanted random radio frequency electrical signals, fluctuating voltages, always present in a radio receiver in addition to the desired radio signal. Radio noise near in frequency to the radio signal being receive ...
. However, physical phenomena and tools used to measure them generally feature asymmetries and
systematic bias
Systematic may refer to:
Science
* Short for systematic error
* Systematic fault
* Systematic bias, errors that are not determined by chance but are introduced by an inaccuracy (involving either the observation or measurement process) inheren ...
es that make their outcomes not uniformly random. A
randomness extractor A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent fro ...
, such as a
cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output re ...
, can be used to approach a uniform distribution of bits from a non-uniformly random source, though at a lower bit rate.
The appearance of wideband photonic entropy sources, such as
optical chaos and
amplified spontaneous emission Amplified spontaneous emission (ASE) or superluminescence is light, produced by spontaneous emission, that has been optically amplified by the process of stimulated emission in a gain medium. It is inherent in the field of random lasers.
Origins ...
noise, greatly aid the development of the physical random number generator. Among them, optical chaos has a high potential to physically produce high-speed random numbers due to its high bandwidth and large amplitude. A prototype of a high speed, real-time physical random bit generator based on a chaotic laser was built in 2013.
Various imaginative ways of collecting this entropic information have been devised. One technique is to run a hash function against a frame of a video stream from an unpredictable source.
Lavarand used this technique with images of a number of
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
HotBitsmeasures radioactive decay with
Geiger–Muller tubes, while
Random.org uses variations in the amplitude of atmospheric noise recorded with a normal radio.
![Demo_random_SMIL](https://upload.wikimedia.org/wikipedia/commons/7/79/Demo_random_SMIL.svg)
Another common entropy source is the behavior of human users of the system. While people are not considered good randomness generators upon request, they generate random behavior quite well in the context of playing
mixed strategy
In game theory, a player's strategy is any of the options which they choose in a setting where the outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the action of a player in a game ...
games. Some security-related computer software requires the user to make a lengthy series of mouse movements or keyboard inputs to create sufficient entropy needed to generate random
keys or to initialize pseudorandom number generators.
Computational methods
Most computer generated random numbers use PRNGs which are algorithms that can automatically create long runs of numbers with good random properties but eventually the sequence repeats (or the memory usage grows without bound). These random numbers are fine in many situations but are not as random as numbers generated from electromagnetic atmospheric noise used as a source of entropy. The series of values generated by such algorithms is generally determined by a fixed number called a ''
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 ...
''. One of the most common
PRNG is the
linear congruential generator
A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generat ...
, which uses the recurrence
:
to generate numbers, where , and are large integers, and
is the next in as a series of pseudorandom numbers. The maximum number of numbers the formula can produce is the
modulus, . The recurrence relation can be extended to matrices to have much longer periods and better statistical properties
.
To avoid certain non-random properties of a single linear congruential generator, several such random number generators with slightly different values of the multiplier coefficient, , can be used in parallel, with a "master" random number generator that selects from among the several different generators.
A simple pen-and-paper method for generating random numbers is the so-called
middle-square method suggested by
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 ...
. While simple to implement, its output is of poor quality. It has a very short period and severe weaknesses, such as the output sequence almost always converging to zero. A recent innovation is to combine the middle square with a
Weyl sequence. This method produces high quality output through a long period.
Most computer programming languages include functions or library routines that provide random number generators. They are often designed to provide a random byte or word, or a
floating point
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can b ...
number
uniformly distributed between 0 and 1.
The quality i.e. randomness of such library functions varies widely from completely predictable output, to cryptographically secure. The default random number generator in many languages, including Python, Ruby, R, IDL and PHP is based on the
Mersenne Twister
The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by and . Its name derives from the fact that its period length is chosen to be a Mersenne prime.
The Mersenne Twister was designed specifically to re ...
algorithm and is ''not'' sufficient for cryptography purposes, as is explicitly stated in the language documentation. Such library functions often have poor statistical properties and some will repeat patterns after only tens of thousands of trials. They are often initialized using a computer's
real time clock as the seed, since such a clock is 64 bit and measures in nanoseconds, far beyond the person's
precision
Precision, precise or precisely may refer to:
Science, and technology, and mathematics Mathematics and computing (general)
* Accuracy and precision, measurement deviation from true value and its scatter
* Significant figures, the number of digit ...
. These functions may provide enough randomness for certain tasks (for example video games) but are unsuitable where high-quality randomness is required, such as in cryptography applications, statistics or numerical analysis.
Much higher quality random number sources are available on most operating systems; for example
/dev/random
In Unix-like operating systems, and are special files that serve as cryptographically secure pseudorandom number generators. They allow access to environmental noise collected from device drivers and other sources. typically blocked if ther ...
on various BSD flavors, Linux, Mac OS X, IRIX, and Solaris, or
CryptGenRandom
CryptGenRandom is a deprecated cryptographically secure pseudorandom number generator function that is included in Microsoft CryptoAPI. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed. A 2007 paper from ...
for Microsoft Windows. Most programming languages, including those mentioned above, provide a means to access these higher quality sources.
By humans
Random number generation may also be performed by humans, in the form of collecting various inputs from
end users and using them as a randomization source. However, most studies find that human subjects have some degree of non-randomness when attempting to produce a random sequence of e.g. digits or letters. They may alternate too much between choices when compared to a good random generator; thus, this approach is not widely used.
Post-processing and statistical checks
Even given a source of plausible random numbers (perhaps from a quantum mechanically based hardware generator), obtaining numbers which are completely unbiased takes care. In addition, behavior of these generators often changes with temperature, power supply voltage, the age of the device, or other outside interference. And a software bug in a pseudorandom number routine, or a hardware bug in the hardware it runs on, may be similarly difficult to detect.
Generated random numbers are sometimes subjected to statistical tests before use to ensure that the underlying source is still working, and then post-processed to improve their statistical properties. An example would be the TRNG9803 hardware random number generator, which uses an entropy measurement as a hardware test, and then post-processes the random sequence with a shift register stream cipher. It is generally hard to use statistical tests to validate the generated random numbers. Wang and Nicol proposed a distance-based statistical testing technique that is used to identify the weaknesses of several random generators. Li and Wang proposed a method of testing random numbers based on laser chaotic entropy sources using Brownian motion properties.
Other considerations
Reshaping the distribution
Uniform distributions
Most random number generators natively work with integers or individual bits, so an extra step is required to arrive at the "canonical" uniform distribution between 0 and 1. The implementation is not as trivial as dividing the integer by its maximum possible value. Specifically:
# The integer used in the transformation must provide enough bits for the intended precision.
# The nature of floating-point math itself means there exists more precision the closer the number is to zero. This extra precision is usually not used due to the sheer number of bits required.
# Rounding error in division may bias the result. At worst, a supposedly excluded bound may be drawn countrary to expectations based on real-number math.
The mainstream algorithm, used by
OpenJDK
OpenJDK (Open Java Development Kit) is a free and open-source implementation of the Java Platform, Standard Edition (Java SE). It is the result of an effort Sun Microsystems began in 2006. The implementation is licensed under the GPL-2.0-only w ...
,
Rust
Rust is an iron oxide, a usually reddish-brown oxide formed by the reaction of iron and oxygen in the catalytic presence of water or air moisture. Rust consists of hydrous iron(III) oxides (Fe2O3·nH2O) and iron(III) oxide-hydroxide (FeO( ...
, and
NumPy, is described in a proposal for
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
's STL. It does not use the extra precision and suffers from bias only in the last bit due to round-to-even. Other numeric concerns are warranted when shifting this "canonical" uniform distribution to a different range. A proposed method for the
Swift programming language claims to use the full precision everywhere.
Uniformly distributed integers are commonly used in algorithms such as the
Fisher–Yates shuffle. Again, a naive implementation may induce a modulo bias into the result, so more involved algorithms must be used. A method that nearly never performs division was described in 2018 by Daniel Lemire, with the current state-of-the-art being the arithmetic encoding-inspired 2021 "optimal algorithm" by Stephen Canon of
Apple Inc.
Apple Inc. is an American multinational technology company headquartered in Cupertino, California, United States. Apple is the largest technology company by revenue (totaling in 2021) and, as of June 2022, is the world's biggest company ...
Most 0 to 1 RNGs include 0 but exclude 1, while others include or exclude both.
Other distributions
Given a source of uniform random numbers, there are a couple of methods to create a new random source that corresponds to a
probability density function
In probability theory, a probability density function (PDF), or density of a continuous random variable, is a function whose value at any given sample (or point) in the sample space (the set of possible values taken by the random variable) ca ...
. One method, called the
inversion method
Inverse transform sampling (also known as inversion sampling, the inverse probability integral transform, the inverse transformation method, Smirnov transform, or the golden ruleAalto University, N. Hyvönen, Computational methods in inverse probl ...
, involves integrating up to an area greater than or equal to the random number (which should be generated between 0 and 1 for proper distributions). A second method, called the
acceptance-rejection method, involves choosing an x and y value and testing whether the function of x is greater than the y value. If it is, the x value is accepted. Otherwise, the x value is rejected and the algorithm tries again.
->
As an example for rejection sampling, to generate a pair of
Statistical independence, statistically independent standard normally distributed random numbers (''x'', ''y''), one may first generate the
polar coordinates
In mathematics, the polar coordinate system is a two-dimensional coordinate system in which each point on a plane is determined by a distance from a reference point and an angle from a reference direction. The reference point (analogous to th ...
(''r'', ''θ''), where ''r''
2~
χ22 and ''θ''~
UNIFORM(0,2π) (see
Box–Muller transform
The Box–Muller transform, by George Edward Pelham Box and Mervin Edgar Muller, is a random number sampling method for generating pairs of independent, standard, normally distributed (zero expectation, unit variance) random numbers, given a ...
).
Whitening
The outputs of multiple independent RNGs can be combined (for example, using a bit-wise
XOR operation) to provide a combined RNG at least as good as the best RNG used. This is referred to as
software whitening.
Computational and hardware random number generators are sometimes combined to reflect the benefits of both kinds. Computational random number generators can typically generate pseudorandom numbers much faster than physical generators, while physical generators can generate "true randomness."
Low-discrepancy sequences as an alternative
Some computations making use of a random number generator can be summarized as the computation of a total or average value, such as the computation of integrals by the
Monte Carlo method
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be determi ...
. For such problems, it may be possible to find a more accurate solution by the use of so-called
low-discrepancy sequence In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of ''N'', its subsequence ''x''1, ..., ''x'N'' has a low discrepancy.
Roughly speaking, the discrepancy of a sequence is low if the proportion of poi ...
s, also called
quasirandom numbers. Such sequences have a definite pattern that fills in gaps evenly, qualitatively speaking; a truly random sequence may, and usually does, leave larger gaps.
Activities and demonstrations
The following sites make available random number samples:
* The
SOCR resource pages contain a number of hands-on interactive activities and demonstrations of random number generation using Java applets.
* The Quantum Optics Group at the
ANU generates random numbers sourced from quantum vacuum. Sample of random numbers are available at their quantum random number generator research page.
* Random.org makes available random numbers that are sourced from the randomness of atmospheric noise.
* The Quantum Random Bit Generator Service at the
Ruđer Bošković Institute
The Ruđer Bošković Institute (RBI; hr, Institut Ruđer Bošković, , IRB) is a research institute located in the Šalata neighborhood of Zagreb, Croatia, founded in 1950, which studies the sciences.
Description
It is the largest Croatian resea ...
harvests randomness from the quantum process of photonic emission in semiconductors. They supply a variety of ways of fetching the data, including libraries for several programming languages.
* The Group at the Taiyuan University of Technology generates random numbers sourced from a chaotic laser. Samples of random number are available at their Physical Random Number Generator Service.
Backdoors
Since much cryptography depends on a cryptographically secure random number generator for key and
cryptographic nonce
In cryptography, a nonce is an arbitrary number that can be used just once in a cryptographic communication. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused in ...
generation, if a random number generator can be made predictable, it can be used as
backdoor
A back door is a door in the rear of a building. Back door may also refer to:
Arts and media
* Back Door (jazz trio), a British group
* Porta dos Fundos (literally “Back Door” in Portuguese) Brazilian comedy YouTube channel.
* Works so titl ...
by an attacker to break the encryption.
The NSA is reported to have inserted a backdoor into the
NIST certified
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 ...
Dual EC DRBG
Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public crit ...
. If for example an SSL connection is created using this random number generator, then according to
Matthew Green it would allow NSA to determine the state of the random number generator, and thereby eventually be able to read all data sent over the SSL connection. Even though it was apparent that Dual_EC_DRBG was a very poor and possibly backdoored pseudorandom number generator long before the NSA backdoor was confirmed in 2013, it had seen significant usage in practice until 2013, for example by the prominent security company
RSA Security
RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rive ...
.
There have subsequently been accusations that RSA Security knowingly inserted a NSA backdoor into its products, possibly as part of the
Bullrun program
Bullrun (stylized BULLRUN) is a clandestine, highly classified program to crack encryption of online communications and data, which is run by the United States National Security Agency (NSA). The British Government Communications Headquarters ...
. RSA has denied knowingly inserting a backdoor into its products.
It has also been theorized that hardware RNGs could be secretly modified to have less entropy than stated, which would make encryption using the hardware RNG susceptible to attack. One such method which has been published works by modifying the dopant mask of the chip, which would be undetectable to optical reverse-engineering. For example, for random number generation in Linux, it is seen as unacceptable to use Intel's
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 ...
hardware RNG without mixing in the RDRAND output with other sources of entropy to counteract any backdoors in the hardware RNG, especially after the revelation of the NSA Bullrun program.
In 2010,
a U.S. lottery draw was rigged by the information security director of the
Multi-State Lottery Association
The Multi-State Lottery Association (MUSL) is an American non-profit, government-benefit association owned and operated by agreement of its 34 member lotteries. MUSL was created to facilitate the operation of multi-jurisdictional lottery games, ...
(MUSL), who surreptitiously installed backdoor
malware on the MUSL's secure RNG computer during routine maintenance.
During the hacks the man won a total amount of $16,500,000 by predicting the numbers correctly a few times in year.
Address space layout randomization
Address space layout randomization (ASLR) is a computer security technique involved in preventing exploitation of memory corruption vulnerabilities. In order to prevent an attacker from reliably jumping to, for example, a particular exploited f ...
(ASLR), a mitigation against rowhammer and related attacks on the physical hardware of memory chips has been found to be inadequate as of early 2017 by VUSec. The random number algorithm, if based on a shift register implemented in hardware, is predictable at sufficiently large values of p and can be reverse engineered with enough processing power (
Brute Force Hack).
This also indirectly means that malware using this method can run on both GPUs and CPUs if coded to do so, even using GPU to break ASLR on the CPU itself.
See also
*
Flipism
Flipism, sometimes spelled "flippism", is a pseudophilosophy under which decisions are made by flipping a coin. It originally appeared in the ''Donald Duck'' Disney comic "Flip Decision" by Carl Barks, published in 1953. Barks called a practitio ...
*
League of entropy
*
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 ...
*
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. ...
*
Procedural generation
In computing, procedural generation is a method of creating data algorithmically as opposed to manually, typically through a combination of human-generated assets and algorithms coupled with computer-generated randomness and processing power. In ...
*
Randomized algorithm
*
Random password generator
A random password generator is software program or hardware device that takes input from a random or pseudo-random number generator and automatically generates a password. Random passwords can be generated manually, using simple sources of rando ...
*
Random variable, contains a chance-dependent value
References
Further reading
*
*
*
*
*
NIST SP800-90A, B, C series on random number generation*
External links
RANDOM.ORGTrue Random Number Service
Quantum random number generatorat ANU
*
jRanda Java-based framework for the generation of simulation sequences, including pseudorandom sequences of numbers
Randomness Beaconat
NIST, broadcasting full-entropy bit-strings in blocks of 512 bits every 60 seconds. Designed to provide unpredictability, autonomy, and consistency.
A system call for random numbers: getrandom() a
LWN.net
LWN.net is a computing webzine with an emphasis on free software and software for Linux and other Unix-like operating systems. It consists of a weekly issue, separate stories which are published most days, and threaded discussion attached to ...
article describing a dedicated Linux system call
Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSLRandom Sequence Generator based on Avalanche Noise
{{Authority control
Information theory