In the the world of computers we all face a very common idea create by humans randomness. When ever you request a OTP a mathematical function fires and gives us a Random Number. How are random numbers created, and why is it considered difficult? in this I will explain how Random Number Generation Algorithm works
Answer in shot:
Quantum Random Number Generators (QRNGs) is the best Random Number Generator algorithm if our parameter is only generating true random number Leveraging principles of quantum mechanics to generate randomness, QRNGs promise true randomness and are theoretically unpredictable. They are at the cutting edge of technology and find applications in quantum cryptography and research.
Human mind
Well if I ask you to give me a random number you can do that easily. But when it comes to computers it is verry hard for them to do this. I hear you ask:
but amarnath why it is hard form them to create randomness? it’s verry easy for us to do it and doesn’t computer spouse to me smarter then us?
Yes, indeed, the truth is somewhat different from the perception of the masses; it is acknowledged that computers excel at certain tasks but are quite poor at others. Among these tasks, understanding emotions and responding emotionally, which are embedded in human nature, may be included.
but a verry good question to ask is why this fundamental happens ?
The human brain is an verry complex machine, governed by both deterministic processes (like neurophysiology) and seemingly random influences (like environmental interactions and internal states). When we attempt to generate a random number, our choice is influenced by unconscious processes, memories, current stimuli, and perhaps even inherent neural noise. This complexity can produce outcomes that are unpredictable, which might seem “random” from an externl viewpoint.
unlike computer does not have noise like this, matter of fact we have worked may years trying to reduce such kind of noise, because these type of noise disrupt the computation being performed by the computer, so let’s see how do we produce random number in the computers.
Random Number Generation Algorithm
To start with their are 2 Family of random number generation algorithm:
- Pseudorandom Number Generators (PRNGs)
- True Random Number Generators (TRNGs)
From hear I will give you verry detailed explanation of everything and discuss 5 example of algorithms rom each Family.
Pseudo Random Number Generation Algorithm (PRNGs)
Pseudorandom Number Generators are those algorithm which Generate a number which seems to be a random number but achily is not the way it works is by have a seed. seed is a part of PRNGs that allow us to recreate a random number. this sentence will be clear in a second.
Linear Congruential Generator (LCG)
A Linear Congruential Generator (LCG) is a type of pseudorandom number generator, which is widely used because of its simplicity and speed in generating sequences of numbers that approximate the properties of random numbers. The method generates a sequence of numbers using a linear equation, which is why it’s called “linear congruential.”
The formula for an LCG is:
Where:
Source wikipedia
The choice of the parameters a, c, and m greatly affects the quality and length of the pseudorandom number sequence. Good choices of these parameters can produce sequences that pass various statistical tests for randomness.
To start generating numbers, an initial value X (known as the “seed”) is needed. The seed determines the start point of the sequence, and using the same seed will always produce the same sequence of numbers, which is a useful property for debugging and testing purposes.
LCGs have several advantages, such as their simplicity to implement and understand, and their efficiency in generating numbers quickly. However, they also have limitations, such as the possibility of short cycles and patterns in the generated sequences if the parameters are not chosen carefully. For many applications requiring high-quality randomness, more sophisticated methods might be preferred over LCGs, but LCGs still find use in applications where simplicity and speed are more critical than the quality of randomness.
def lcg(seed, a=1103515245, c=12345, m=2**31):
"""
Linear Congruential Generator (LCG) for generating pseudorandom numbers.
:param seed: The initial seed value (X_0).
:param a: The multiplier.
:param c: The increment.
:param m: The modulus.
:return: A pseudorandom number.
"""
while True:
seed = (a * seed + c) % m
yield seedThe Mersenne Twister (MT19937)
The Mersenne Twister (MT19937) is a standout Random Number Generation Algorithm known for its exceptional performance and reliability. It generates pseudorandom numbers using a prime number-based period of 2^19937-1, ensuring sequences don’t repeat for a vast duration. This algorithm significantly surpasses Linear Congruential Generators (LCGs) by providing sequences with a high degree of randomness and uniform distribution, making it ideal for simulations, scientific research, and any application requiring robust random data generation.
With its 623-dimensional equidistribution and an extensive period, the Mersenne Twister ensures every 32-bit pattern appears uniformly, enhancing the quality of randomness. However, it’s not recommended for all cryptographic uses due to its deterministic nature, which can theoretically be reverse-engineered after observing enough output.
Adopted widely across various programming languages, its ease of implementation combined with high-quality output cements the Mersenne Twister’s position as a premier choice in Random Number Generation Algorithms for applications demanding accurate and extensive random data without repetition.
class MersenneTwister19937:
def __init__(self, seed=5489):
self.w, self.n, self.m, self.r = 32, 624, 397, 31
self.a = 0x9908B0DF
self.u, self.d = 11, 0xFFFFFFFF
self.s, self.b = 7, 0x9D2C5680
self.t, self.c = 15, 0xEFC60000
self.l = 18
self.f = 1812433253
self.MT = [0] * self.n
self.index = self.n + 1
self.lower_mask = (1 << self.r) - 1
self.upper_mask = (~self.lower_mask) & 0xFFFFFFFF
# Initialize the generator from a seed
self.MT[0] = seed
for i in range(1, self.n):
self.MT[i] = ((self.f * (self.MT[i-1] ^ (self.MT[i-1] >> (self.w-2))) + i) & 0xFFFFFFFF)
def extract_number(self):
if self.index >= self.n:
if self.index > self.n:
raise Exception("Generator was never seeded")
self.twist()
y = self.MT[self.index]
y = y ^ ((y >> self.u) & self.d)
y = y ^ ((y << self.s) & self.b)
y = y ^ ((y << self.t) & self.c)
y = y ^ (y >> self.l)
self.index += 1
return y & 0xFFFFFFFF
def twist(self):
for i in range(self.n):
x = (self.MT[i] & self.upper_mask) + (self.MT[(i+1) % self.n] & self.lower_mask)
xA = x >> 1
if x % 2 != 0:
xA = xA ^ self.a
self.MT[i] = self.MT[(i + self.m) % self.n] ^ xA
self.index = 0
# Example usage
if __name__ == "__main__":
rng = MersenneTwister19937(seed=123456789)
for _ in range(5):
print(rng.extract_number())
XORShift generators
XORShift generators excel in the domain of Random Number Generation Algorithms due to their straightforward, fast, and efficient approach. By employing XOR operations and bitwise shifts on a seed value, these algorithms scramble bits to produce pseudorandom numbers effectively. Their performance advantage comes from the use of simple operations that modern CPUs can execute quickly, making XORShift particularly suitable for high-throughput needs like simulations or gaming.
Different variations, such as XORShift+, XORShift*, offer tailored characteristics for specific requirements, enhancing their versatility. Despite their speed and simplicity, the randomness quality of XORShift generators depends significantly on the chosen parameters and initial seed. While they provide excellent performance for many tasks, their deterministic nature may not suit cryptographic applications requiring high unpredictability levels. Overall, XORShift generators represent a compelling choice for fast and efficient random number generation, provided their limitations are carefully considered.
class XORShift32:
def __init__(self, seed=123456789):
self.state = seed # Seed should be non-zero
def xorshift32(self):
"""Performs the XORShift algorithm."""
x = self.state
x ^= (x << 13) & 0xFFFFFFFF # Apply XOR and ensure 32-bit unsigned
x ^= (x >> 17) & 0xFFFFFFFF
x ^= (x << 5) & 0xFFFFFFFF
self.state = x
return x
def random(self):
"""Returns a random float in the range [0.0, 1.0)."""
return self.xorshift32() / 0xFFFFFFFF
# Example usage
generator = XORShift32(seed=42)
for _ in range(5):
print(generator.random())
Blum Blum Shub (BBS)
Blum Blum Shub (BBS), Algorithm that’s the cryptographer’s equivalent of a secret handshake. Picture this: you take two prime numbers, both with a penchant for drama since they’re of the type that leaves a remainder of 3 when divided by 4. Mix these primes in a mathematical cocktail to form N, their product, which serves as the playground for our random number party.
The recipe starts with a seed, the mysterious guest that kicks off the festivities. This seed, when squared and then modestly dressed with a modulo N operation, begins a dance of numbers. But BBS, being the tease that it is, only winks the least significant bit at you from each number’s sequence, serving up bits of randomness one at a time.
Why such a coy approach? Because BBS isn’t just about generating random numbers; it’s about doing so with a cloak of cryptographic security. This algorithm is the introverted genius of Random Number Generation Algorithms, offering numbers so unpredictable, they’re like the plot twists in a telenovela written by a quantum physicist.
In essence, Blum Blum Shub is your go-to for when you need randomness that’s not just any randomness, but the kind that could secure the digital equivalent of Fort Knox. It’s the algorithm for those who like their random numbers like they like their espionage: cryptographically secure and wrapped in layers of mathematical intrigue.
def blum_blum_shub(seed, n_bits):
"""
Blum Blum Shub (BBS) Pseudorandom Number Generator.
:param seed: The initial seed (must be relatively prime to N).
:param n_bits: The number of bits to generate.
:return: A pseudorandom number generated by BBS.
"""
# Example primes p and q. In a real application, these should be large
# and satisfy p % 4 == 3 and q % 4 == 3.
p = 11
q = 19
N = p * q
# The seed value should be relatively prime to N (no common factors other than 1)
x = seed
bits = []
# Generate n_bits of randomness
for _ in range(n_bits):
x = pow(x, 2, N) # x = x^2 mod N
bits.append(x % 2) # Extract the least significant bit
# Convert the bit list to an integer
return int(''.join(str(bit) for bit in bits), 2)
# Example usage
seed = 7 # Choose an appropriate seed
n_bits = 10 # Number of bits to generate
random_number = blum_blum_shub(seed, n_bits)
print(f"Generated number: {random_number}")
Fortuna
Fortuna, the Random Number Generation Algorithm equivalent of a Swiss Army knife, is the brainchild of Bruce Schneier and Niels Ferguson. Think of it as the ultimate randomness chef, whipping up cryptographic randomness from the mundane movements of your mouse to the precise timing between your keyboard clicks. Fortuna is not just one algorithm; it’s a sophisticated ensemble of multiple generators each collecting bits of entropy, like secret ingredients, from various sources.
This algorithm stands out for its adaptability and resilience. It’s like having a team of chefs where, even if one starts using salt instead of sugar, the banquet of randomness still tastes as unpredictable as ever. Fortuna ensures that even if some sources of entropy get compromised, the overall randomness remains top-notch, making it a go-to for securing everything from online transactions to digital communications.
In the bustling world of Random Number Generation Algorithms, Fortuna is your reliable, behind-the-scenes maestro, ensuring that every piece of data enjoys its moment of unpredictability before joining the stream of secure, cryptographic randomness.
import os
import time
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util import Counter
class SimplifiedFortuna:
def __init__(self):
self.key = os.urandom(32) # Generate a 256-bit key
self.counter = Counter.new(128)
self.cipher = AES.new(self.key, AES.MODE_CTR, counter=self.counter)
self.entropy_pools = [bytearray() for _ in range(32)]
self.reseed_counter = 0
self.last_reseed_time = time.time()
def add_entropy(self, source_id, entropy):
# Add entropy to the appropriate pool; source_id determines which pool
if source_id < 0 or source_id >= len(self.entropy_pools):
raise ValueError("Invalid source ID")
self.entropy_pools[source_id] += entropy
def reseed(self):
# Combine entropy from pools and reseed the generator
seed_material = b''
for pool in self.entropy_pools:
if pool:
seed_material += SHA256.new(pool).digest()
pool.clear()
self.key = SHA256.new(self.key + seed_material).digest()
self.cipher = AES.new(self.key, AES.MODE_CTR, counter=self.counter.reset())
self.reseed_counter += 1
self.last_reseed_time = time.time()
def generate_random_data(self, nbytes):
# Ensure periodic reseeding
if time.time() - self.last_reseed_time > 60 or self.reseed_counter == 0:
self.reseed()
return self.cipher.encrypt(b'\x00' * nbytes)
# Example usage
fortuna = SimplifiedFortuna()
# Simulate adding entropy from different sources
fortuna.add_entropy(0, os.urandom(64))
fortuna.add_entropy(1, str(time.time()).encode())
# Generate random data
random_data = fortuna.generate_random_data(16)
print(random_data.hex())
True Random Number Generators (TRNGs)
True Random Number Generators (TRNGs) are the mavericks of the Random Number Generation Algorithm universe, sourcing their unpredictability directly from physical phenomena. Unlike their sibling, the Pseudorandom Number Generator (PRNG), which operates on mathematical formulas, TRNGs tap into the inherent randomness of the physical world—be it quantum mechanics, atmospheric noise, or electronic circuit behavior.
The catch with TRNGs is that they’re not something you can conjure up with a few lines of code. Why? Because they rely on hardware to detect and measure physical processes. It’s like trying to download a pizza; you can’t code your way into generating true randomness without a physical process to base it on.
never the less hear is something for you to research
- Quantum Random Number Generators (QRNGs): These devices use quantum phenomena, such as the random polarization states of photons, to generate true random numbers. The inherent unpredictability of quantum mechanics makes these generators capable of producing high-quality randomness. QRNGs are often used in cryptographic applications where the security depends on the unpredictability of random numbers.
- Atmospheric Noise Generators: These TRNGs use noise from natural atmospheric phenomena, such as electrical discharges during thunderstorms, as a source of randomness. The unpredictability of atmospheric noise can be converted into random numbers through suitable analog-to-digital conversion processes. Websites and services requiring randomness for non-critical applications sometimes use atmospheric noise to generate random numbers.
- Radioactive Decay Generators: The decay of radioactive materials is a quantum process that is fundamentally random. By measuring the time between decay events or the number of particles emitted over a certain period, these generators can produce true random numbers. Due to the nature of radioactive decay, these generators are highly unpredictable and can be used for cryptographic applications.
- Shot Noise Generators: Shot noise or quantum noise in electronic circuits, caused by the discrete nature of charge carriers (like electrons), can be used to generate randomness. For instance, the random fluctuations in the current passing through a semiconductor diode can be measured and converted into random numbers. This method exploits physical noise inherent in electronic components.
- Thermal Noise Generators (Johnson-Nyquist Noise): Thermal noise is generated by the random motion of electrons in conductors due to their thermal energy. By measuring this noise, which is present in all electrical circuits to some extent, and converting it into a digital form, true random numbers can be generated. Thermal noise generators are widely used due to their reliability and the ease of generating noise in electronic components.
The exploration of random number generation in computing showcases a significant dichotomy: while humans can intuitively produce random numbers, computers require sophisticated algorithms to achieve similar randomness. This article navigates through the complexities of Random Number Generation (RNG), distinguishing between Pseudorandom Number Generators (PRNGs) and True Random Number Generators (TRNGs), and further illuminates the cutting-edge Quantum Random Number Generators (QRNGs). These QRNGs epitomize the pinnacle of RNG technology, utilizing quantum mechanics to ensure genuine randomness, crucial for secure cryptographic applications.
Through examining algorithms such as the Linear Congruential Generator, Mersenne Twister, XORShift, Blum Blum Shub, and Fortuna, the piece articulates the pivotal role of randomness in computing for simulations, security, and beyond. It highlights the inventive human efforts to simulate the unpredictability of nature within digital systems, illustrating the ongoing challenge and ingenuity in creating true randomness through technology.
Leave a Reply