Appendix D: Solutions for Chapter 6

This page collects solutions and editorial notes for the exercises in Chapter 6: Digital signatures reconsidered. 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 signature_attacks package under solutions/ch06-signature-attacks. From a clone of the companion repository, pytest tests/ch06 runs its suite. Appendix C has the setup.

Exercise 1

The textbook RSA signature on $m$ is $s = m^d \bmod n$, so $s_1 s_2 = m_1^d m_2^d = (m_1 m_2)^d \bmod n$, because raising to the $d$-th power is multiplicative on $(\mathbb{Z}/n\mathbb{Z})^\times$. Nothing here needs the group to be cyclic, and for a two-prime modulus it is not: $(\mathbb{Z}/n\mathbb{Z})^\times \cong C_{p-1} \times C_{q-1}$, which for the chapter’s modulus is not cyclic because $\gcd(p - 1, q - 1) = 6$. The combined signature is therefore a valid textbook-RSA signature on the message $m_1 m_2 \bmod n$ without ever asking the signer for it: the multiplicative homomorphism is the forgery.

The full-domain-hash variant FDH-RSA replaces $m$ with $H(m)$ in both signing and verification, so $\mathrm{Verify}(\mathrm{pk}, m, s)$ accepts iff $s^e \equiv H(m) \pmod n$. Multiplying the two signatures still works as arithmetic: $s_1 s_2 \equiv (H(m_1) H(m_2))^d \pmod n$, because RSA exponentiation is multiplicative whatever is fed into it. What the product is not is a forgery. It verifies only against a message $m^*$ whose hash satisfies $H(m^*) \equiv H(m_1) H(m_2) \pmod n$, and producing such an $m^*$ means inverting the random oracle at a value the attacker chose, which succeeds only with negligible probability. The obvious candidate $m_1 m_2$ fails for the separate reason that $H$ is not multiplicative.

# The 64-bit modulus from the chapter's opening snippet.
p, q = 3184935163, 3199286161
n = p * q
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))

m1, m2 = 0x1111222233334444, 0x5555666677778888
s1, s2 = pow(m1, d, n), pow(m2, d, n)
combined = (s1 * s2) % n
expected = pow((m1 * m2) % n, d, n)
print(combined == expected, combined)
# ==> True 2687895047109345874

Exercise 2

The recovery uses the same identities derived in Appendix D, Chapter 4: $k = (z_1 - z_2)(s_1 - s_2)^{-1}$ and $d = (s_1 k - z_1) r^{-1}$, all modulo the group order. The block below keeps the chapter’s group and changes what the exercise asks you to change: private key $d = 4$ instead of $7$, nonce $k = 8$ instead of $6$. As in the chapter, $r$ is derived from $k$ rather than chosen, since a nonce the signer picks is what fixes $r$.

Two conditions are worth checking rather than assuming, because a real signer enforces both. FIPS 186-5 rejects a signature with $r = 0$ or $s = 0$, so a pair that includes one is not a pair an attacker could ever observe. A randomized signer then draws a fresh nonce; a deterministic one outputs failure (National Institute of Standards and Technology, 2023). And the recovery needs $s_1 \neq s_2$, which for a fixed $k$ holds exactly when $z_1 \neq z_2$.

When $z_1 = z_2$, the differences $s_1 - s_2$ and $z_1 - z_2$ are both zero. The recovery formula $k = (z_1 - z_2)(s_1 - s_2)^{-1}$ becomes $0 \cdot 0^{-1}$, which is undefined. The two signatures collapse to the same equation, so two equations in two unknowns degenerate to one, and $k$ and $d$ cannot be solved independently.

p, n, g = 23, 11, 4      # the chapter's group: order-11 subgroup of (Z/23)^*
d, k = 4, 8              # a different private key and nonce, as the exercise asks
r = pow(g, k, p) % n     # r follows from k; the signer does not choose it
z1, z2 = 1, 2

# signing: s = k^{-1} (z + r d) mod n
s1 = (pow(k, -1, n) * (z1 + r * d)) % n
s2 = (pow(k, -1, n) * (z2 + r * d)) % n

# a conforming signer never emits a signature with r = 0 or s = 0
assert r != 0 and s1 != 0 and s2 != 0
assert s1 != s2

# recovery
k_rec = ((z1 - z2) * pow(s1 - s2, -1, n)) % n
d_rec = ((s1 * k_rec - z1) * pow(r, -1, n)) % n
print(r, s1, s2, k_rec, d_rec)
# ==> 9 6 2 8 4

Exercise 3

A reference statement to compare against your own version:

The challenger samples a keypair $(\mathrm{pk}, \mathrm{sk}) \leftarrow \mathrm{Gen}()$ and gives $\mathrm{pk}$ to the adversary. The adversary makes any number of queries to a signing oracle that returns $\mathrm{Sign}(\mathrm{sk}, m_i)$ for adversary-chosen messages $m_i$, with the queried set $Q = \{m_i\}$ recorded by the challenger. The adversary then outputs a forgery $(m^*, \sigma^*)$, and the challenger declares the adversary the winner if and only if $m^* \notin Q$ and $\mathrm{Verify}(\mathrm{pk}, m^*, \sigma^*) = 1$. The adversary’s advantage $\mathrm{Adv}^{\mathrm{EUF\text{-}CMA}}_{\Pi, \mathcal{A}}(\lambda) = \Pr[\mathcal{A} \text{ wins}]$ as a function of the security parameter $\lambda$, and the scheme is EUF-CMA secure if every probabilistic polynomial-time adversary’s advantage is negligible in $\lambda$.

A complete answer also names the original paper (Goldwasser et al., 1988) and says which of the chapter’s four notions it is stating: the key-only or EUF-KMA weakenings, plain EUF-CMA, or the stronger sEUF-CMA. The last of those counts a second valid signature on an already-queried message as a win. The two standards this book builds are specified against different notions: FIPS 204 designs ML-DSA for SUF-CMA, its name for sEUF-CMA, while FIPS 205 states SLH-DSA’s security categories with respect to EUF-CMA (National Institute of Standards and Technology, 2024a, 2024b).

Exercise 4

A stateful hash-based scheme tracks an index of which one-time keypairs have been consumed. If two machines hold a copy of the secret state and sign independently, both will eventually use the same one-time index. That produces two signatures under the same one-time key on different messages, which reveals additional secret material at every position where the two signed digests differ. What that buys an attacker is a much larger set of forgeable messages, not the whole one-time secret and not unrestricted signing: Chapter 14 works out which Lamport positions become supplyable after two signatures, and Chapter 15 does the same for WOTS+ chain positions. It is already a break, because the scheme’s security condition is one signature per key, and a forgeable set an attacker can search through is far inside the work the parameters promise. Coordination is the only safe way to share state: a shared sequence number, an atomic counter, or enforcement inside a hardware security module (HSM). Any backup that does not preserve the coordination invariant is a forgery vector.

The NIST stateful standard is XMSS / LMS (NIST SP 800-208). The way that standard contains the risk is to move the state inside the hardware. It requires key generation and signature generation to happen in cryptographic modules that never export secret keying material, validated to FIPS 140-2 or FIPS 140-3 Level 3 or higher physical security (Cooper et al., 2020). The NIST stateless standard is SLH-DSA (FIPS 205), which removes the state requirement at the cost of a larger signature (National Institute of Standards and Technology, 2024b).

Exercise 5

The EUF-CMA win condition is unchanged in the deployment setting: an adversary that produces $(m^*, \sigma^*)$ such that $\mathrm{Verify}(\mathrm{pk}, m^*, \sigma^*) = 1$ and $m^*$ was never queried to the signing oracle wins the game. In the recorded-key scenario the adversary makes zero oracle queries: it reads $\mathrm{pk}$ from the public ledger at year $Y_\text{first}$ and waits. At year $Y_\text{CRQC}$ Shor’s algorithm (Shor, 1994) recovers the secret scalar $d$ from $\mathrm{pk}$ in polynomial time, after which the adversary signs any $m^*$ of its choice and the forgery is unconditional. The win condition is satisfied trivially because the queried set $Q = \emptyset$ contains no message at all.

The key-exposure window length is

$$\Delta_\text{exposure} = Y_\text{CRQC} - Y_\text{first}.$$

At $Y_\text{first} = 2021$ and $Y_\text{CRQC} = 2031$ the window is ten years. Part VII picks this up: Chapter 36 sets a quantum threat model for public ledgers using Mosca’s inequality, and Chapter 37 works through signature migration for Bitcoin and Ethereum, whose Layer-1 (L1) keys are the ones exposed this way.

# Key-exposure window for a Schnorr-on-secp256k1 public key first published at Y_first,
# evaluated at a stated CRQC arrival year Y_CRQC.
Y_first = 2021    # BIP-341 puts the output key in the P2TR scriptPubKey
Y_CRQC = 2031     # CNSSP 15 CNSA 2.0 mandatory-use milestone (Chapter 1)
exposure_years = Y_CRQC - Y_first
print(exposure_years)
# ==> 10

References

Cooper, D., Apon, D., Dang, Q., Davidson, M., Dworkin, M., & Miller, C. (2020). Recommendation for Stateful Hash-Based Signature Schemes. NIST Special Publication 800-208. https://doi.org/10.6028/nist.sp.800-208

Goldwasser, S., Micali, S., & Rivest, R. L. (1988). A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2), 281–308. https://doi.org/10.1137/0217017

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 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. (2024b). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205

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