Unpredictable outcome is the essence of gambling itself.
Let’s see where it all begins!
The first random number generaton was invented in ancient times. Its were simple things still used in gambling - dice, roulette and coin flipping. First methods of using dice for random number generation were described in 1830 by English explorer Francis Halton.
Further step of RNG technology were hardware RNGs introduced in 1939 and 1957 was the year of ERNIE (Electronic Random Number Generation Equipment) invention. It was used for generating winner lotto bond numbers.
Random number generator is a device generating numbers or symbols that can’t be predicted. It’s operation is usually based at chaotically changing parameters – sources of enthropy and unpredictable processes. Main RNG applications are cryptography, computer simulation, gambling, statistical sampling – spheres where unpredictable result is desired.
Hardware RNGs are usually based on random macroscopic process. In fact, even calculated macroscopic systems have unforeseeable outcome depending on immeasurable microscopic details.
Generators operation is driven by several types of process.
• Random physical phenomenon (radioactive decay, thermal noise, shot noise, avalanche noise in Zener diodes and so on)
• Other ways of collecting entropic data (computer cooler sound, lava lamp images)
• Human user behaviour (intervals between mouse moves or keybord inputs)
Specific construction features cause disadvantages:
• Low operation speed comparing to PRNG
• Need for testing (substance characteristics loss, mechanical parts wear)
• External dependence (ambient temperature, system interference
• System complexity and costliness
• Bit consequence expectation offset
Pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG’s seed. RNG generates fully random number using random initial value. In other words, RNG = PRNG + entropy source.
“True” RNG is complex to implement due to above aspects, but RNG generated numbers are often used as pseudorandom number generator seed. PRNGs are central in applications such as simulations (the Monte Carlo method), electronic games (procedural generation), and cryptography.
Main PRNG types are:
• Linear recurrency based generator (LCPRNG) – popular non-cryptographically secure number generator based on 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 generator algorithms.The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modulo arithmetic by storage-bit truncation
• Mersenne Twister – invented in 1997, avoided many of the problems with earlier generators. The Mersenne Twister has a period of 219937−1 iterations (≈4.3×106001), is proven to be equidistributed in (up to) 623 dimensions (for 32-bit values), and at the time of its introduction was running faster than other statistically reasonable generators.
• Xorshift generators introduced by George Marsaglia in 2003, based on a linear recurrence. Such generators are extremely fast and, combined with a nonlinear operation, used to pass strong statistical tests.
• WELL generators developed in 2006 – in some ways improve on the quality of the Mersenne Twister—which has a too-large state space and a very slow recovery from state spaces with a large number of zeros.
Most generators provide high operation speed but cannot fail significant gaps. In practice, the output from many common PRNGs exhibit artifacts that cause them to fail statistical pattern-detection tests. These include:
• Shorter than expected periods for some seed states (such seed states may be called ‘weak’ in this context);
• Lack of uniformity of distribution for large numbers of generated numbers;
• Correlation of successive values;
• Poor dimensional distribution of the output sequence;
• The distances between where certain values occur are distributed differently from those in a random sequence distribution.
Defects exhibited by flawed PRNGs range from unnoticeable (and unknown) to very obvious. An example was the RANDU random number algorithm used for decades on mainframe computers. It was seriously flawed, but its inadequacy went undetected for a very long time.
Cryptographically secure pseudorandom number generator (CSPNG) is a PRNG posessing properties that make it suitable for use in cryptography.
Most cryptographic applications require random numbers, for example:
• key generation
• nonces
• one-time pads
• salts in certain signature schemes, including ECDSA, RSASSA-PSS
Demanded random quality depends on the objective. For example, creating a nonce in some protocols needs only uniqueness. On the other hand a master key generation requires a higher quality, such as more entropy. Ideally, CSPRNG is provided with high-security entropy source – a hardware random number generator or unpredictable internal process, but unexpected vulnerability can sometimes be found.
Regarding to an information-theoretic point of view, the amount of randomness, the entropy that can be generated, is equal to the entropy provided by the system. But sometimes, in practical situations, more random numbers are needed than there is entropy available. Also the processes to extract randomness from a running system are slow in actual practice. In such instances, a CSPRNG can sometimes be used. A CSPRNG can “stretch” the available entropy over more bits.
When all entropy is available before cryptographical algorithm performed, a stream encryption is obtained. However, some cryptosystems allow adding entropy throughout the process. In this case, the algorithm is not equal stream encryption and can’t be used in this function. Therefore, stream encryption development is closely related with CSPRNG.
Requirements made to CSPNG are impossible for simple PRNG. They can be divided into 2 main groups: statistical randomness tests and cryptographical persistence – the numbers have to stay unpredictable even if basic data is partly compromised. Some cases below:
• Every CSPRNG should satisfy the next-bit test. That is, given the first k bits of a random sequence, there is no polynomial-time algorithm that can predict the (k+1)th bit with probability of success non-negligibly better than 50%. Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.
• Every CSPRNG should withstand “state compromise extensions”. In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation. Additionally, if there is an entropy input while running, it should be infeasible to use knowledge of the input’s state to predict future conditions of the CSPRNG state.
Most PRNGs are not suitable for use as CSPRNGs on both criterias. First to say, most PRNGs generate random numbers in terms of statistical tests, but they are not resistant to determined reverse engineering. Specialized statistical tests may be conducted to show PRNG numbers not to be truly random. Secondly, most PRNGs’ random number consequence can be retrodicted if basic data and conditions are partly compromised. It allows cryptologist to build up all the past and future number consequence and hack the PRNG.
CSPRNGs are designed to resist different types of cryptoanalysis and are based on three basic principles: cryptographical algorythms, complicated math problems, other specific realisations. Recent ones use additional entropy sources so their outcome is not determined by default conditions. This method facilitates further cryptographical security.
