In computing, a hardware random number generator is an apparatus that generates random numbers from a physical process. Such devices are often based on microscopic phenomena such as thermal noise or the photoelectric effect or other quantum phenomena. These processes are, in theory, completely unpredictable, and the theory's assertions of unpredictability are subject to experimental test. A quantum-based hardware random number generator typically contains an amplifier to bring the output of the physical process into the macroscopic realm, and a transducer to convert the output into a digital signal. RAM (Random Access Memory) Look up computing in Wiktionary, the free dictionary. ... Random number may refer to: A number generated for or part of a set exhibiting statistical randomness. ... Johnson-Nyquist noise (sometimes thermal noise, Johnson noise or Nyquist noise) is the noise generated by the equilibrium fluctuations of the electric current inside an electrical conductor, which happens without any applied voltage, due to the random thermal motion of the charge carriers (the electrons). ... A diagram illustrating the emission of electrons from a metal plate, requiring energy gained from an incoming photon to be more than the work function of the material. ... In physics, a quantum (plural: quanta) is an indivisible entity of energy. ... For the British rock band of the same name, see Amplifier (band). ... Macroscopic is commonly used to describe physical objects that are measurable and observable by the naked eye. ... A transducer is a device, usually electrical or electronic, that converts one type of energy to another. ...

Random number generators can also be built from macroscopic phenomena, such as playing cards, dice, and the roulette wheel. The presence of unpredictability in these phenomena can be justified by the theory of unstable dynamical systems and chaos theory. These theories suggest that even though macroscopic phenomena are deterministic in theory under Newtonian mechanics, real-world systems evolve in ways that cannot be predicted in practice because one would need to know the micro-details of initial conditions and subsequent manipulation or change. Some typical modern playing cards. ... Dice (the plural of die, from Old French de, from Latin datum something given or played [1]) are small polyhedral objects, usually cubical, used for generating random numbers or other symbols. ... Roulette is a casino and gambling game named after the French word meaning small wheel. In the game a croupier spins a wheel in one direction, then spins a ball in the opposite direction around a tilted circular surface running around the circumference of the wheel. ... The Lorenz attractor is an example of a non-linear dynamical system. ... For other uses, see Chaos Theory (disambiguation). ... It has been suggested that this article or section be merged with Classical mechanics. ...

Although dice have been mostly used in gambling, and in recent times as 'randomizing' elements in games (e.g. role playing games), the Victorian scientist Francis Galton described a way to use dice to explicitly generate random numbers for scientific purposes, in 1890. Though some gamblers believe they can control their throws of dice enough to win at dice games (a claim which has been long debated), no one has produced a way to exploit the claimed effect in either generating or attacking physical randomness sources. Caravaggio, The Cardsharps, c. ... This article is about traditional role-playing games. ... Queen Victoria (shown here on the morning of her accession to the Throne, 20 June 1837) gave her name to the historic era The Victorian era of the United Kingdom marked the height of the British Industrial Revolution and the apex of the British Empire. ... This article does not cite any references or sources. ... ...

Hardware random number generators are often relatively slow, and they may produce a biased sequence (i.e., some values are more common than others). Whether a hardware random number generator is suitable for a particular application depends on the details of both the application and the generator.

Pseudo-random generators

Main article: Pseudorandom number generator

Most computer "random number generators" are not hardware devices, but are software routines implementing generator algorithms. They are often supplied as library routines in programming language implementations, or as part of the operating system. These are more properly called pseudo-random number generators, since, being finite state machines, they cannot produce truly random outputs. Within that limitation, some produce sequences which pass one or several statistical pattern tests for randomness, and may be useful in many circumstances. Several common ones are very poor, not only failing to pass many of the relevant statistical tests, but also being readily, even trivially, predictable. A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... In computer science, a library is a collection of subprograms used to develop software. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... // An operating system (OS) is the software that manages the sharing of the resources of a computer. ... A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ... Fig. ...

Algorithmic information theory defines a sequence of bits as non-random if it can be produced by some computer program that is shorter than that sequence (Chaitin-Kolmogorov randomness). Pseudo-random number generators fail that test dramatically. They can usually be programmed in a few thousand bits, but can produce far larger sequences, with periods so long no plausible computer or combination of them could exhaust a single period before the heat death of the Universe. This article or section is in need of attention from an expert on the subject. ... This article is about the unit of information. ... It has been suggested that this article or section be merged with Kolmogorov complexity. ... The heat death is a possible final state of the universe, in which it has reached maximum entropy. ...

There are several informal definitions of randomness, usually based on either a lack of discernible patterns in a sequence, or the unpredictability of the sequence or various aspects of it by, generally, the most puissant possible adversary. Output from well-designed pseudo-random number generators should pass assorted statistical tests probing for non-randomness (see NIST Special Publication 800-22, Knuth, The Art of Computer Programming, vol. 2, and RFC 4086 for details of many such tests). “Random” redirects here. ... This article does not cite any references or sources. ... As a non-regulatory agency of the United States Department of Commerce’s Technology Administration, the National Institute of Standards (NIST) develops and promotes measurement, standards, and technology to enhance productivity, facilitate trade, and improve the quality of life. ... Donald Knuth Donald Ervin Knuth (born January 10, 1938) is a renowned computer scientist and Professor Emeritus at Stanford University. ... Cover of books The Art of Computer Programming[1] is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ...

The sequences such generators produce always have patterns, in one sense, since the algorithm that generates them has a finite state, and must, eventually, repeat one of those states. Given the original state of the generator, and the implementation of the algorithm, a pseudo-random number generator of this sort is totally predictable. Given even partial knowledge of that state, they are often insecure for many purposes. On the other hand, it has become relatively easy to produce pseudo-random number generators that are guaranteed not to repeat on any conceivable computer within a time-frame that is millions of times longer than the age of the universe. It is an open question whether it is always possible, in some practical way, to distinguish the output of such a pseudo-random number generator from that of a perfectly random source, without knowledge of the generator's internal state. Much of modern cryptography rests on the assumption that ciphers can be constructed whose output is indistinguishable from random noise without knowledge of a secret key used in the algorithm. The age of the universe, in Big Bang cosmology, refers to the time elapsed between the Big Bang and the present day. ... This article is about algorithms for encryption and decryption. ... A key is a piece of information that controls the operation of a cryptography algorithm. ...

Uses

Main article: Applications of randomness

Unpredictable random numbers were first investigated in the context of gambling, and many randomizing devices such as dice, shuffling playing cards, and roulette wheels, were first developed for use in gambling. Fairly produced random numbers are vital to electronic gambling and ways of creating them are sometimes regulated by governmental gaming commissions. Randomness has many uses in gambling, divination, statistics, cryptography, art, etc. ... Caravaggio, The Cardsharps, c. ... Dice (the plural of die, from Old French de, from Latin datum something given or played [1]) are small polyhedral objects, usually cubical, used for generating random numbers or other symbols. ... The term shuffle can also refer to the act of dragging ones feet on the ground while walking, running, or dancing. ... Roulette is a casino and gambling game named after the French word meaning small wheel. In the game a croupier spins a wheel in one direction, then spins a ball in the opposite direction around a tilted circular surface running around the circumference of the wheel. ...

Random numbers are also used for non-gambling purposes, both where their use is mathematically important, such as sampling for opinion polls, and in situations where fairness is approximated by randomization, such as selecting jurors and military draft lotteries. Their use is antique as well. In the Book of Numbers (33:54), Moses commands the Israelites to apportion the land by lot (גורל). And the drawing of lots, often pottery shards, are well attested in the Classical world of Greece and Rome. Some of these very shards have been archeologically recovered. An opinion poll is a survey of opinion from a particular sample. ... Randomization is the process of making something random; this can mean: Generating a random permutation of a sequence (such as when shuffling cards). ... This article is confusing for some readers, and needs to be edited for clarity. ... It has been suggested that this article be split into multiple articles accessible from a disambiguation page. ... The Book of Numbers is the fourth of the books of the Pentateuch, called in the Hebrew ba-midbar במדבר, i. ... Moses with the Tablets, 1659, by Rembrandt This article is about the Biblical figure. ...

Early attempts

One early way of producing random numbers was by a variation of the same machines used to play keno or select lottery numbers. Basically, these mixed numbered ping-pong balls with blown air, perhaps combined with mechanical agitation, and use some method to withdraw balls from the mixing chamber. This method gives reasonable results in some senses, but the random numbers generated by this means are expensive. The method is inherently slow, and is unusable in most automated situations, (i.e., with computers). This article describes the lottery game. ... A lottery is a popular form of gambling which involves the drawing of lots for a prize. ...

In 1927, Cambridge University Press published a book of Random sampling numbers, arranged by a statistician, Leonard Henry Caleb Tippett, which contained 41,600 digits taken from English parishes listed in census records. Other random number tables were published in that era, including one by R. A. Fischer and another by the U.S. Interstate Commerce Commission in 1949 with over 100,000 random digits. The headquarters of the Cambridge University Press, in Trumpington Street, Cambridge. ... Sir Ronald Aylmer Fisher, FRS (17 February 1890 – 29 July 1962) was an English statistician, evolutionary biologist, and geneticist. ... The Interstate Commerce Commission (or ICC) was a regulatory body in the United States created by the Interstate Commerce Act of 1887, which was signed into law by President Grover Cleveland. ...

What is likely to be the last of these projects is A Million Random Digits with 100,000 Normal Deviates, published by the RAND Corporation in 1955. They created an electronic simulation of a roulette wheel attached to a key punch, the results of which were then carefully filtered and tested before being used to generate the table. 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 was useful for simulations and modeling. But, having been published, it is not usable as cryptographic keys, or for preparing them, or as a seed in some cryptographic pseudo-random number generator. However, since it was published long before modern cryptography, using values from it for the random (if not unknown) constants for initializing algorithms would demonstrate that the constants had not been selected for (in B. Schneier's words) "nefarious purpose(es)." Khufu and Khafre do this, for example (ref Applied Cryptography - B. Schneier). See: Nothing up my sleeve numbers. An important 20th century work in the field of statistics and random numbers was the RAND Corporations book of tables containing, and entitled, A Million Random Digits with 100,000 Normal Deviates. ... Alternate meanings: See RAND (disambiguation) The RAND Corporation is an American think tank first formed to offer research and analysis to the U.S. military. ... IBM 029 keypunch. ... Bruce Schneier Bruce Schneier (born January 15, 1963) is an American cryptographer, computer security specialist, and writer. ... In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xeroxs Palo Alto Research Center. ... Nothing up my sleeve numbers are the the opposite extreme of Chaitin-Kolmogorov randomness in that they appear to be random by statistical tests but are created with minimum entropy. ...

Physical phenomena with random properties

There are two fundamental sources of practical quantum mechanical physical randomness: quantum mechanics at the atomic or sub-atomic level and thermal noise (some of which is quantum mechanical in origin). Quantum mechanics predicts that certain physical phenomena, such as the nuclear decay of atoms, are fundamentally random and cannot, in principle, be predicted. (For a discussion of empirical verification of quantum unpredictability, see Bell test experiments.) And, because we live at a finite, non-zero temperature, every system has some random variation in its state; for instance, molecules of air are constantly bouncing off each other in a random way. (See statistical mechanics.) This randomness is a quantum phenomenon as well. (See phonon.) Johnson-Nyquist noise (sometimes thermal noise, Johnson noise or Nyquist noise) is the noise generated by the equilibrium fluctuations of the electric current inside an electrical conductor, which happens without any applied voltage, due to the random thermal motion of the charge carriers (the electrons). ... Radioactive decay is the set of various processes by which unstable atomic nuclei (nuclides) emit subatomic particles. ... In quantum mechanics, Bells Theorem states that a Bell inequality must be obeyed under any local hidden variable theory but can in certain circumstances be violated under quantum mechanics (QM). ... Statistical mechanics is the application of probability theory, which includes mathematical tools for dealing with large populations, to the field of mechanics, which is concerned with the motion of particles or objects when subjected to a force. ... Normal modes of vibration progression through a crystal. ...

Because the outcome of quantum-mechanical events cannot in principle be predicted, they are the 'gold standard' for random number generation. Some quantum phenomena used for random number generation include:

• Shot noise, a quantum mechanical noise source in electronic circuits. A simple example is a lamp shining on a photodiode. Due to the uncertainty principle, arriving photons create noise in the circuit. Collecting the noise for use poses some problems, but this is an especially simple random noise source.

• A nuclear decay radiation source (as, for instance, from some kinds of commercial smoke detectors), detected by a Geiger counter attached to a PC.

• Photons travelling through a semi-transparent mirror, as in the commercial product, Quantis from id Quantique. The mutually exclusive events (reflection — transmission) are detected and associated to "0" or "1" bit values respectively.

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 (e.g., ~150 K) low enough to reduce noise by a factor of two. Some of the thermal phenomena used include: Photon noise simulation. ... In quantum physics, the outcome of even an ideal measurement of a system is not deterministic, but instead is characterized by a probability distribution, and the larger the associated standard deviation is, the more uncertain we might say that that characteristic is for the system. ... Radioactive decay is the set of various processes by which unstable atomic nuclei (nuclides) emit subatomic particles. ... A smoke detector or smoke alarm is a device that detects smoke and issues an alarm to alert nearby people that there is a potential fire. ... This article or section does not cite any references or sources. ... In modern physics the photon is the elementary particle responsible for electromagnetic phenomena. ... A beam splitter is an optical device, that splits a beam of light in two. ... Wikipedia does not have an article with this exact name. ... In logic, two mutually exclusive (or mutual exclusive according to some sources) propositions are propositions that logically cannot both be true. ...

• Thermal noise from a resistor, amplified to provide a random voltage source.

• Avalanche noise generated from an avalanche diode, or Zener breakdown noise from a reverse-biased zener diode.

• Atmospheric noise, 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 phenomenon).

Another variable physical phenomenon that is easy to measure is clock drift. Johnson-Nyquist noise, thermal noise, Johnson noise, or Nyquist noise) is the noise generated by the equilibrium fluctuations of the electric current inside an electrical conductor, which happens regardless of any applied voltage, due to the random thermal motion of the charge carriers (the electrons). ... Resistor symbols (non-European) Resistor symbols (Europe, IEC) Axial-lead resistors on tape. ... Avalanche breakdown is a phenomenon that can occur in both insulating and semiconducting materials. ... An avalanche diode is a diode (usually made from silicon, but can be made from another semiconductor) that is designed to break down and conduct at a specified reverse bias voltage. ... Zener diode schematic symbol A Zener diode is a type of diode that permits current to flow in the forward direction like a normal diode, but also in the reverse direction if the voltage is larger (not equal to, but larger) than the rated breakdown voltage known as Zener knee... Radio noise If there was no noise picked up with radio signals, then tiny transmitters could be received at any distance just by making a radio receiver that was sensitive enough. ... For other senses of this word, see chaos (disambiguation). ... Clock drift refers to several related phenomena where a clock does not run in the exact right speed compared to another clock. ...

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 or Fortuna 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 knowledgable 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 interrupts caused by mechanical input/output devices, such as keyboards and disk drives, various system information counters, etc. The Yarrow algorithm is a cryptographically secure pseudo-random number generator. ... Fortuna is a cryptographically secure pseudo-random number generator (PRNG) devised by Bruce Schneier and Niels Ferguson. ... A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography. ... In security engineering, a nonce is a number used once. ... In computing, an interrupt is an asynchronous signal from hardware or software indicating the need for attention. ... Disk Drive is the afternoon show on CBC Radio Two. ...

This last approach must be implemented carefully and may be subject to attack if it is not. For instance, the generator built into the Linux kernel, which combines several such sources, may be vulnerable to an attack [1]. The random number generator used for cryptographic purposes in an early version of the Netscape browser was certainly vulnerable (and was promptly changed). Netscape Communications (formally known as Netscape Communications Corporation and commonly known as Netscape), is an American computer services company, best known for its web browser. ...

One approach in using physical randomness is to convert a noise source into a random bit sequence in a separate device that is then connected to the computer through an I/O port. The acquired noise signal is amplified, filtered, and then run through a high-speed voltage comparator to produce a logic signal that alternates states at random intervals. At least in part, the randomness produced depends on the specific details of the 'separate device'. Care must also always be taken when amplifying low-level noise to keep out spurious signals, such as power line hum and unwanted broadcast transmissions, and to avoid adding bias during acquisition and amplification. In some simple designs, the fluctuating logic value is converted to an RS-232 type signal and presented to a computer's serial port. Software then sees this series of logic values as bursts of "line noise" characters on an I/O port. More sophisticated systems may format the bit values before passing them into a computer. RS-232 (also referred to as EIA RS-232C or V.24) is a standard for serial binary data interchange between a DTE (Data terminal equipment) and a DCE (Data communication equipment). ... In science, and especially in physics and telecommunication, noise is fluctuations in and the addition of external factors to the stream of target information (signal) being received at a detector. ...

Another approach is to feed an analog noise signal to an analog to digital converter, such as the audio input port built into most personal computers. The digitized signal may then be processed further in software to remove bias. However, digitization is itself often a source of bias, sometimes subtle, so this approach requires considerable caution and care. This article or section should include material from AD converters In electronics, an analog-to-digital converter (abbreviated ADC, A/D, or A to D) is a device that converts continuous signals to discrete digital numbers. ...

Some have suggested using digital cameras, such as webcams, to photograph chaotic macroscopic phenomena. A group at Silicon Graphics imaged Lava lamps to generate random numbers. U.S. Patent 5,732,138  One problem was determining whether the chaotic shapes generated were actually random -- the team decided that they are in properly operating Lava lamps. Other chaotic scenes could be employed, such as the motion of streamers in a fan air stream or, probably, bubbles in a fish tank (fish optional). The digitized image will generally contain additional noise, perhaps not very random, resulting from the video to digital conversion process. A higher quality device might use two sources and eliminate signals that are common to both— depending on the sources and their physical locations, this reduces or eliminates interference from outside electric and magnetic fields. This is often recommended for gambling devices, to reduce cheating by requiring attackers to exploit bias in several "random bit" streams. A typical webcam A web camera (or webcam) is a real-time camera (usually, though not always, a video camera) whose images can be accessed using the World Wide Web, instant messaging, or a PC video calling application. ... Silicon Graphics, Inc. ... A lava lamp is a novelty item typically used for decoration rather than illumination. ... “Aquaria” redirects here. ...

The Commodore C64 provided a hardware random number generator, included in its soundchip, the Mos_Technology_SID 6581. Random bytes are fetchable by a read on the correct memory address on the 6581. C-64 redirects here. ... MOS Technology SIDs: The right image shows a 6581 from MOS Technology, at the time they were known as the Commodore Semiconductor Group (CSG) and the left image shows an 8580 from MOS Technology. ...

The Intel 80802 Firmware Hub 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 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. Intel Corporation (NASDAQ: INTC, SEHK: 4335), founded in 1968 as Integrated Electronics Corporation, is an American multinational corporation that is best known for designing and manufacturing microprocessors and specialized integrated circuits. ... For other persons named John Neumann, see John Neumann (disambiguation). ...

All VIA C3 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 insure 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. The VIA C3 is an x86 central processing unit for personal computers produced by VIA Technologies. ...

A software implementation of a related idea on ordinary hardware is included in CryptoLib, a cryptographic routine library (JB Lacy, DP Mitchell, WM Schell, CryptoLib: Cryptography in software, Proc 4th USENIX Security Symp, pg 1-17, 1993). The algorithm is 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 bit of a count of loop interations, 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).

Dealing with bias

The bit-stream from such systems is 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, 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. A central limit theorem is any of a set of weak-convergence results in probability theory. ...

Software whitening

A second approach to coping with bias is to reduce it after generation (in software or hardware). Even if the above hardware bias reduction steps have been taken, the bit-stream should still be assumed to contain bias and correlation. There are several techniques for reducing bias and correlation, often known by the name "whitening" algorithms, by analogy with the related problem of producing white noise from a correlated signal. Decorrelation is a general term for any process that is used to reduce autocorrelation within a signal, or cross-correlation within a set of signals, while preserving other aspects of the signal. ...

John von Neumann invented a simple algorithm to fix simple bias, and reduce correlation. It considers bits two at a time, taking one of three actions: when two successive bits are the same, they are not used as a random bit, a sequence of 1,0 becomes a 1, and a sequence of 0,1 becomes a zero. 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 random bit stream with a frequency of 1's different from 50% into a stream closer to that frequency. For other persons named John Neumann, see John Neumann (disambiguation). ...

Another technique for improving a near random bit stream is to exclusive-or the bit stream with the output of a high-quality cryptographically secure pseudorandom number generator such as Blum Blum Shub or a good stream cipher. This can cheaply improve decorrelation and digit bias. Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ... A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography. ... Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986). ... The operation of the keystream generator in A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ...

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 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 2e². This may be repeated with more bit streams. (See also Piling-up lemma). Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ... In cryptanalysis, the piling-up lemma is a principle used in linear cryptanalysis to construct linear approximations to the action of block ciphers. ...

Some designs apply cryptographic hash functions such as MD5, SHA-1, 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 compared to some other methods, but depends entirely on qualities in the hash output for which there may be little theoretical basis. A hash function is a reproducible method of turning some kind of data into a (relatively) small number that may serve as a digital fingerprint of the data. ... In cryptography, MD5 (Message-Digest algorithm 5) is a widely used cryptographic hash function with a 128-bit hash value. ... The SHA (Secure Hash Algorithm) family is a set of related cryptographic hash functions designed by the National Security Agency (NSA) and published by the National Institute of Standards and Technology (NIST). ... RIPEMD-160 (RACE Integrity Primitives Evaluation Message Digest) is a 160-bit message digest algorithm (and cryptographic hash function) developed in Europe by Hans Dobbertin, Antoon Bosselaers and Bart Preneel, and first published in 1996. ... A cyclic redundancy check (CRC) is a type of function that takes as input a data stream of any length and produces as output a value of a certain fixed size. ...

PRNG with periodically refreshed random key

Other designs use what are believed to be true random bits as the key for a high quality block cipher 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. A key is a piece of information that controls the operation of a cryptography algorithm. ... Encryption Decryption In cryptography, a block cipher is a symmetric key cipher which operates on fixed-length groups of bits, termed blocks, with an unvarying transformation. ... OFB redirects here. ...

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 (see the CSPRNG article). A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography. ...

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. Several gambling frauds have been uncovered which rely on manipulating normally hidden events internal to the operation of computers or networks. 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. In the context of network security, a spoofing attack is a situation in which one person or program successfully masquerades as another by falsifying data and thereby gaining an illegitimate advantage. ...

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 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 with a key and 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 library. It provides resistance against some attacks and conserves hard-to-obtain entropy.

In Unix-like operating systems, /dev/random is a special file that serves as a true random number generator or as a pseudorandom number generator. ... Theodore Ted Tso is a software developer known for his contributions to the Linux kernel, in particular his contributions to filesystems. ... The operation of the keystream generator in A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ... In cryptography, an initialization vector (IV) is a block of bits that is required to allow a stream cipher or a block cipher executed in any of several streaming modes of operation to produce a unique stream independent from other streams produced by the same encryption key, without having to... The Yarrow algorithm is a cryptographically secure pseudo-random number generator. ...

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. Failure modes in such devices are plentiful and are complicated, slow, and hard to detect.

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.

Just as with other components of a cryptosystem, a software random number generator should be designed to resist certain attacks. Defending against these attacks is difficult. See: random number generator attack. The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. ...

Estimating entropy

There are mathematical techniques for estimating the entropy 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 pseudo-random generator. Claude Shannon In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. ...

Performance checks

Hardware random number generators should be constantly monitored for proper operation. RFC 4086 and FIPS Pub 140-2 include tests which can be used for this. Also see the documentation for the New Zealand cryptographic software library cryptlib. Federal Information Processing Standards (FIPS) are publicly announced standards developed by the U.S. Federal government for use by all (non-military) government agencies and by government contractors. ... FIPS 140 (Federal Information Processing Standards Publication 140) is a United States federal standard that specifies security requirements for cryptography modules. ... cryptlib is an open source cross-platform software security toolkit. ...

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

• Pseudorandom number generator
• Random number generator
• Random number generation
• Randomness extractor
• Randomness
• Bell test experiments
• ERNIE
• Lottery machine
• Peter Gutmann of the University of Auckland has produced an extensive analysis of "random number" generation with computers (and of several actual designs) in the documentation for the cryptlib cryptographic tool kit.

A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. ... A random number generator is a computational or physical device designed to generate a sequence of elements (usually numbers), such that the sequence can be used as a random one. ... A random number generator is a computational or physical device designed to generate a sequence of numbers that does not have any easily discernable pattern, so that the sequence can be treated as being random. ... This does not cite any references or sources. ... “Random” redirects here. ... In quantum mechanics, Bells Theorem states that a Bell inequality must be obeyed under any local hidden variable theory but can in certain circumstances be violated under quantum mechanics (QM). ... Ernie, in a skit. ... A lottery machine is the machine used to draw the winning numbers for a lottery. ... This article is about a computer scientist. ... The University of Auckland (Māori: Te Whare Wānanga o Tāmaki Makaurau) is New Zealands largest research-based university. ...

External links

• RFC 4086 on Randomness Recommendations for Security (Replaces earlier RFC 1750.)
• A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications NIST Special Publication 800-22
• An article on the history of generating random numbers at the American Scientist Online.
• Glossary of words concerning true random number generation

As a non-regulatory agency of the United States Department of Commerce’s Technology Administration, the National Institute of Standards (NIST) develops and promotes measurement, standards, and technology to enhance productivity, facilitate trade, and improve the quality of life. ...

Code

• Theodore Ts'o (November 1995). "random.c -- A strong random number generator".
• Pars Mutaf (February 2006). "True random numbers from Wi-Fi background noise". Retrieved on 2007-04-16.
• video_entropyd (Randomness from video)
• audio_entropyd (Randomness from audio)
• Math::TrulyRandom (Perl module that claims to generate actual random numbers from interrupt timing discrepancies)
• True (physical) random number generators (with USB interface - for Microsoft Windows)

Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era in the 21st Century. ... is the 106th day of the year (107th in leap years) in the Gregorian calendar. ... A Perl module is a discrete component of software for the Perl programming language. ...

References

• A Million Random Digits with 100,000 Normal Deviates by the RAND Corporation
• Francis Galton. "Dice for statistical experiments", Nature 42:13-14, 1890. (Facsimile at: [2])