Appendix D: Solutions for Chapter 4

This page collects solutions and editorial notes for the exercises in Chapter 4: From classical to post-quantum. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the classical package under solutions/ch04-classical-to-pq. From a clone of the companion repository, pytest tests/ch04 runs its suite. Appendix C has the setup.

Exercise 1

The prime-counting theorem says the density of primes near $2^{32}$ is $1 / \ln(2^{32}) \approx 1/22.18 \approx 0.045$. A uniformly random 32-bit candidate is therefore prime with probability about 4.5%, which would put the expected count at about 22 candidates per prime.

That is the wrong regime for this implementation. _random_prime takes a random draw of the requested width and forces both its top bit and its bottom bit high. The top bit fixes the width at exactly 32 bits. The trailing | 1 forces every candidate odd, so no test is ever spent on an even number. Every prime above 2 is odd, so the density among the candidates actually drawn is twice the density among all integers, and the expected count halves to $22.18 / 2 \approx 11.09$ per prime. A keygen(bits=64) invocation draws two primes, so it makes about 22 Miller-Rabin calls in total, plus a small additional retry rate for the $p \neq q$ and $\gcd(e, \varphi) = 1$ checks.

Instrumenting the call and averaging over 200 seeds puts the implementation in the odd-forced regime, within a few percent of $11.09$:

import random, sys
sys.path.insert(0, "solutions/ch04-classical-to-pq/src")
import classical.rsa as rsa

calls = 0
inner = rsa._miller_rabin

def counted(n, witnesses):
    global calls
    calls += 1
    return inner(n, witnesses)

rsa._miller_rabin = counted

totals = []
for seed in range(200):
    calls = 0
    rsa.keygen(bits=64, rng=random.Random(seed))
    totals.append(calls)

mean_per_keygen = sum(totals) / len(totals)
print("calls per keygen:", round(mean_per_keygen, 1))
print("calls per prime :", round(mean_per_keygen / 2, 1))
# ==> calls per keygen: 22.9
# ==> calls per prime : 11.5

Any single seed scatters widely, because the count per prime is geometrically distributed; the average over many seeds is what should agree with the theory.

Exercise 2

For $a = 10$, the post-processing computes $\gcd(10^{390} - 1, 3233)$. Numerically $10^{390} \bmod 3233 = 2439$, and $\gcd(2438, 3233) = 53$. recover_factor returns a single integer, the first non-trivial candidate, so it returns $53$. The cofactor $3233 / 53 = 61$ is the other prime.

For $a = 2$, the order $r = 780$ is even, but $2^{390} \equiv 3232 \equiv -1 \pmod{3233}$. The standard recovery requires $a^{r/2} \not\equiv \pm 1 \pmod n$. The $+1$ case contradicts $r$ being the order. The $-1$ case makes $\gcd(a^{r/2} - 1, n) = \gcd(-2, n) = 1$, because $n$ is odd, and $\gcd(a^{r/2} + 1, n) = \gcd(0, n) = n$, a trivial factor. Both branches give no useful factor. This is the documented retry condition. The classical Shor loop responds by drawing a fresh random base $a$ and starting over. Take $a$ a uniformly random unit modulo $n$, with $n$ odd and carrying at least two distinct prime factors. The combined probability of an odd order or $a^{r/2} \equiv -1 \pmod n$ is then at most $1/2$, so a constant number of retries succeeds in expectation. If $\gcd(a, n) > 1$ at the outset, that gcd is already a factor and the quantum step is not needed at all.

n = 3233
print(pow(10, 390, n))
print(pow(2, 390, n))
# ==> 2439
# ==> 3232

Exercise 3

The expected sequence: keygen() returns a (private_key, public_key) pair, private key first. sign(private_key, message, nonce) returns a signature pair $(r, s)$, with the message passed as bytes. verify(public_key, message, signature) returns True. Flipping the first byte changes the SHA-256 digest and therefore the message representative $z$, so the verification computation $X = s^{-1}(z G + r Q)$ lands on a different point and $X_x \bmod N \neq r$. Verification returns False. Stated generally the guarantee is computational rather than absolute: absent a hash collision or a successful forgery, changing the signed bytes invalidates the signature. The surface is intentionally minimal and matches the verification equation in the chapter.

Exercise 4: recovering the ECDSA private key from a reused nonce

Both signatures carry the same $r$, because both come from $R = kG$ with $r = R_x \bmod N$ under the same nonce $k$. Subtracting the two signing equations gives a linear relation in $k$:

$$s_1 \equiv k^{-1}(z_1 + r d) \pmod N, \qquad s_2 \equiv k^{-1}(z_2 + r d) \pmod N.$$

Subtracting eliminates $r d$:

$$s_1 - s_2 \equiv k^{-1}(z_1 - z_2) \pmod N.$$

Assume $z_1 \not\equiv z_2 \pmod N$. Distinct messages do not by themselves guarantee this, since two messages can share a digest or reduce to the same representative, but it holds for any pair an attacker can actually use. Because $k$ is invertible modulo the prime order $N$, the two signing equations then force $s_1 \not\equiv s_2 \pmod N$, so $s_1 - s_2$ is invertible modulo $N$. Solving for $k$:

$$k \equiv (z_1 - z_2)(s_1 - s_2)^{-1} \pmod N.$$

That recovers $k$ from public data ($z_1, z_2, s_1, s_2$) alone. With $k$ in hand, substitute into the first signing equation and solve for $d$. Multiplying both sides by $k$:

$$s_1 k \equiv z_1 + r d \pmod N \implies r d \equiv s_1 k - z_1 \pmod N.$$

Real ECDSA requires $1 \leq r \leq N - 1$, and secp256k1 has prime group order $N$, so $r$ is invertible modulo $N$. Primality alone would not be enough: $r \equiv 0$ has no inverse for any modulus. Inverting $r$:

$$d \equiv (s_1 k - z_1) r^{-1} \pmod N.$$

The private key falls out in two modular operations once the nonce is known.

The PlayStation 3 code signing key was recovered this way in 2010, after fail0verflow showed that Sony’s ECDSA signer used a fixed value in place of a per-signature random nonce (fail0verflow, 2010). Bitcoin has leaked keys the same way, and at measurable scale: Bos and colleagues found 158 public keys on the chain that had signed more than once under the same nonce, each of them recoverable (Bos et al., 2014). Reuse is observable on-chain precisely because $r$ is published with every signature. The defense is deterministic nonce generation, which derives $k$ from the private key and the message hash with HMAC-DRBG and so removes any dependence on a signing-time randomness source (Pornin, 2013). It does not guarantee a distinct nonce for every distinct message: equal message-hash representatives feed the derivation identical input and produce identical $k$. What it removes is the failure mode that caused both incidents above, a signer whose entropy source repeats or is absent.

N = 17  # toy stand-in for the secp256k1 group order
r = 5
s1, s2 = 7, 11
z1, z2 = 3, 9
# nonce reuse: solve k = (z1 - z2)(s1 - s2)^{-1} mod N
k = ((z1 - z2) * pow(s1 - s2, -1, N)) % N
# private key: d = (s1 k - z1) r^{-1} mod N
d = ((s1 * k - z1) * pow(r, -1, N)) % N
print(k, d)
# ==> 10 10

The toy values above are illustrative. Real ECDSA operates over the secp256k1 group order, and the same algebraic identity holds.

References

Bos, J. W., Halderman, J. A., Heninger, N., Moore, J., Naehrig, M., & Wustrow, E. (2014). Elliptic Curve Cryptography in Practice. Financial Cryptography and Data Security (FC 2014), 8437. https://doi.org/10.1007/978-3-662-45472-5_11

fail0verflow. (2010). Console Hacking 2010: PS3 Epic Fail. 27th Chaos Communication Congress (27C3), Berlin. https://media.ccc.de/v/27c3-4087-en-console_hacking_2010

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