Building Cryptography: Lego Bricks of Modern Security

Preface

This article is part of my “Introduction to Cryptography” series, cross-published from my Substack. If you enjoy clear explainers with visuals, animations, and Python demos, you can subscribe here 👉 [https://dmytrohuz.substack.com/].

Cryptography doesn’t start with AES. It starts with the Lego bricks: pseudo-random generators (PRG), pseudo-random functions (PRF), and pseudo-random permutations (PRP).

In this guide, we’ll cover:
• Why we can’t rely only on stream ciphers
• How randomness expands into usable cryptographic functions
• The transition from PRG → PRF → PRP
• Visual animations + Python snippets that bring the concepts to life

Introduction

In the previous section, we looked at stream ciphers: fast, infinite, and unpredictable. But are they enough to secure everything in our digital world? Not really. Stream ciphers are powerful, but they are not a silver bullet. They fail in several important scenarios:

1. Non-invertible encryption – Sometimes we need encryption that cannot be reversed (e.g., storing passwords). Stream ciphers always decrypt what they encrypt.
2. Integrity and authentication – Stream ciphers hide content but cannot prevent tampering or impersonation. We need tools to check whether a message was changed and to confirm its sender.
3. Reuse of keys across multiple messages – With stream ciphers, the output depends only on the secret key. Using the same key for multiple messages risks reusing the keystream. We need constructions where input and key both matter.

Clearly, building a custom cipher for every special case would be impossible: each would need years of testing, breaking, and patching. Instead, cryptographers chose a different path:

👉 Build a small set of secure primitives — each with well-defined properties and proofs of security — and then combine them as Lego blocks to solve different real-world problems.

In this article we’ll explore three fundamental primitives:

• PRG (Pseudo-Random Generator) – stretches a short random seed into a long, random-looking sequence.
• PRF (Pseudo-Random Function) – produces a fixed-size random-looking output from a key and an input.
• PRP (Pseudo-Random Permutation) – a PRF that is invertible: outputs can be reversed if you know the key.

We’ll also see how each can be built from the previous one. That’s the elegant chain:

If PRG is possible and secure → PRF is possible and secure → PRP is possible and secure.

By the end, you’ll have an intuitive map of these primitives, working code samples, and animations that bring the theory to life.

PRG: Pseudo-Random Generator

We’ve already met PRGs before. They are the foundation of modern cryptography:

• Input: a short truly random seed.
• Output: a much longer string that looks random.

For this article, we’ll just recap by showing one practical construction: a PRG that doubles the seed length using HMAC.

import hmac
import hashlib

def prg_double(seed):
    """
    HMAC-based Pseudo-Random Generator commonly used in modern ciphers

    Args:
        seed (bytes): The seed value

    Returns:
        bytes: Random bytes twice the length of the seed
    """
    length = len(seed) * 2

    output = b''
    counter = 0

    # Generate output until we have enough bytes
    while len(output) < length:
        counter_bytes = counter.to_bytes(4, byteorder='big')
        h = hmac.new(seed, counter_bytes, hashlib.sha256)
        output += h.digest()
        counter += 1    
    return output[:length]

# Example usage
if __name__ == "__main__":
    seed = "hello world"
    random_str = prg_double(seed.encode('utf-8'))
    print(f"Seed: {seed}")
    print(f"Seed length (bytes) (length {len(seed.encode('utf-8'))}): {seed.encode('utf-8')}")
    print(f"Random string (bytes) (length {len(random_str)}): {random_str}")

This is our basic building block — and the seed for everything else.

---

Pseudo-Random Function (PRF)

A PRF is the natural next step after a PRG. Instead of just stretching randomness, we want a function that behaves like this:

• It takes a secret key and an input.
• With the same key and input, it always returns the same output.
• To anyone without the key, the outputs look completely random.

Formally: for a key k and input x, the function Fₖ(x) is deterministic but indistinguishable from a truly random function.

---

Why do we need PRFs?

PRFs are everywhere in modern cryptography:

• Message authentication codes (MACs): compute a tag t = Fₖ(m) so any tampering can be detected.
• Key derivation: derive fresh, independent keys k₁, k₂ … from one master key.
• Counters into keystreams: avoid keystream reuse by turning counters or nonces into blocks Fₖ(ctr).
• Bigger constructions: PRPs (via Feistel), KDFs, and many secure protocols use PRFs as their inner engines.

Without PRFs, we couldn’t authenticate messages, manage keys securely, or even build block ciphers.

From PRG to PRF: the GGM construction

The beautiful part of theory is that we don’t need to assume PRFs “out of nowhere.”

The Goldreich–Goldwasser–Micali (GGM) construction shows:

👉 If secure PRGs exist, then secure PRFs exist.

The idea:

1. Start with a seed (the secret key).
2. Use the PRG to expand it into two new seeds.
3. Input bits decide which path you follow: 0 = left child, 1 = right child.
4. After consuming all input bits, the seed you reach becomes the PRF output.

Think of it as growing a binary tree of seeds, and your input walks a path through the tree.

Feel free to download an animation and play with it on your own.

This gives us a PRF whose security reduces directly to the PRG’s security. That’s a profound result: PRFs are guaranteed if PRGs exist.

Implementation demo

Here’s a fixed-parameter Python implementation of the GGM PRF:

#!/usr/bin/env python3
"""
GGM PRF (fixed-parameter version)
---------------------------------
- Key size:    128 bits (16 bytes) exactly
- Output size: 128 bits (16 bytes) exactly
- Domain:      bitstrings (you can pass str of '0'/'1')
"""

from prg import prg_double

KEY_LEN = 16  # 128-bit key and output
OUT_LEN = 16

def ensure_bits(x) -> str:
    if isinstance(x, str):
        if not set(x) <= {"0","1"}:
            raise ValueError("bit string must contain only '0'/'1'")
        return x
    raise TypeError("x must be str of bits, bytes, or int")

# ---- Fixed-parameter GGM PRF: F_k(x) -> 16 bytes ----
def ggm_prf_128(key: bytes, x) -> bytes:
    if not isinstance(key, (bytes, bytearray)) or len(key) != KEY_LEN:
        raise ValueError(f"key must be exactly {KEY_LEN} bytes (128 bits)")
    seed = bytes(key)
    path = ensure_bits(x)

    for i, bit in enumerate(path):
        lr = prg_double(seed)           # 32 bytes: left||right
        seed = lr[:OUT_LEN] if bit == "0" else lr[OUT_LEN:]
        print(f"  Level {i}: bit={bit}  seed={seed.hex()}")

    # Fixed output length: 16 bytes
    return seed  # 128-bit PRF output

def _demo(bits: str) -> None:
    key = bytes.fromhex("00112233445566778899aabbccddeeff")

    print(f"key    = {key.hex()}")
    print(f"x      = {bits}  (len={len(bits)} bits)")

    y = ggm_prf_128(key, bits)

    print(f"F_k(x) = {y.hex()}  ({len(y)} bytes)")

if __name__ == "__main__":
    print("Demo 1:")
    _demo("0101")

GGM is not the only way

GGM is powerful as a proof of existence and a teaching tool, but it’s not what systems use in practice. Real-world PRFs are built differently:

• HMAC (with SHA-2/3): deployed everywhere and modeled as a PRF.
• HKDF: key derivation built on HMAC.
• AES as a PRF: Fₖ(x) = AESₖ(x) , with variants like CMAC or PMAC for authentication.

These are faster, widely standardized, and hardened by decades of cryptanalysis.

Reflection

We can treat GGM as the conceptual golden standard of PRFs, much like the one-time pad is for stream ciphers. It isn’t deployed, but it proves that PRFs are possible and gives us a clean reference point. Practical PRFs like HMAC or AES can then be understood as flesh built on this soul.

Pseudo-Random Permutation (PRP)

A PRP is like a PRF with one extra property: invertibility.

• A PRF maps inputs to outputs but doesn’t guarantee you can reverse the process.
• A PRP is a PRF that’s also a bijection: every input block maps to a unique output block, and every output maps back to its input.

Formally: for a key k, a PRP Pₖ is a permutation over fixed-length blocks (e.g. 128 bits). Both Pₖ(x) and its inverse Pₖ⁻¹(y) are efficiently computable if you know the key.

---

Why do we need PRPs?

Invertibility is what makes encryption and decryption possible. With a PRF you can authenticate or derive, but you can’t take ciphertext and recover plaintext. PRPs give us:

• Block ciphers like AES — encryption that can always be undone with the same key.
• Secure shuffling of fixed-size blocks.
• Building blocks for modes of operation (CBC, CTR, GCM), which rely on encryption/decryption symmetry.

Without PRPs, we couldn’t have reversible encryption schemes.

---

From PRF to PRP: the Feistel network

So how do we take a PRF (one-way) and make it invertible? The answer is the Feistel construction.

1. Split the input block into two halves: L₀, R₀.
2. Compute: Lᵢ₊₁ = Rᵢ Rᵢ₊₁ = Lᵢ ⊕ Fₖ(Rᵢ)
3. Repeat for several rounds.

The magic:

• Even though the round function F (a PRF) is not invertible by itself, the whole Feistel structure is.
• You can always recover Lᵢ, Rᵢ from Lᵢ₊₁, Rᵢ₊₁ .
• With enough rounds, the permutation looks indistinguishable from random.

Feel free to download an animation and play with it on your own.

Example intuition (no numbers)

Think of it as a dance between halves:

• One half moves forward unchanged.
• The other half is “mixed” with a pseudo-random function.

• Then they swap roles.

  Round after round, both halves keep carrying and mixing information, until the whole block is scrambled but reversible.

---

Implementation demo

Here is the full implementation:

#!/usr/bin/env python3
from prf import prf

class PRP:
    def __init__(self, key, rounds=4):
        """Initialize PRP with a key and number of rounds.

        Args:
            key (bytes): The secret key (must be exactly 16 bytes/128 bits for prf)
            rounds (int): Number of Feistel rounds
        """
        # Ensure key is exactly 16 bytes as required by prf.py
        if len(key) != 16:
            raise ValueError("Key must be exactly 16 bytes (128 bits)")
        self.key = key
        self.rounds = rounds

    def _round_function(self, right_half):
        """Round function based on PRF from prf.py.

        Args:
            right_half (bytes): Right half of the current state            
        Returns:
            bytes: Output of the round function
        """
        # Use the entire right_half as input to the PRF
        # Convert each byte to its 8-bit binary representation
        if right_half:
            # Convert all bytes to bits
            bits = ''.join(format(byte, '08b') for byte in right_half)
        else:
            # Default if input is empty
            bits = "0000"

        # Apply the PRF from prf.py using all bits from right_half
        return prf(self.key, bits)

    def encrypt(self, plaintext):
        """Encrypt a block using the Feistel network.

        Args:
            plaintext (bytes): Input block to encrypt

        Returns:
            bytes: Encrypted block with padding byte if needed
        """
        # Ensure even length by padding if necessary
        if len(plaintext) % 2 != 0:
            # Add padding indicator as the last byte
            plaintext = plaintext + b'\x01'
        else:
            # Even length, add padding block to indicate no padding needed
            plaintext = plaintext + b'\x00'

        # Split the plaintext into two equal halves
        half_size = len(plaintext) // 2
        left = plaintext[:half_size]
        right = plaintext[half_size:]

        # Feistel rounds
        for _ in range(self.rounds):
            # Apply round function to right half
            f_output = self._round_function(right)
            # XOR the output with left half
            new_right = bytes(a ^ b for a, b in zip(left, f_output[:half_size]))
            # Swap halves for next round
            left = right
            right = new_right

        # For an even number of rounds, we need to swap back for decryption to work properly
        if self.rounds % 2 == 0:
            return right + left
        else:
            return left + right

    def decrypt(self, ciphertext):
        """Decrypt a block using the Feistel network.

        Args:
            ciphertext (bytes): Input block to decrypt

        Returns:
            bytes: Decrypted block with padding removed
        """
        # Split the ciphertext into two equal halves
        half_size = len(ciphertext) // 2
        left = ciphertext[:half_size]
        right = ciphertext[half_size:]

        # Feistel rounds in reverse
        for i in range(self.rounds-1, -1, -1):
            # Apply round function to right half
            f_output = self._round_function(right)
            # XOR the output with left half
            new_right = bytes(a ^ b for a, b in zip(left, f_output[:half_size]))
            # Swap halves for next round
            left = right
            right = new_right

        # For an even number of rounds, we need to swap back
        if self.rounds % 2 == 0:
            decrypted = right + left
        else:
            decrypted = left + right

        # Remove padding and return
        return decrypted[:-1]


# Example usage
if __name__ == "__main__":
    # Create a 16-byte key (128 bits)
    key = bytes.fromhex("00112233445566778899aabbccddeeff")

    # Create a PRP instance with 4 rounds
    prp = PRP(key, rounds=4)

    # Create a plaintext (must be even length for splitting)
    plaintext = b"This is a test!"  # 16 bytes

    print(f"Original: {plaintext}")
    print(f"Length: {len(plaintext)} bytes")

    # Encrypt
    ciphertext = prp.encrypt(plaintext)
    print(f"Encrypted (hex): {ciphertext.hex()}")
    print(f"Encrypted length: {len(ciphertext)} bytes")

    # Decrypt
    decrypted = prp.decrypt(ciphertext)
    print(f"Decrypted: {decrypted}")
    print(f"Decrypted length: {len(decrypted)} bytes")

    # Compare byte by byte
    if len(plaintext) == len(decrypted):
        for i in range(len(plaintext)):
            if plaintext[i] != decrypted[i]:
                print(f"Mismatch at position {i}: {plaintext[i]} vs {decrypted[i]}")
    else:
        print(f"Length mismatch: {len(plaintext)} vs {len(decrypted)}")

    # Verify
    if plaintext == decrypted:
        print("Success: Encryption/decryption verified!")
    else:
        print("Failed: Decryption didn't match original!")

(Note: this is just a toy; real ciphers use many rounds, carefully designed PRFs, and strong diffusion.)

---

Reflection

PRPs are the natural endpoint of our chain:

• PRG → PRF → PRP.
• From stretching randomness, to keyed functions, to invertible permutations.
• PRPs give us encryption that can be undone — the core of block ciphers.

Just like GGM proves PRFs are possible, the Feistel construction proves that PRPs are possible from PRFs. Real-world block ciphers (DES, AES) go beyond this basic template, but the Feistel idea is the conceptual backbone of why reversible, secure encryption exists.

---

What is next?

We’ve unlocked the core techniques of our cryptographic “combat training.” Next up: the real combos — the block ciphers and modes that defenders actually use in the field. In the next article we’ll study the most important block ciphers (AES, DES/3DES history), explain modes like CTR, CBC, and GCM, and build working implementations from scratch. Bring curiosity — and your code editor.
...And subscribe to do not miss the next article: https://dmytrohuz.substack.com/ ;)