Post-Quantum

Every public-key system in production today — RSA, ECDSA, Ed25519, ECDH, X25519 — is broken by a sufficiently large quantum computer. Not "weakened." Broken. Polynomial-time recovery of the private key from the public key. The math is settled; only the engineering of building the quantum computer is in question.

This lesson is about Shor's algorithm (the threat), the harvest-now-decrypt-later attack model, NIST's PQC standardisation, and the hybrid schemes you'll see in production today.

Shor's algorithm

In 1994, Peter Shor showed that a quantum computer can factor an n-bit integer in O((log n)³) gates. The same algorithm solves the discrete logarithm problem (over multiplicative groups and elliptic curves alike) in polynomial time.

Translated to crypto:

• RSA: factor n, recover (p, q), derive d. Game over.
• DSA / DH: solve discrete log in (Z/pZ)*. Game over.
• ECDSA / ECDH: solve elliptic-curve discrete log. Game over.

A 2048-bit RSA key requires roughly 4000 logical qubits plus error-correction overhead (current estimates land somewhere in the millions of physical qubits). We're not there yet — IBM's 2024 chip is around 1,121 qubits, none of them logical. But the trajectory is real, and most experts treat 10–20 years as a reasonable planning horizon for cryptographically-relevant quantum computers (CRQC).

Symmetric crypto is mostly fine

Quantum doesn't trash everything. Grover's algorithm gives a √n speedup on brute-force search:

• AES-128 → effective security drops to 64-bit. Not great. Move to AES-256 (which still gives 128-bit post-quantum security).
• SHA-256 → effective collision resistance halves to 128-bit. Still safe for most uses; SHA-384 / SHA-512 buys margin.
• HMAC, GCM, ChaCha20-Poly1305 — fine with appropriate key sizes.

The big migration is only the public-key parts. Symmetric crypto and hashes need bigger keys, not different algorithms.

Harvest-Now-Decrypt-Later (HNDL)

This is why post-quantum matters NOW even though the quantum computer doesn't exist yet:

An adversary records every encrypted session crossing their network today. In 15 years, when they have a quantum computer, they decrypt everything they've stored.

For data with long-tail confidentiality requirements — medical records, classified diplomatic cables, source code with embargoed disclosures, intellectual property — this is a credible attack today. Capturing the ciphertext is cheap; storing it is cheap; waiting 15 years is fine.

The defence is to switch to PQC algorithms for the long-secrecy traffic now, even though we expect classical algorithms to remain secure for years. NSA, GCHQ, and other state-level actors have already begun this transition for top-secret material.

NIST PQC standardisation

In 2016, NIST started a competition to standardise post-quantum primitives. After multiple rounds and 6+ years of public cryptanalysis:

FIPS	Standard name	Original name	Purpose	Family
203	ML-KEM	CRYSTALS-Kyber	Key encapsulation	Module-LWE (lattices)
204	ML-DSA	CRYSTALS-Dilithium	Digital signatures	Module-LWE (lattices)
205	SLH-DSA	SPHINCS+	Digital signatures (backup)	Hash-based
(in progress)	FN-DSA	Falcon	Digital signatures	NTRU lattices

ML-KEM (Kyber) is the new ECDH replacement — a Key Encapsulation Mechanism. Instead of "exchange to derive a shared secret," you "encapsulate a random session key under the recipient's public key" and they decapsulate it.

ML-DSA (Dilithium) is the new Ed25519 / ECDSA replacement for signatures.

Both are based on the Module Learning With Errors (MLWE) problem — an entirely different mathematical hardness assumption than factoring or discrete log. If a quantum computer arrives, MLWE survives.

SLH-DSA (SPHINCS+) is a stateless hash-based signature scheme. It's slower and has bigger signatures, but its security depends only on the underlying hash function — no fancy math assumption to break. NIST keeps it as a fallback in case of unforeseen attacks on lattice-based schemes.

Hybrid schemes

The careful answer to "we don't know if PQC will be broken in some unforeseen way" is hybrid: combine a classical primitive with a PQC primitive such that an attacker has to break both to succeed.

For TLS 1.3 key exchange:

client_hello: [supported_groups: x25519+kyber768, x25519, kyber768]

Hybrid X25519+Kyber768:
  shared_secret = HKDF-Extract(X25519_secret || Kyber_secret)

If X25519 is broken (say, a classical breakthrough), Kyber still holds. If Kyber is broken (say, an unforeseen lattice attack), X25519 still holds. Both must fall to compromise the session.

This is exactly what Cloudflare, Google Chrome, Apple iMessage, and Signal have rolled out. As of 2024–2025, a meaningful fraction of TLS 1.3 sessions on the public internet now run X25519+Kyber hybrid — usually invisible to the application, configured at the proxy/CDN layer.

Where you'll see it	Status
Cloudflare → origin	Default in 2023
Chrome → public web	Rolled out in 2024 (X25519MLKEM768)
Apple iMessage	PQ3 protocol shipped 2024
Signal Protocol	PQXDH released 2024
AWS KMS	Hybrid TLS available to KMS endpoints
OpenSSH	post-quantum hybrid since 9.0

Migration challenges

PQC isn't a drop-in. Real engineering pain:

Bigger keys, signatures, ciphertexts.

Primitive	Public key	Signature / ciphertext
Ed25519	32 B	64 B
X25519	32 B	32 B (DH share)
Dilithium-3 (ML-DSA-65)	1952 B	3309 B
Kyber-768 (ML-KEM-768)	1184 B	1088 B (ciphertext)

A TLS 1.3 ClientHello has historically been 200-500 bytes. Hybrid X25519+Kyber768 pushes it past 1 KB — sometimes triggering MTU / packet fragmentation issues that older networking gear can't handle. Cloudflare wrote a great deep-dive on the bugs they hit at scale.

Signature size. Code-signing pipelines today emit ~64-byte signatures. Dilithium signatures are ~3 KB. Multiply that across every commit, every container layer, every CI artifact. Storage and bandwidth costs are real.

Implementation complexity. PQC primitives have side-channel issues that are different from classical ones — careful constant-time implementations are still maturing. Use vetted libraries; don't roll your own.

What you should do today

A practical migration roadmap:

1. Inventory your asymmetric usage. Where is RSA / ECDSA / ECDH actually called? You can't migrate what you can't find.
2. Identify long-secrecy data. Anything you'd be unhappy seeing decrypted in 2040 needs PQC priority.
3. Enable hybrid TLS on edge. CDN + load-balancer deployments are the lowest-effort win — your apps don't change.
4. Migrate signing in stages. Start with low-risk pipelines (CI internal artifacts) before code-signing certs.
5. Track NIST. FIPS 203, 204, 205 are stable; 206 (Falcon) is still in flight. Library support is improving monthly.

This is one of the largest crypto migrations in history — comparable to the SHA-1 → SHA-2 → SHA-3 push, but bigger. Start now.

What this lesson asks of you

The playground walks you through five PQC scenarios — TLS 1.3 hybrid choice, signature replacement for code-signing, KMS hybrid mode, long-secrecy threat triage, and recognising HNDL-vulnerable systems. The visualizer shows the timeline of quantum threat estimates next to NIST standardisation milestones, with key/signature size comparisons against the classical equivalents.