Chapter 17 — Cryptography concepts | Bachelor's Quantum and post-quantum security

Open, free learning for anyone who wants to protect people and technology. No account is required to read this text or its worked answers.

Chapter 17 — Cryptography concepts

Lesson map

Lesson 17 published. Map, example, EX033.

flowchart TD
  N0["Learning outcomes"]
  N1["17.1 The toolbox"]
  N2["17.2 The NIST standards"]
  N3["17.3 Practical activity — Lab L"]
  N4["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4
  N4 --> EX["Worked example"]
  EX --> Q["Exercise EX033"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["17.1 The toolbox"]
  N2["17.2 The NIST standards"]
  N3["17.3 Practical activity — Lab L"]
  N4["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX033"]

[Learning outcomes]
    |
    v
[17.1 The toolbox]
    |
    v
[17.2 The NIST standards]
    |
    v
[17.3 Practical activity — Lab L]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX033]

Learning outcomes

You will (1) distinguish symmetric encryption, hash functions, MACs, key exchange, KEMs and signatures; (2) explain security levels and NIST's post-quantum categories; (3) build and break a Lamport one-time signature; and (4) name the three final NIST post-quantum standards.

17.1 The toolbox

Symmetric encryption (AES) uses one shared key; hash functions (SHA-2, SHA-3) compress data to a fingerprint; MACs (HMAC) prove integrity with a shared key; key exchange (Diffie–Hellman) lets two parties derive a shared secret over a public channel; a key-encapsulation mechanism (KEM) lets one party encapsulate a fresh secret to another's public key; signatures let anyone verify that the holder of a private key approved a message. Quantum computers threaten key exchange, public-key encryption and signatures based on factoring and discrete logarithms; symmetric primitives and hashes need at most larger parameters.

17.2 The NIST standards

In August 2024 NIST published three post-quantum standards: FIPS 203 ML-KEM, a lattice-based KEM with parameter sets ML-KEM-512, -768 and -1024; FIPS 204 ML-DSA, a lattice-based signature; and FIPS 205 SLH-DSA, a stateless hash-based signature. Earlier, SP 800-208 approved the stateful hash-based signatures LMS and XMSS. NIST defines security categories 1–5 by comparison with breaking AES-128, SHA-256, AES-192, SHA-384 and AES-256; ML-KEM-768 targets category 3.

For HCU, category three parameter sets are the common starting point, since they offer a comfortable margin at moderate size.

17.3 Practical activity — Lab L

The Lamport scheme signs one message by revealing, for each bit of its hash, one of two secret values whose hashes form the public key.

# Lab L (ch 17): Lamport one-time signatures from SHA-256 - the idea under SLH-DSA, LMS and XMSS.
import hashlib, secrets
H = lambda b: hashlib.sha256(b).digest()
def keygen(bits=256):
    sk = [(secrets.token_bytes(32), secrets.token_bytes(32)) for _ in range(bits)]
    pk = [(H(a), H(b)) for a, b in sk]
    return sk, pk
def bits_of(msg):
    d = int.from_bytes(H(msg), "big"); return [(d >> (255 - i)) & 1 for i in range(256)]
def sign(sk, msg): return [sk[i][b] for i, b in enumerate(bits_of(msg))]
def verify(pk, msg, sig): return all(H(s) == pk[i][b] for i, (s, b) in enumerate(zip(sig, bits_of(msg))))
sk, pk = keygen()
s1 = sign(sk, b"firmware v1.0")
print("valid signature verifies:", verify(pk, b"firmware v1.0", s1))
print("tampered message rejected:", not verify(pk, b"firmware v1.1", s1))
s2 = sign(sk, b"firmware v1.1")          # KEY REUSE: never do this
revealed = sum(1 for i in range(256) if bits_of(b"firmware v1.0")[i] != bits_of(b"firmware v1.1")[i])
print(f"after one reuse, both secrets revealed at {revealed}/256 positions -> forging needs ~2^{256 - revealed} hashes, not 2^256")
print("signature size:", 256 * 32, "bytes; public key:", 2 * 256 * 32, "bytes")

Expected output:

valid signature verifies: True
tampered message rejected: True
after one reuse, both secrets revealed at 118/256 positions -> forging needs ~2^138 hashes, not 2^256
signature size: 8192 bytes; public key: 16384 bytes

Security rests only on the hash function, which is why hash-based signatures are considered conservative. Reuse is fatal: two signatures reveal both secrets at many positions. SLH-DSA builds trees of one-time and few-time signatures so that a single key can sign many messages without state; LMS and XMSS do so with state that the signer must never repeat.

17.4 Worked example

HCU's architect asks which primitive fits each need: archive encryption (AES-256, keep), key transport to the archive (KEM: ML-KEM-768 in a hybrid), statement signing (ML-DSA-65 once supported, or hybrid with ECDSA during transition), firmware signing for ATMs (LMS via SP 800-208 or SLH-DSA, because signing volume is low and conservatism is valued).

Each choice follows from the need rather than from the newest algorithm. Symmetric encryption stays because Grover's search leaves AES-256 strong. Key transport needs a KEM. Signatures need to be verifiable for as long as the signed statement matters. Firmware signing favours hash-based schemes because their security rests on hash functions alone, and the low signing volume makes managing state practical.

17.5 Common errors and limits

Calling ML-KEM "encryption"; it is a KEM producing a shared secret.
Reusing one-time or stateful signature keys.
Treating the toy Lamport lab as usable code.

A KEM gives both sides a shared secret; the data itself is then encrypted with a symmetric algorithm. Stateful signature keys must never sign twice with the same one-time key, which means the signer must track state reliably, including across backups and failures. The lab's Lamport scheme exists to show the idea of hash-based signatures; it is insecure in practice and must never be used outside the classroom.

Exercises

EX033 — Pick the primitive. For password storage, message integrity between two HCU servers, session key agreement and document approval, name the primitive and a standard algorithm. Rubric: 3 = four correct choices.
EX034 — Reuse. Using Lab L's output, explain why the second Lamport signature enables forgery. Rubric: 3 = both secrets at many positions, mixing to sign new messages.

Synthesis

Quantum computers break public-key key exchange and signatures based on factoring and discrete logarithms. NIST's FIPS 203, 204 and 205 and SP 800-208 supply replacements; symmetric and hash primitives remain, with adequate sizes.

Continue studying — chapter 17 of 40

← Chapter 16 (draft) · Course chapter index · Chapter 18 (draft) →