Pseudrandom Generators

A fundamental tool used to achieve computational security is the pseudorandom generator (PRG). Pseudorandom generators are algorithms that generate sequences of bits that appear to be random but are, in fact, deterministically derived from a shorter random seed. These generators act as a crucial component in many cryptographic constructions, allowing us to produce longer, seemingly random streams of data from a shorter, truly random seed.

Why PRGs and not true randomness? True randomness is hard to achieve in practice because it typically requires measuring physical processes that are inherently unpredictable (such as quantum phenomena). These processes can be time-consuming and resource-intensive. On the other hand, PRGs are computationally efficient and can quickly generate large amounts of pseudo-random data with relatively little computational overhead.

import random
# Generate a random float between 0 and 1
random_float = random.random()
# This is not truly random, but there are ways via third party libraries to get true randomness that compute the randomness on a different machine via quantum phenomena.

The security of pseudorandom generators relies on the assumption that the output they produce is indistinguishable from true randomness, even for computationally bounded adversaries. If a PRG meets this property, it is considered cryptographically secure. However, designing provably secure pseudorandom generators is a non-trivial task, as it requires rigorous mathematical proofs and the ability to withstand sophisticated attacks.

With a secure pseudorandom generator, it becomes possible to use a shorter, random seed to produce a long stream of bits that can be used as a key for encryption. This overcomes the key length limitations of one-time pads and enables the use of symmetric encryption schemes with strong computational security guarantees.

One widely used application of pseudorandom generators is in stream ciphers, where the key stream generated by the PRG is combined with the plaintext using a bitwise XOR operation to produce the ciphertext. Stream ciphers are efficient and well-suited for secure communication in scenarios where data is transmitted in a continuous flow, such as real-time communication or data streaming.