Pseudorandom Number Generators
These pseudorandom numbers are used a lot in computer technology, so I want to learn more about them.
Date Created:
References
Notes
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-sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values). Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generators and their reproducibility.
PRNGs are central in applications such as simulations, electronic gaming, and cryptography. Good statistical properties are a central requirement for the output of a PRNG. In general, careful mathematical analysis is required to have any confidence that a PRNG generates numbers that are sufficiently close to random to suit the intended use.
Potential Issues
- The output from many PRNGs exhibit artifacts (error in the perception or representation of any information introduced by the involved equipment or techniques) that cause them to fail statistical pattern detection tests. These include:
- Shorter-than-expected periods for some seed states
- Lack of uniformity of distribution for large quantities of generated numbers
- Correlation of successive values
- Poor dimensional distribution of the output sequence
- Distances between where certain values occur are distributed differently from those in a random sequence distribution
- The following warning is in the International Encyclopedia of Statistical Science:
The list of widely used generators that should be discarded is much longer [than the list of good generators]. Do not trust blindly the software vendors. Check the default RNG of your favorite software and be ready to replace it if needed. This last recommendation has been made over and over again over the past 40 years. Perhaps amazingly, it remains as relevant today as it was 40 years ago.
- As an example, Java relied on a low-quality PRNG until 2020.
Generators Based on Linear Recurrences
- In the second half of the 20th century, the standard class of algorithms used for PRNGs comprised linear congruential generators.
- A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation.
- A major advance in the construction of pseudorandom generators was the introduction of techniques based on linear recurrences on the two-element field; such generators are related to linear-feedback shift registers
- A linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state
- The 1997 invention of the Mersenne Twister avoided many problems with earlier generators.
- In 2003, a family of xorshift generators based on linear recurrence was introduced
- In 2006, the WELL family of generators was developed.
Cryptographic PRNGs
- A PRNG suitable for cryptographic applications is called a cryptographically-secure PRNG (CSPRNG). A requirement for a CSPRNG is that an adversary not knowing the seed has only negligible advantage in distinguishing the generator's output sequence from a random sequence.
- While a PRNG is only required to pass certain statistical tests, a CSPRNG must pass all statistical tests that are restricted to polynomial time in the size of the seed.
- Most PRNG algorithms produce sequences that are uniformly distributed by any of several tests. It is an open question, and one central to the theory and practice of cryptography, whether there is any way to distinguish the output of a high-quality PRNG from a truly random sequence.
BSI Evaluation Criteria
- The German Federal Office for Information Security (BSI) has established for criteria for quality of deterministic random number generators:
- K1 - There should be high probability that generated sequences of random numbers are different from each other.
- K2 - A sequence of numbers is indistinguishable from
truly random
numbers according to specified statistical tests. - K3 - It should be impossible for an attacker to calculate, or otherwise guess, from any given subsequence, any previous or future values in the sequence, nor any inner state of the generator
- K4 - It should be impossible, for all practical purposes, for an attacker to calculate, or guess from an inner state of the generator, any previous numbers in the sequence or any previous inner generator states.
Early Approaches
- An early computer-based PRNG, suggested by Von Neumann in 1946, is known as the middle-square method. The algorithm is as follows: take any number, square it, remove the middle digits of the resulting number as the "random number", then use that number as the seed for the next iteration.
- The problem with this method is that the sequences eventually repeat themselves.