Deterministic random numbers — are pseudo-random sequences that are created by algorithms and look random, but are fully determined by the initial conditions (seed).
In mathematics and computer science it is often necessary to use random numbers: for modeling, statistics, cryptography, games, and even in artificial intelligence. However, obtaining true randomness in computing systems is difficult. Therefore, deterministic pseudo-random number generators (PRNGs) are used — algorithms that create sequences imitating randomness.
What are deterministic random numbers
-
Definition: numbers obtained from an algorithm that, given the same initial state, always produces the same sequence.
-
Key feature: they look random, but are actually fully predictable if the algorithm and the initial value are known.
-
Example: the linear congruential method (LCG), where each new number is calculated using the formula
Xn+1=(aXn+c)mod m
Here a,c,ma, c, m — are the generator's parameters, and X0 — is the initial value (seed).
Main properties
-
Determinism: repeatability of the sequence given the same seed.
-
Pseudo-randomness: statistical properties (uniform distribution, independence) bring them close to true random numbers.
-
Computational efficiency: number generation happens quickly and does not require physical sources of randomness.
-
Controllability: the ability to reproduce the results of experiments and simulations.
There are two main methods for generating random numbers. The first method measures some physical phenomenon that is expected to be random, and then compensates for possible errors in the measurement process. Examples of sources include measurements of atmospheric noise, thermal noise, and other external electromagnetic and quantum phenomena. For instance, cosmic background radiation or radioactive decay, measured over short intervals of time, represent sources of natural entropy (as a measure of the unpredictability or unexpectedness of the number-generation process).
types of pseudo-random numbers:
A cryptographically secure pseudo-random number generator (CSPRNG) or cryptographic pseudo-random number generator (CPRNG) — is a pseudo-random number generator (PRNG) possessing properties that make it suitable for use in cryptography. It is also called a cryptographic random number generator (CRNG).
Pseudo-random (deterministic) — numbers that appear random externally, but are fully determined by the initial seed and the algorithm.
Applications
-
Modeling and the Monte Carlo method: for simulating random processes.
-
Computer games: generation of maps, events, opponents.
-
Cryptography: although protecting data requires cryptographically secure generators, many algorithms use pseudo-random sequences as a foundation.
-
Testing and statistics: reproducible random samples make it possible to verify algorithms and systems.
| Games |
Repeatable levels, identical worlds |
| Simulations |
Reproducible experiments |
| Modeling |
Control of statistics |
| AI |
Training neural networks with a fixed seed |
| World generation |
Minecraft, No Man’s Sky |
Limitations
-
Predictability: if the algorithm and seed are known, the sequence can be reconstructed.
-
Not suitable for cryptography without strengthening: ordinary generators are easy to break, so special cryptographic PRNGs are used instead.
-
Finite period: any sequence sooner or later repeats itself.
Where they cannot be used
| Area |
Why |
| Cryptography |
Predictable |
| Passwords |
Easy to crack |
| Casinos |
Fairness cannot be guaranteed |
For this purpose, cryptographically secure generators (CSPRNGs) are used.
Implementations of CSPRNGs
Let us consider three classes of CSPRNG implementations:
- Based on cryptographic algorithms
- Based on computationally hard mathematical problems
- Special implementations
The latter often use additional sources of entropy, so, strictly speaking, they are not «pure» generators, since their output is not fully determined by the initial state. This makes it possible to provide additional protection against attacks aimed at determining the initial state.
Implementations based on cryptographic algorithms
- A secure block cipher can be converted into a CSPRNG by running it in counter mode. Thus, by choosing a random key, one can obtain the next random block by applying the algorithm to consecutive natural numbers. Counting can start from an arbitrary natural number. Obviously, the period will be no greater than 2n for an n-bit block cipher. It is also obvious that the security of such a scheme depends entirely on the secrecy of the key.
- A cryptographically secure hash function can also be converted into a CSPRNG. In that case, the initial counter value must remain secret. However, some authors warn against such use of hash functions .
- Most stream ciphers work on the basis of generating a pseudo-random bit stream, which is combined in some way (almost always via the XOR operation) with the bits of the plaintext. Running such a cipher on a sequence of natural numbers will produce a new pseudo-random sequence, possibly even with a longer period. This method is secure only if the stream cipher itself uses a reliable CSPRNG (which is not always the case). Again, the initial state of the counter must remain secret.
Implementations based on mathematical problems
- The Blum — Blum — Shub algorithm has high cryptographic strength, based on the presumed difficulty of factoring integers. However, this algorithm is characterized by very slow performance.
- The Blum — Micali algorithm (Blum-Micali algorithm) is based on the discrete logarithm problem.
Special implementations
There is a whole series of practically used PRNGs that were designed with cryptographic strength in mind, for example
- The Yarrow algorithm (Yarrow algorithm) which attempts to determine the entropy of the input data. It is used in FreeBSD, OpenBSD, and Mac OS X
- The Fortuna algorithm (Fortuna algorithm), the successor of the Yarrow algorithm.
- The special UNIX OS file /dev/random, in particular /dev/urandom, implemented in Linux.
- The CryptGenRandom function provided in Microsoft's CryptoAPI
- ISAAC is based on a variant of RC4.
Conclusion
Deterministic random numbers — are a compromise between true randomness and practical necessity. They make it possible to efficiently model random processes, but require caution in areas where unpredictability is important, such as cryptography.
See also
- Flipism (decisions are made by tossing a coin)
- The Entropy League
- List of random number generators
- Class PP
- Procedural generation
- Randomized algorithm
- Random password generator
- Random variable, contains a value that depends on randomness
Comments