Read it here first: Are You Using These Random Number Algorithms Incorrectly?
In computer science, several methods are used to generate random numbers. Here are a few popular ones:
- Linear Congruential Generator (LCG)
- Mersenne Twister
- Xorshift
- WELL (Well Equidistributed Long-period Linear)
- PCG (Permuted Congruential Generator)
(When high security is required, such as for cryptographic uses, these methods should not be used*. Instead, one should use a cryptographic random number generator such as those provided by Web Crypto API.)*
Here I will discuss their strengths, weaknesses and where to use them in your project.
LCGs are one of the oldest and best-known pseudo-random number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast.
Where to Use: They are good for simple applications that need random numbers but don’t have high requirements for the quality of randomness, such as basic computer simulations or games. Their advantage is that they are fast and require very little memory.
Strengths: Easy to implement, fast, and uses little memory.
Weaknesses: Not suitable for all applications due to the low randomness. The lower bits of the numbers generated by LCG are noticeably less random than the higher bits.
CPU/Memory Load and Speed: Very low CPU and memory load, very fast.
function LCG(seed) {
const a = 1664525;
const c = 1013904223;
const m = Math.pow(2, 32);
let state = seed;
return function() {
state = (a \* state + c) % m;
return state / m;
};
}
const lcg = LCG(123);
console.log(lcg());
The Mersenne Twister has a period of 2¹⁹⁹³⁷-1 iterations and is one of the most extensively tested random number generators in existence. However, it’s not suitable for cryptography.
Where to Use: It’s useful for applications that require many random numbers with high-quality randomness, such as Monte Carlo simulations or procedural generation in video games.
Strengths: Excellent statistical properties, long period.
Weaknesses: Relatively slow, not suitable for cryptography.
CPU/Memory Load and Speed: Moderate CPU and memory load, relatively slow.
// Mersenne Twister
let MersenneTwister = require('mersenne-twister'); //npm package
let generator = new MersenneTwister();
console.log(generator.random());
Xorshift RNGs are a class of pseudorandom number generators discovered by George Marsaglia. They generate the next number in their sequence by repeatedly taking the exclusive or of a number with a bit-shifted version of itself.
Where to Use: They are typically very fast and use very little memory, which makes them suitable for applications that need many random numbers quickly and don’t have very high requirements for randomness, such as some computer graphics or simulation applications.
Strengths: Simple, fast.
Weaknesses: Not suitable for cryptographic purposes, relatively short period compared to other generators.
CPU/Memory Load and Speed: Low CPU and memory load, fast.
class XorShift {
constructor(seed = 1) {
this.state = seed;
}
next() {
this.state ^= this.state \<\< 13;
this.state ^= this.state \>\> 17;
this.state ^= this.state \<\< 5;
return this.state / Math.pow(2, 32);
}
}
let xorShift = new XorShift(123);
console.log(xorShift.next());
The WELL generator improves upon the Mersenne Twister, addressing some of its issues and providing better statistical qualities.
Where to Use: It’s good for applications that require a large number of high-quality random numbers and can afford the higher computational cost, such as scientific simulations or complex procedural generation in games.
Strengths: Improved statistical qualities over Mersenne Twister.
Weaknesses: More complex and slower than some other algorithms.
CPU/Memory Load and Speed: Moderate to high CPU and memory load, relatively slow.
// WELL
let WELL = require('well-rng'); //npm package
let well = new WELL();
console.log(well.random());
The PCG family is a collection of simple, fast, space-efficient, and high-quality random number generators. It is a relatively recent addition to the world of RNG algorithms.
Where to Use: They’re suitable for a wide range of applications, including games, simulations, and statistical sampling, especially where the balance between good quality randomness and speed is important.
Strengths: High quality random numbers, fast, space-efficient.
Weaknesses: Slightly more complex than the simplest algorithms (like LCG or Xorshift).
CPU/Memory Load and Speed: Low to moderate CPU and memory load, fast.
// PCG
let PCG = require('pcg-random');//npm package
let pcg = new PCG();
console.log(pcg.random());
Cryptographic applications require random numbers that are unpredictable and uniformly distributed. Non-cryptographic random number generators, like those mentioned above, are designed for speed and statistical randomness. They aren’t designed to withstand someone actively trying to predict the next number given full knowledge of the algorithm and some output, which is a requirement for cryptographic purposes.
Statistical random number generators (also known as pseudo-random number generators, PRNGs) are not truly random; they are deterministic and operate according to a set algorithm. Given enough output from these generators or knowledge of their state at a certain point, it is theoretically possible to predict their future output. Here are some known prediction methods:
- State compromise extension: If an attacker knows the internal state of the PRNG, they can predict all future outputs. This may happen if they can read the memory of your software or if they can cause it to output its internal state.
- Output analysis: The outputs of PRNGs often contain patterns or biases that can be used to predict their future output. If an attacker has access to a long enough sequence of outputs from the PRNG, they can often predict future outputs. This is easier for some PRNGs than others.
- Backtracking: Some PRNGs are susceptible to backtracking attacks, where the past output of the generator can be deduced from the current output. This is a particular concern for PRNGs that are used to generate cryptographic keys.
Remember, achieving true randomness in a computer environment poses a significant challenge due to its inherent deterministic nature. Consequently, many so-called Random Number Generators (RNGs) are, in fact, Pseudo-Random Number Generators (PRNGs), producing sequences that only approximate true randomness. It’s essential to be aware that perspectives on these algorithms — including those considered ‘secure’ — are likely to evolve over time. This change can be prompted by advancements in technology, newer methods of attacks, or increased computational power.
Additionally, vulnerabilities can arise from programming errors or bugs within the chosen algorithm or its specific implementation. Therefore, it’s crucial to stay informed and regularly update your knowledge about the chosen algorithm and its particular package or implementation. By doing so, you ensure that your RNG maintains its integrity and serves its intended function reliably.
- The quality of randomness, speed, and memory usage are relative to each other and can vary with different implementations and usages.
- Cryptographically secure random number generators are typically slower than their non-secure counterparts due to the extra steps taken to ensure security.
- The period of a PRNG is the length of the sequence before it starts repeating. A longer period is generally better, but any period long enough that the sequence will not repeat within the expected runtime of the program is usually sufficient.