Chapter 4: From classical to post-quantum

RSA’s security rests on generating moduli whose factorization is infeasible to recover. Given the factorization, the private exponent is one extended-Euclidean call away. ECDSA rests on the hardness of the elliptic-curve discrete logarithm. A fault-tolerant quantum computer running Shor’s algorithm factors RSA moduli and solves discrete logarithm in polynomial time (Nielsen & Chuang, 2010; Shor, 1994), so both schemes fall together. Chapter 4 builds them from scratch in Python and then walks the classical post-processing step that finishes a successful RSA factoring attempt, once period finding has returned a useful even order. Everything in the chapter is toy code: RSA moduli built from two 32-bit primes, an explicit reader-supplied ECDSA nonce, no padding, no hashing for RSA signatures, and no constant-time or side-channel hardening on the secp256k1 implementation. The full package with its pytest suite lives at solutions/ch04-classical-to-pq/.

A toy RSA we can factor by hand

The smallest useful RSA example in this chapter uses 32-bit primes and a 64-bit modulus. The full package generates the primes from whatever PRNG the caller hands it, so a fixed seed reproduces these two. Here we hard-code them so the keying material is on the page:

# In the full package this is classical.rsa.keygen. Called as
# keygen(bits=64, rng=random.Random(42)) it uses Miller-Rabin to
# generate these two distinct 32-bit primes. It returns the pair
# (public_key, private_key), with p and q stored on the private key.
p = 3184935163
q = 3199286161
n = p * q
print(n)
# ==> 10189518990668179243

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch04/, one file per block. Appendix C covers the clone and the environment they run on.

The modulus n is 64 bits wide. Chapter 1 quoted the 2021 surface-code estimate of Gidney and Ekerå for factoring a 2048-bit RSA modulus: roughly 8 hours of runtime on about 20 million noisy qubits (Gidney & Ekerå, 2021). Later work has lowered the qubit count at the cost of longer runtime: Gidney’s 2025 follow-up reaches under one million noisy qubits with runtime under a week (Gidney, 2025). Read the 2021 figure as a reference point rather than a fixed threshold.

A 64-bit modulus is nowhere near that bar. A laptop factors it instantly with a standard integer-factorization routine such as Pollard rho. Naive trial division is easy to understand, but for a 64-bit semiprime whose factors sit near $\sqrt{n}$ it would still scan on the order of billions of candidate divisors in the worst case and is the wrong tool. The point of using 64 bits here is not security; it is that every intermediate value fits on the page.

Pick the public exponent e = 65537, compute Euler’s totient phi(n) = (p-1)(q-1), and invert e modulo phi(n) to get the private exponent d. The next section explains why these three steps reconstruct the inverse of the encryption map.

p = 3184935163
q = 3199286161
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(d)
# ==> 6603433942666100993

Encryption and decryption are the raw pow operations m -> m^e mod n and c -> c^d mod n, where the plaintext $m$ is an integer in $[0, n - 1]$. With the message m = 0xDEADBEEF (well under our 64-bit modulus), the round-trip returns the original message:

p = 3184935163
q = 3199286161
n = p * q
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
m = 0xDEADBEEF
c = pow(m, e, n)
back = pow(c, d, n)
print(c)
print(hex(back))
# ==> 2094384833718895087
# ==> 0xdeadbeef

That is the whole of textbook RSA as a calculation. The rest of this chapter is machinery around these three lines: how to pick the primes, how to prove the round-trip works, how to sign and verify, and what the quantum attack does to the modulus.

The algebra we need

This chapter draws on three results from Chapter 2: modular exponentiation via Python’s built-in pow, the extended Euclidean algorithm for the modular inverse, and Euler’s theorem for RSA’s correctness.

Euler’s theorem states that if gcd(a, n) = 1 then

$$a^{\varphi(n)} \equiv 1 \pmod{n},$$

where $\varphi(n)$ is Euler’s totient function, counting the integers in $[1, n]$ that are coprime to $n$. For $n = pq$ with $p$ and $q$ distinct primes, $\varphi(n) = (p-1)(q-1)$. Chapter 2 states Euler’s theorem and cites Shoup rather than proving it (Shoup, 2009). The proof is two lines: the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ has order $\varphi(n)$, and by Lagrange’s theorem the cyclic subgroup generated by $a$ has order dividing $\varphi(n)$, so $a^{\varphi(n)} = 1$.

RSA’s correctness follows in two more lines. Choose $e$ coprime to $\varphi(n)$ and set $d = e^{-1} \bmod \varphi(n)$, so $ed = 1 + k\varphi(n)$ for some integer $k \geq 0$. For any message $m$ coprime to $n$,

$$m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^{k} \equiv m \cdot 1^{k} = m \pmod{n}.$$

The edge case where $\gcd(m, n) > 1$ is handled by the Chinese remainder theorem. Since $\varphi(n) = (p - 1)(q - 1)$, the exponent $k\varphi(n)$ is a multiple of $p - 1$. That means $m^{ed} = m \cdot (m^{p-1})^{k(q-1)}$. If $p \nmid m$, Fermat’s little theorem gives $m^{p-1} \equiv 1 \pmod{p}$, so $m^{ed} \equiv m \pmod{p}$. If instead $p \mid m$, then both sides are $0 \pmod{p}$. The same argument applied to $q$ gives $m^{ed} \equiv m \pmod{q}$, and CRT stitches the two congruences back to a single congruence modulo $n$ (Shoup, 2009). Chapter 2 spells out CRT and Fermat’s little theorem.

Why standardized RSA inverts modulo lcm(p-1, q-1)

Both FIPS 186-5 and PKCS #1 v2.2 state the inverse condition modulo $\lambda(n) = \mathrm{lcm}(p - 1, q - 1)$ rather than $\varphi(n)$ (Moriarty et al., 2016; National Institute of Standards and Technology, 2023), and choosing the least positive representative modulo $\lambda(n)$ can give a smaller equivalent private exponent. The textbook construction in this chapter uses $\varphi(n)$ for symmetry with Euler’s theorem.

Elliptic-curve cryptography needs a different algebra. The curve $y^2 = x^3 + 7$ over the prime field $\mathbb{F}_p$ with $p = 2^{256} - 2^{32} - 977$ is called secp256k1 (Certicom Research, 2010). Its points, together with a point at infinity, form an abelian group under the chord-and-tangent construction. To add two distinct points $P_1$ and $P_2$, draw the line through them, find the third intersection with the curve, and reflect it over the $x$-axis. To double $P$, use the tangent at $P$ in place of the chord. The group has a prime order $N$ close to $2^{256}$ and a canonical generator $G$, both fixed in the standard. Elliptic-curve cryptography was proposed independently by Miller in 1985 and Koblitz in 1987 (Koblitz, 1987; Miller, 1986). The curve secp256k1 is the one used by Bitcoin and cited in Chapter 1 as the target of the 2026 Google quantum resource estimate (Babbush et al., 2026).

The public and private keys of ECDSA are a scalar and a point: the private key is a random integer $d \in [1, N-1]$ and the public key is the point $Q = dG$. The next section builds the signing and verification maps on top of this.

Building textbook RSA

Keygen is the expensive step. Picking two random 32-bit primes needs a primality test. Trial division decides primality of a single 32-bit candidate in roughly $2^{16}$ operations, which is fine for one test but wasteful when sampling tens of candidates per call. The full package uses deterministic Miller-Rabin with the witness set $\{2, 3, 5, 7, 11, 13\}$. For every composite odd $n$ strictly below $3{,}474{,}749{,}660{,}383$, at least one of those six bases is a Miller-Rabin witness, so with the usual small-prime handling they give a deterministic test across the whole 32-bit range. The bound is Jaeschke’s (Jaeschke, 1993) and is also recorded as OEIS A014233. The boundary value is itself a strong pseudoprime to all six bases. The snippet below shows the core of the Miller-Rabin test on a single candidate. The full primality routine handles small primes and the write-n-1 factorization.

def miller_rabin_once(n, a):
    if n < 2:
        return False          # without this, n = 1 loops forever below
    if n % 2 == 0:
        return n == 2
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return True
    for _ in range(s - 1):
        x = pow(x, 2, n)
        if x == n - 1:
            return True
    return False

# 3184935163 is prime; 3184935164 is not; 1 is neither.
print(miller_rabin_once(3184935163, 2))
print(miller_rabin_once(3184935164, 2))
print(miller_rabin_once(1, 2))
# ==> True
# ==> False
# ==> False

Given two primes $p \neq q$, keygen computes $\varphi(n) = (p-1)(q-1)$ and $d = e^{-1} \bmod \varphi(n)$ as in the opening example, and returns the public and private exponents together with the modulus:

p = 3184935163
q = 3199286161
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
# If 65537 divides phi, retry with new primes. For these two it does not.
assert phi % e != 0
d = pow(e, -1, phi)
public_key = (n, e)
private_key = (n, d)
print(public_key[0].bit_length(), "bit modulus")
print("public exponent", public_key[1])
# ==> 64 bit modulus
# ==> public exponent 65537

Encryption and decryption are the raw modular exponentiations shown earlier: c = pow(m, e, n) and m = pow(c, d, n). Signing reuses the private exponent on the message itself, without hashing:

p = 3184935163
q = 3199286161
n = p * q
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
m = 0xCAFEBABE
s = pow(m, d, n)            # textbook RSA signing
ok = pow(s, e, n) == m       # textbook RSA verification
print(s)
print(ok)
# ==> 8817286230336697963
# ==> True

Both shortcuts in the block above are wrong in production. Textbook encryption is deterministic, so a repeat message produces a repeat ciphertext. The production fix is to encode the message with optimal asymmetric encryption padding (OAEP), introduced by Bellare and Rogaway in 1994 (Bellare & Rogaway, 1994) and standardized as RSAES-OAEP in PKCS #1 v2.2 (Moriarty et al., 2016). Textbook signing is multiplicatively malleable: from valid signatures on $m_1$ and $m_2$, an attacker forms $s_1 s_2 \bmod n$, which is a valid signature on $m_1 m_2 \bmod n$. Hashing the message first does not by itself fix this. Production RSA signatures use a structured encoding such as RSASSA-PSS (Moriarty et al., 2016). The Fujisaki-Okamoto transform appears later in the book in the KEM setting: ML-KEM builds a public-key encryption component from Module-LWE and uses an FO-style transform to turn it into an IND-CCA2-secure key-encapsulation mechanism (National Institute of Standards and Technology, 2024). Chapter 5 walks the KEM construction; Chapter 6 walks hashed-message signing.

The RSA module of the ch04-classical-to-pq package under solutions/ wraps these five functions: keygen, encrypt, decrypt, sign, and verify. Its pytest suite at tests/ch04/test_rsa.py checks the round-trip on random keys generated with bits=64, checks that bit-flipping a signature breaks verification, and checks that e = 65537.

Building ECDSA on secp256k1

The first piece is the affine group law. Take two points $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$ on $y^2 = x^3 + 7$, and assume $P_1 \neq -P_2$. Their sum $(x_3, y_3)$ follows from a slope $\lambda$. For $P_1 \neq P_2$, $\lambda$ is the chord slope; for $P_1 = P_2$, it is the tangent slope:

$$\lambda = \begin{cases} (y_2 - y_1)(x_2 - x_1)^{-1} \bmod p, & P_1 \neq P_2, \\ (3 x_1^2)(2 y_1)^{-1} \bmod p, & P_1 = P_2. \end{cases}$$

Then $x_3$ and $y_3$ come from the standard Vieta-style formulas:

$$x_3 = \lambda^2 - x_1 - x_2 \bmod p, \qquad y_3 = \lambda(x_1 - x_3) - y_1 \bmod p.$$

Both cases come out of the same argument. Parameterize the chord or tangent as $y = \lambda x + \beta$ and substitute into $y^2 = x^3 + 7$ to get a monic cubic in $x$ whose roots are $x_1$, $x_2$, and $x_3$. Vieta’s formulas give $x_1 + x_2 + x_3 = \lambda^2$, so $x_3 = \lambda^2 - x_1 - x_2$. The point $-P_3$ lies on the line, so $y_3 = -(\lambda x_3 + \beta) = \lambda(x_1 - x_3) - y_1$, where the second equality uses the fact that $(x_1, y_1)$ lies on the same line. The full formula (including the point-at-infinity and vertical-line cases) is point_add in the ch04-classical-to-pq package under solutions/. The pedagogical slice below defines point_add for two distinct non-vertical points and demonstrates it on a hand-picked example over a toy field:

# Toy curve y^2 = x^3 + 7 over F_97.
P = 97

def point_add(x1, y1, x2, y2):
    lam = (y2 - y1) * pow(x2 - x1, -1, P) % P
    x3 = (lam * lam - x1 - x2) % P
    y3 = (lam * (x1 - x3) - y1) % P
    return (x3, y3)

# Two points on y^2 = x^3 + 7 mod 97: (1, 28) and (5, 36).
# Check they are on the curve.
for (x, y) in [(1, 28), (5, 36)]:
    assert (y * y - x * x * x - 7) % P == 0

x3, y3 = point_add(1, 28, 5, 36)
print(x3, y3)
print((y3 * y3 - x3 * x3 * x3 - 7) % P)
# ==> 95 75
# ==> 0

Scalar multiplication $kP$ uses double-and-add, the additive analogue of square-and-multiply. For secp256k1 and for toy curves the same algorithm applies. The full package implements it as scalar_mul in classical.curve. With the group law in hand, ECDSA becomes three equations. For a private key $d$, a message hash converted to an integer $z$, and a nonce $k \in [1, N-1]$, the signature is

$$R = kG, \qquad r = R_x \bmod N, \qquad s = k^{-1}(z + r d) \bmod N.$$

Verification uses the public key $Q = dG$ and the inverse of $s$ modulo $N$:

$$\begin{aligned} w &= s^{-1} \bmod N, \qquad u_1 = zw \bmod N, \qquad u_2 = rw \bmod N, \\ X &= u_1 G + u_2 Q, \qquad \text{accept iff } X_x \bmod N = r. \end{aligned}$$

The verification identity is mechanical. Substituting $Q = dG$ and $s = k^{-1}(z + rd)$ gives $u_1 G + u_2 Q = s^{-1}(z + rd) G = kG = R$. Therefore $X_x \bmod N = R_x \bmod N = r$, and verification accepts.

FIPS 186-5 (National Institute of Standards and Technology, 2023) specifies every step of the real procedure. The ECDSA algorithmic rules (key generation, signing, verification, hash-to-integer conversion, zero-edge-case handling) come from FIPS 186-5. The secp256k1 domain parameters come from SEC 2 (Certicom Research, 2010), and NIST SP 800-186 lists secp256k1 as allowed for blockchain-related applications (Chen et al., 2023) separately from the classic NIST P-curves. The hash-to-integer conversion under FIPS 186-5 is more careful than “hash $\bmod N$”: the digest is read as an integer and truncated to the leftmost $\lceil \log_2 N \rceil$ bits when needed. For secp256k1 the SHA-256 digest length already matches the group-order bit length, so the truncation is a no-op, but the rule still applies for other curves. The standard also rejects edge cases where $r$ or $s$ is zero, requires verifiers to reject signatures with $r$ or $s$ outside $[1, N-1]$, and rejects malformed public keys.

In the toy code we read the SHA-256 output as a big-endian integer and reduce modulo $N$ for compactness, which is a simplification: FIPS 186-5 uses the truncated digest directly and does not reduce it. The displayed sketch below also omits the reject-if-zero branches, though the full package implements them. The sign in the ECDSA module of the ch04-classical-to-pq package under solutions/ also takes the nonce k as an explicit argument so signatures are reproducible across test runs:

# Sketch of the signing step; the full version lives in the package.
# scalar_mul, G, N come from classical.curve.
def ecdsa_sign(d, z, k):
    R = scalar_mul(k, G)
    r = R.x % N
    s = (pow(k, -1, N) * (z + r * d)) % N
    return (r, s)

Real ECDSA requires a fresh per-message secret number $k \in [1, N-1]$, generated either uniformly or derived deterministically from the message and the private key per FIPS 186-5 (National Institute of Standards and Technology, 2023). Reusing one $k$ across two signatures whose message representatives differ, $z_1 \not\equiv z_2 \pmod N$, is catastrophic: subtracting the two signing equations recovers $k$, and then either equation recovers $d$. Chapter 6 walks that derivation. Re-signing the same input deterministically is not that case and is safe by construction, because it reproduces the same $k$, the same $z$, and so the same signature.

The toy in this chapter takes $k$ as an explicit argument so tests are reproducible. This is not production deterministic ECDSA: real deterministic ECDSA derives $k$ from the private key and message digest as in RFC 6979 (Pornin, 2013) or the FIPS 186-5 deterministic method (National Institute of Standards and Technology, 2023), not from a caller-supplied integer. The fixed-$k$ shortcut also lets the reader see directly what the nonce-reuse compromise of Exercise 4 looks like.

The pytest suite at tests/ch04/test_ecdsa.py checks the full round-trip, checks that the generator is on the curve, checks that $NG$ is the point at infinity, and checks that verification rejects both tampered messages and signatures from the wrong key.

What Shor does to this

Shor’s algorithm solves two problems in polynomial time on a fault-tolerant quantum computer: the order-finding problem for an integer modulo $n$, and the discrete-logarithm problem in any cyclic group whose elements can be multiplied and inverted by polynomial-size reversible circuits and whose generator’s order is known or found by the same order-finding routine (Shor, 1994, sec. 6). Integer factorization reduces to order finding in $(\mathbb{Z}/n\mathbb{Z})^{\times}$. Elliptic-curve discrete logarithm on secp256k1 reduces to discrete logarithm in a cyclic group of 256-bit order. Both attacks have the same strategic shape: a quantum subroutine extracts hidden periodic or linear structure from the target group, and a short classical computation turns that information into the secret. The RSA case ends in gcd arithmetic; the ECDLP case ends in modular linear recovery from the Fourier-sampling output. This section walks the RSA case in full and sketches the ECDLP case at the end.

Figure 4.1. Shor's algorithm is a quantum subroutine followed by a classical one, in both the factoring and the discrete-logarithm cases. The left-hand boxes are the quantum halves: small instances can be simulated classically, but generic simulation costs memory exponential in the qubit count and cryptographic scale needs fault-tolerant hardware, which is why no chapter of this book runs them. The right-hand boxes are ordinary arithmetic: for RSA it is the pair of gcd calls built below, and for the elliptic-curve case it is the modular linear solve this chapter only sketches.

Nielsen and Chuang chapter 5 shows that the order-finding subroutine runs in $O((\log n)^3)$ time on a quantum computer using the quantum Fourier transform (Nielsen & Chuang, 2010). NC §5.3 walks the continued-fraction post-step that turns a QFT measurement into a candidate denominator related to the order of $a$ modulo $n$. A single sample lands near a multiple of $1/r$ with constant probability, but it recovers the full order only when the sampled numerator is coprime to $r$. Otherwise the continued fraction returns a proper divisor of $r$, and the caller draws again, combines denominators, or tests small multiples. From here on $r$ denotes the order after that classical verification. The classical post-processing is then elementary. Pick a random base $a$ coprime to $n$ and let $r$ be the multiplicative order of $a$ modulo $n$, so $a^r \equiv 1 \pmod{n}$ and no smaller positive exponent does. If $r$ is odd, retry with a new $a$ and a fresh period-finding call. If $r$ is even, set $x = a^{r/2} \bmod n$ and note that

$$x^2 \equiv 1 \pmod{n},$$

so $x$ is a square root of $1$ modulo $n$. The trivial square roots are $\pm 1$. The case $x = 1$ cannot occur for the true order: it would force $a^{r/2} \equiv 1$ and contradict the minimality of $r$. The case $x \equiv -1 \pmod{n}$ does occur and is unproductive: $n$ divides $x + 1$, so $\gcd(x - 1, n) = 1$ and $\gcd(x + 1, n) = n$, both trivial, and we retry with a new $a$. Otherwise $x$ is a non-trivial square root of $1$, and then

$$(x - 1)(x + 1) \equiv 0 \pmod{n},$$

so $n$ divides the product $(x-1)(x+1)$ but divides neither factor alone. That means $\gcd(x - 1, n)$ and $\gcd(x + 1, n)$ are both proper divisors of $n$, and the non-trivial one is a factor.

The concrete case worth running by hand is $n = 323 = 17 \cdot 19$, $a = 2$. The order of $2$ modulo $323$ is $72$. Then $r/2 = 36$, $x = 2^{36} \bmod 323 = 305$, and the two gcd computations give

$$\gcd(304, 323) = 19, \qquad \gcd(306, 323) = 17,$$

so both candidates recover a prime factor. In Python:

from math import gcd

n = 323
a = 2
r = 72
x = pow(a, r // 2, n)
factor = gcd(x - 1, n)
factor2 = gcd(x + 1, n)
print(x, factor, factor2)
# ==> 305 19 17

The full classical.shor_postprocess.recover_factor in the package raises ValueError if $r$ is odd, if $x = n - 1$, or if neither gcd candidate lies in $(1, n)$. That last branch is the defensive catch-all: it covers the $x = 1$ case, which arises when the caller passes in a multiple of the true order rather than the order itself. In the classical Shor loop, the reader’s job on failure is to sample a new base $a$ and call the quantum period-finding subroutine again. The pytest case test_worked_example_n323 in tests/ch04/test_shor_postprocess.py runs the same worked example, asserting on the first non-trivial GCD candidate that recover_factor returns.

What is missing from the chapter and from the package is the quantum period-finding step itself. Shor’s complexity bound depends on the quantum Fourier transform. Small instances can be simulated on a laptop, but generic state-vector simulation costs memory exponential in the qubit count, so that route does not reach cryptographic scale. Reaching it needs fault-tolerant quantum hardware, which does not exist as of this writing. A pedagogical run would still want a quantum-circuit simulator such as Qiskit or Cirq, and pulling one in would break the environment contract in Appendix C. The pedagogical slice in this chapter is the classical post-processing, which is where factoring actually finishes. Every line of it runs on a laptop.

The ECDLP version of the attack ends differently. Given the public key $Q = dG$ on secp256k1 and the generator $G$, the quantum step is a hidden-subgroup procedure on $(\mathbb{Z}/N\mathbb{Z})^2$: a quantum Fourier transform and a measurement yield modular linear information about $d$. The classical step solves the resulting congruences. The full derivation is in Nielsen and Chuang §5.4 (Nielsen & Chuang, 2010). Chapter 1 cited the 2026 Google resource estimate for breaking a single secp256k1 public key: fewer than 500,000 physical qubits and minutes-scale runtime (Babbush et al., 2026). Those figures assume a superconducting architecture and a specific surface-code overhead. They are not a claim that any current quantum computer can perform the attack. Once $d$ is recovered, the attacker signs arbitrary messages under the victim’s key with the same toy ECDSA code above.

Tradeoffs against the post-quantum families

RSA and ECDSA buy small keys, fast signing, and thirty years of cryptanalysis. A 2048-bit RSA modulus is 256 bytes before encoding overhead. The conventional public exponent 65537 = $0\mathtt{x}010001$ needs three bytes as a minimal unsigned integer, and real DER/SPKI encodings add additional structural overhead on top. A secp256k1 compressed public key is 33 bytes. Signing and verification are both a handful of big-integer operations. Both schemes lose everything under Shor. Blockchain protocols anchor to that byte budget: BIP 340 uses a 64-byte Schnorr signature and a 32-byte x-only public key (Wuille et al., 2020). The standardized post-quantum signatures are tens to hundreds of times larger than that 96-byte pair, depending on parameter set: ML-DSA-44 totals 3,732 bytes of public key plus signature (National Institute of Standards and Technology, 2024b) and SLH-DSA-SHAKE-256f totals 49,920 (National Institute of Standards and Technology, 2024c). Not every candidate sits there. SQIsign’s level-1 parameters total 283 bytes, at a signing cost Chapter 23 quantifies (The SQIsign Team, 2026). Part VII (Chapter 37) treats the L1 signature migration as a throughput-and-storage problem first.

The post-quantum replacements in the rest of the book trade size for quantum resistance. Measured against the 256-byte RSA modulus and the 33-byte secp256k1 public key above:

Family	Artifact size	Where the book builds it
Lattice KEM (ML-KEM-512)	800-byte encapsulation key, 768-byte ciphertext (National Institute of Standards and Technology, 2024a)	Chapter 11, on the lattice primitives of Chapters 7 through 10
Lattice signature (ML-DSA-44)	2,420-byte signature (National Institute of Standards and Technology, 2024b)	Chapter 12
Hash-based signature (SLH-DSA)	7,856 bytes at SHA2-128s to 49,856 bytes at SHAKE-256f (National Institute of Standards and Technology, 2024c)	Chapter 17, on the one-time signature primitives of Chapters 14 through 16
Code-based KEM (Classic McEliece, HQC)	Much larger public keys than the lattice KEM	Chapter 20 and Chapter 21, as teaching builds of original McEliece PKE and the HQC IND-CPA core, each with its gap from the submission documented
Isogeny signature (SQIsign)	Much smaller than lattice signatures, with substantially slower signing	Chapter 23, which quantifies the hardware-specific benchmark ratio against the round-3 reference package (The SQIsign Team, 2026)

Standardization status

ML-KEM, ML-DSA, and SLH-DSA are final FIPS standards. NIST selected HQC in March 2025 as a non-lattice backup to ML-KEM and did not select Classic McEliece. The HQC standard is not yet published (National Institute of Standards and Technology, 2025a, 2025b). SQIsign advanced to the third round of NIST’s Additional Digital Signatures process in May 2026 and is not a FIPS standard (National Institute of Standards and Technology, 2026).

None of the post-quantum families is a drop-in replacement for RSA or ECDSA in every dimension. Every deployment chooses where to pay: bandwidth for larger signatures, CPU time for slower signing or verification, storage for larger keys, or confidence in a newer security assumption. Chapter 24 compares the signature families at the low end of the size range against real deployment constraints such as layer-1 byte budgets.

Where Chapter 4 ends and Chapter 5 picks up

This chapter built two deployed schemes from scratch and then walked the classical half of the attack that breaks them. It also flagged the textbook shortcuts twice over: textbook RSA encryption is deterministic, so a repeated message repeats its ciphertext, and textbook RSA signing is multiplicatively malleable. Both were named as defects and left there. The chapter names IND-CCA2 in passing but never says what it means, which is the gap the next two chapters close.

Chapter 5 closes it for encryption. It separates public-key encryption from key encapsulation and from key agreement, states what chosen-ciphertext security demands of each, and shows why textbook RSA and a naively built RSA-KEM both fail that bar. That is the vocabulary the post-quantum KEMs are specified in: ML-KEM is a key-encapsulation mechanism carrying an IND-CCA2 claim, not a drop-in for the pow(m, e, n) on this page. Chapter 6 does the same for signatures, and picks up the nonce-reuse recovery this chapter leaves as Exercise 4.

Exercises

1. Count the keygen work. The RSA keygen in classical.rsa retries whenever the two primes collide or when 65537 divides $\varphi(n)$. Instrument classical.rsa._random_prime to count the number of Miller-Rabin calls made in a fresh keygen(bits=64) invocation with a few different PRNG seeds. How many candidates does it sample on average before hitting a 32-bit prime? Compare against the prime-counting theorem: if the sampler tests arbitrary 32-bit integers, expect about $\ln(2^{32}) = 32 \ln 2 \approx 22.18$ candidates per prime; if it forces candidates to be odd (the usual implementation), expect about half that, roughly $11.09$ candidates per prime, before any small-prime filter. Which regime does the implementation in classical.rsa._random_prime fall into?

2. Run the post-processing on a new period. The multiplicative order of $a = 10$ modulo $n = 3233 = 53 \cdot 61$ is $r = 780$. Run classical.shor_postprocess.recover_factor(3233, 10, 780) and confirm it returns either $53$ or $61$. Then change the base to $a = 2$ with the same $n$ and compute $2^{390} \bmod 3233$ by hand. You should find it equals $n - 1$, so recover_factor(3233, 2, 780) raises ValueError. Why does this particular retry branch fire, and what does the classical Shor loop do next?

3. Verify an ECDSA signature from the package. In a Python REPL, generate a fresh secp256k1 keypair with classical.ecdsa_secp256k1.keygen(), sign the byte string b"chapter 4" with a nonce of your choosing, and call verify on the resulting signature. Confirm that flipping the first byte of the message breaks verification.

4. Recover the private key from a reused nonce. Suppose an ECDSA signer produces two signatures $(r, s_1)$ and $(r, s_2)$ on two different message hashes $z_1$ and $z_2$ with the same nonce $k$. Show that $k$ can be solved from $s_1 - s_2 \equiv k^{-1}(z_1 - z_2) \pmod N$, and then show how to recover the private key $d$ from $s_1 \equiv k^{-1}(z_1 + r d) \pmod N$. The derivation requires $s_1 \not\equiv s_2 \pmod N$ and $r \not\equiv 0 \pmod N$ so the inverses $(s_1 - s_2)^{-1}$ and $r^{-1}$ exist. Real ECDSA rejects signatures with $r = 0$ or $s = 0$ outright. Under the same nonce, $z_1 \not\equiv z_2 \pmod N$ forces $s_1 \not\equiv s_2 \pmod N$, because multiplication by $k^{-1}$ is injective modulo the prime order $N$. The chapter’s displayed sketch omits both reject-if-zero checks; the full package implements them. Chapter 6 walks the full derivation.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 4. A separate track, for rebuilding rather than reading: the package exercises/ch04-classical-to-pq has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch04 to grade your version against the suite that proves the reference one.

References

Babbush, R., Zalcman, A., Gidney, C., Broughton, M., Khattar, T., Neven, H., Bergamaschi, T., Drake, J., & Boneh, D. (2026). Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations. PRX Quantum, 7(3), 031001. https://doi.org/10.1103/j3xf-bw18

Bellare, M., & Rogaway, P. (1994). Optimal asymmetric encryption. Advances in Cryptology – EUROCRYPT 1994, 950, 92–111. https://doi.org/10.1007/BFb0053428

Certicom Research. (2010). SEC 2: Recommended Elliptic Curve Domain Parameters (Version 2.0). Standards for Efficient Cryptography Group. https://www.secg.org/sec2-v2.pdf

Chen, L., Moody, D., Regenscheid, A., Robinson, A., & Randall, K. (2023). Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters. NIST SP 800-186. https://doi.org/10.6028/NIST.SP.800-186

Gidney, C. (2025). How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv:2505.15917. https://arxiv.org/abs/2505.15917

Gidney, C., & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433. https://doi.org/10.22331/q-2021-04-15-433

Jaeschke, G. (1993). On Strong Pseudoprimes to Several Bases. Mathematics of Computation, 61(204), 915–926. https://doi.org/10.1090/S0025-5718-1993-1192971-8

Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of Computation, 48(177), 203–209. https://doi.org/10.1090/S0025-5718-1987-0866109-5

Miller, V. S. (1986). Use of elliptic curves in cryptography. Advances in Cryptology – CRYPTO 1985, 218, 417–426. https://doi.org/10.1007/3-540-39799-X_31

Moriarty, K., Kaliski, B., Jonsson, J., & Rusch, A. (2016). PKCS #1: RSA Cryptography Specifications Version 2.2. RFC 8017. https://doi.org/10.17487/RFC8017

National Institute of Standards and Technology. (2023). Digital Signature Standard (DSS). FIPS Publication 186-5. https://doi.org/10.6028/NIST.FIPS.186-5

National Institute of Standards and Technology. (2024a). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203

National Institute of Standards and Technology. (2024b). FIPS 204: Module-Lattice-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.204

National Institute of Standards and Technology. (2024c). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205

National Institute of Standards and Technology. (2025a). Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process (Internal Report NIST IR 8545). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8545

National Institute of Standards and Technology. (2025b). NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption. NIST news release. https://www.nist.gov/news-events/news/2025/03/nist-selects-hqc-fifth-algorithm-post-quantum-encryption

National Institute of Standards and Technology. (2026). Status Report on the Second Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process (Internal Report NIST IR 8610). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8610

Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. https://www.cambridge.org/highereducation/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE

Pornin, T. (2013). Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). RFC 6979. https://doi.org/10.17487/RFC6979

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), 124–134. https://doi.org/10.1109/SFCS.1994.365700

Shoup, V. (2009). A Computational Introduction to Number Theory and Algebra (2nd ed.). Cambridge University Press. https://doi.org/10.1017/cbo9780511814549

The SQIsign Team. (2026). SQIsign: Algorithm Specifications and Supporting Documentation (Version 3.0). NIST Post-Quantum Cryptography Additional Signatures, Round 3 submission. https://sqisign.org/spec/sqisign-20260901.pdf

Wuille, P., Nick, J., & Ruffing, T. (2020). BIP-340: Schnorr Signatures for secp256k1. Bitcoin Improvement Proposal. https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki