Breaking Randomness
In this page, we'll talk about pseudo random number generators (PRNGs)
Randomness and Pseudo-Random Number Generators (PRNGs)
Randomness is a fundamental concept in many areas of computer science, mathematics, and cryptography. It plays a crucial role in simulations, gaming, statistical sampling, and securing sensitive data. However, true randomness is surprisingly hard (impossible) to achieve in computational systems, leading to the development of Pseudo-Random Number Generators (PRNGs).
What is Randomness?
True Randomness: Refers to outcomes that are completely unpredictable and have no discernible pattern.
Pseudo-Randomness: Refers to sequences of numbers that appear random but are actually generated by deterministic algorithms. They mimic the properties of randomness but are ultimately predictable if you know the algorithm and its parameters.
Why Do We Need Randomness?
Randomness is essential in areas such as:
Cryptography: Generating secure encryption keys, salts, and nonces.
Simulations: Modeling natural processes like weather or biological systems.
Gaming: Ensuring fairness and unpredictability in game mechanics.
Machine Learning: Initializing weights in neural networks and shuffling data.
What are PRNGs?
A Pseudo-Random Number Generator (PRNG) is an algorithm that produces a sequence of numbers that approximates true randomness. Unlike true random sources, PRNGs are:
Deterministic: Given the same initial input (called a seed), a PRNG will always produce the same sequence.
Fast and Efficient: PRNGs are designed to generate numbers quickly and reproducibly, making them ideal for computer applications.
How PRNGs Work
PRNGs start with an initial value (the seed). They apply a mathematical formula to the seed to generate the next number in the sequence, updating the state after each step.
Randomness in Cryptography
In cryptographic applications, randomness needs to be:
Unpredictable: Even if part of the sequence is known, the rest must remain impossible to deduce.
Securely Generated: Resistant to reverse-engineering by attackers.
Why PRNGs Can Fall Short
Most PRNGs, such as LCGs or Mersenne Twister, fail to meet cryptographic standards because:
They are predictable if the algorithm or seed is known.
They lack resilience against reverse-engineering.
What is the Period in PRNGs?
The period of a Pseudo-Random Number Generator (PRNG) is how long its sequence of numbers lasts before it starts repeating.
Think of it like a playlist: if your playlist has 10 songs and it’s on repeat, after the 10th song, the first song will play again, and the sequence starts over. In the same way, a PRNG generates numbers until it reaches the end of its “playlist” and starts from the beginning.
A short period means the sequence repeats quickly, which isn’t very random.
A long period means the PRNG can generate many unique numbers before repeating, which is better for most uses.
For example:
If a PRNG has a period of 8, the numbers might look like this: 5, 3, 7, 1, 6, 2, 4, 0, and then it starts again: 5, 3, 7....
A good PRNG has a long enough period to avoid noticeable repetition in practical applications.
Linear Congruential Generators (LCGs)
What is an LCG?
An LCG is a mathematical formula that generates a sequence of numbers using this recurrence relation:
Xn: The current number in the sequence (also called the "state").
a: The multiplier (a constant that affects how the numbers are distributed).
c: The increment (a constant added to the product; if c=0, it becomes a "multiplicative" LCG).
m: The modulus (determines the range of numbers produced, typically a power of 2).
Xo: The seed (initial value; it starts the sequence).
How Does It Work?
Use the formula repeatedly to generate the next number in the sequence.
And so on...
Why is LCG Not Truly Random?
Periodicity: LCG sequences eventually repeat themselves. The period (maximum length before repetition) depends on the choice of a, c, and m. A poorly chosen set of constants results in short or poor-quality sequences.
Low Entropy: The sequence may have patterns or correlations, especially in high-dimensional spaces (e.g., if plotted in 3D, points might lie on a few planes).
Linear Feedback Shift Registers (LFSRs)
Linear Feedback Shift Registers (LFSRs) are another type of pseudo-random number generator (PRNG) commonly used in areas like error correction codes, cryptography, and digital systems. Unlike algorithms like Linear Congruential Generators (LCGs), LFSRs operate at the hardware level, making them lightweight, fast, and efficient for generating pseudo-random sequences.
Registers
In simple words, a register is a component in modern computers that holds binary data, your memory (RAM) is a bunch of registers stacked on top of each other, but for our work, let's visualize it like this:
Shift Registers
A shift register is essentially a storage unit (a register) that moves, or "shifts," its contents. When we shift the values, each bit in the register moves one position to the right, like a conveyor belt:
The leftmost bit becomes the second from the left.
The second bit becomes the third, and so on.
The rightmost bit exits the register.
If we think of the register as a 7-bit array, shifting means each bit moves one step to the right. When a bit exits the register, it can be processed externally, such as for generating a stream of bits. The empty spaces on the left are filled with zeroes.
For example:
Start:
1010100After one shift:
0101010(with a zero filling the leftmost space).
This simple mechanism makes shift registers useful in cryptography for generating bit streams or performing simple operations.
Adding Feedback to a Shift Register
A basic shift register is neat, but it gets boring fast because it eventually fills with zeroes, producing a dull bit stream. To make it more dynamic, we introduce feedback!
Here’s how it works:
Instead of always adding a zero as the new bit, we compute the new input by XORing specific bits in the register.
These specific positions are called taps.
For example, let’s say we have a shift register and we "tap" bits at indices 1, 2, 4, and 6 (counting left to right). The XOR result of these tapped bits becomes the new bit added to the leftmost position after the shift.
With feedback, our bit stream becomes more interesting. For instance:
The first replacement bit might be a zero.
The second could be a one, depending on the XOR of the tapped bits.
This feedback mechanism ensures the stream isn’t just repetitive zeroes and adds variety to the output!
The "Linear" in LFSR
The "linear" part of Linear Feedback Shift Registers (LFSRs) refers to the operation used to generate the replacement bit: XOR.
XOR is a linear function when applied to single bits, meaning the output is determined by a straightforward combination of the tapped bits (with no complex or non-linear transformations). This simplicity is why "linear" is included in the name—it describes the type of feedback mechanism used.
Last updated
