Notebook 00b — Classical crypto recap

Notebook 00b — Classical crypto recap#

A 10-minute refresher on the primitives this book replaces. A reader who has heard the word “RSA” but never used it should finish this notebook knowing what a KEM is and what role it plays.

The three flavors of crypto#

Type	What it does	Examples
Symmetric encryption	Same key encrypts and decrypts. Fast, needs a shared secret.	AES, ChaCha20
Asymmetric (public-key)	Public key ≠ private key. Anyone can send you a secret; only you can read.	RSA, ECDH, ML-KEM
Hash / MAC / Signature	Integrity and authentication — “this came from X, unmodified”.	SHA-256, HMAC, ECDSA, ML-DSA

The handshake problem#

Symmetric crypto is fast, but requires a shared key. How do two strangers on the internet agree on a secret key without meeting first? That’s what asymmetric crypto solves.

KEM — Key Encapsulation Mechanism#

A KEM is a specific asymmetric pattern with three operations:

(ek, dk) = KeyGen() — generate an encapsulation key (public) and decapsulation key (private).
(K, ct) = Encaps(ek) — using someone’s public key, produce a shared secret K and a ciphertext ct.
K = Decaps(dk, ct) — the holder of the private key recovers the same K.

Both parties now hold the same 32-byte secret. They feed it into a symmetric cipher (AES-GCM) to actually transmit data.

import os, hashlib

def toy_keygen():
    dk = os.urandom(32)                # "private"
    ek = hashlib.sha256(dk).digest()   # "public" — in a real KEM, ek can't reveal dk
    return ek, dk

def toy_encaps(ek):
    m = os.urandom(32)                 # random message
    ct = hashlib.sha256(ek + m).digest()
    K  = hashlib.sha256(b"secret" + m).digest()
    return K, ct

# ToyDecaps cannot actually work here (because ek is derived from dk via a one-way hash,
# so decaps has no way to recover m from ct). The point is the *shape* of the API:
ek, dk = toy_keygen()
K1, ct = toy_encaps(ek)
print("ek size:", len(ek), "ct size:", len(ct), "K size:", len(K1))
print("Both sides would now hold the same K — our toy can't decapsulate, but ML-KEM can.")

ek size: 32 ct size: 32 K size: 32
Both sides would now hold the same K — our toy can't decapsulate, but ML-KEM can.

KEM vs Public-Key Encryption vs Signature#

KEM: agree on a random key. That key is then used for symmetric encryption. ML-KEM is a KEM.
Public-Key Encryption (PKE): directly encrypt a message with the public key. ML-KEM contains a PKE inside (called K-PKE), but the user-facing API is a KEM.
Signature: prove “I signed this message”. Not for secrecy — for authenticity. ML-DSA is a signature.

How a real TLS 1.3 handshake uses KEMs#

Simplified: when your browser connects to a server,

Server sends its public key ek.
Browser calls Encaps(ek) → gets (K, ct). Sends ct.
Server calls Decaps(dk, ct) → gets the same K.
Both derive AES keys from K. All further traffic is AES-GCM.

Today, ek is an ECDH (X25519) public key. In hybrid deployments (Chrome since 2023), it’s X25519 + ML-KEM concatenated — safe if either part survives cryptanalysis. Notebook 08 walks through a hybrid implementation.

What Shor breaks#

RSA relies on: factoring large integers is hard. Shor factors them in polynomial time → RSA broken.
ECDH/ECDSA rely on: elliptic-curve discrete logarithm is hard. Shor solves discrete log in polynomial time → ECC broken.
Both are algebraic problems with exploitable structure.
Lattice problems (LWE, SIS) have no known polynomial quantum algorithm — that is the post-quantum bet.

Ready for the math primer? → 00c_math_toolbox. Already comfortable with mod-q arithmetic and vectors? Skip ahead to 01_lattice_intro.