Appendix D: Solutions for Chapter 5

This page collects solutions and editorial notes for the exercises in Chapter 5: KEMs vs key agreement vs public-key encryption. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

Every block below is self-contained and runs on the standard library alone. The fuller versions of these routines, with the mauling attack and the multiplicative-order computation written out, are in the kem_primitives package under solutions/ch05-kem-primitives. From a clone of the companion repository, pytest tests/ch05 runs its suite. Appendix C has the setup.

Exercise 1

The exchange round-trips because $g^{ab} \equiv g^{ba} \pmod p$ regardless of how $a$ and $b$ are sampled. The auxiliary computation $5^{1031} \bmod 2063$ returns 2062, which is $-1 \bmod 2063$. The order of 5 in $\mathbb{F}_{2063}^*$ must divide $p - 1 = 2062 = 2 \cdot 1031$, so it is 1, 2, 1031, or 2062. The first three are ruled out: $5 \neq 1$, $5^2 = 25 \neq 1$, and $5^{1031} \equiv -1 \neq 1$. So the order is 2062 and $g = 5$ is a primitive root, generating the full multiplicative group rather than a strict subgroup. Real DH groups still prefer prime-order subgroups of carefully chosen safe primes for unrelated reasons (subgroup-confinement attacks).

Classical hardness of the discrete log on $\mathbb{F}_p^*$ is set against the general number field sieve, which runs in sub-exponential time. Modern parameter sets use $|p| \ge 2048$ bits. The Logjam analysis put the 1024-bit primes that protected legacy TLS at the edge of nation-state-feasible per-prime precomputation (Adrian et al., 2015), so 2048 bits is the conservative floor used today.

p, g = 2063, 5
print(pow(5, 1031, p))
# ==> 2062

Exercise 2

The mauling works because RSA encryption is multiplicative: $\mathrm{Enc}(r) \cdot \mathrm{Enc}(K) = \mathrm{Enc}(rK) \bmod n$, so the receiver decrypts to $rK$ instead of $K$. With $r = 2$ the attacker recovers $K$ exactly. Since $r$ was chosen invertible, multiplying the oracle’s answer by $r^{-1} \bmod n$ returns $K$ itself, which is the recovery step the exercise asks for and the one test_mauling_recovers_the_encapsulated_key pins. One decapsulation query on a ciphertext other than the challenge therefore hands over the challenge key, which is exactly the IND-CCA capability the FO transform must defend against.

The $\mathrm{FO}^{\not\perp}$ transform recomputes the ciphertext during decap by re-encrypting the recovered plaintext under encryption coins derived from a random oracle of that plaintext, then compares the re-encryption byte-for-byte to the received ciphertext. Over a randomized public-key encryption scheme each message has exactly one ciphertext under its derived coins. So a $c'$ obtained by applying an algebraic relation to the challenge is essentially never the re-encryption of whatever it decrypts to, and the check fails. Decap then returns the implicit-rejection fallback $\bar{K} = H(z, c')$, which depends on the private seed $z$ and on the ciphertext the attacker submitted, not on the challenge key.

Why “any invertible $r \neq 1$” is not good enough. The CCA oracle refuses the challenge ciphertext, so the attack needs $c' \neq c$ as well as an invertible $r$, and invertibility does not imply it. Take $K = p$, so $c \equiv 0 \pmod p$, and choose $r$ by the Chinese remainder theorem with $r \equiv 2 \pmod p$ and $r \equiv 1 \pmod q$. That $r$ is coprime to $n$ (it is $2$ mod $p$ and $1$ mod $q$, so neither prime divides it) and is not $1 \bmod n$. Yet $c' = c$: modulo $p$ both sides are $0$, and modulo $q$ multiplication by $r^e \equiv 1$ changes nothing. For the chapter’s modulus that $r$ is $6{,}957{,}319{,}475{,}842{,}508{,}646$, and the query it produces is forbidden.

$r = 2$ escapes this for every $K \in [1, n-1]$, and not merely on this modulus: it holds for every valid two-prime RSA key. The collision $c' = c$ means $c\,(2^e - 1) \equiv 0 \pmod n$. First note $c \not\equiv 0 \pmod n$, since $n \mid K^e$ would force $p \mid K$ and $q \mid K$, hence $n \mid K$, which $K \in [1, n-1]$ excludes. So some prime $\ell \in \{p, q\}$ does not divide $c$, and the collision would require $2^e \equiv 1 \pmod \ell$.

That is impossible, which is the property of $e$ the exercise asks for. Because $d$ exists, $e$ is invertible modulo $\varphi(n) = (p-1)(q-1)$, so $\gcd(e, p-1) = \gcd(e, q-1) = 1$. If $2^e \equiv 1 \pmod \ell$ then $\mathrm{ord}_\ell(2)$ divides $e$, and it divides $\ell - 1$ by Fermat, so it divides $\gcd(e, \ell - 1) = 1$. Then $2 \equiv 1 \pmod \ell$, forcing $\ell \mid 1$, which no prime does. So $r = 2$ is collision-free under any valid two-prime RSA key, and no per-modulus check is needed.

In the PKE game rather than the KEM game one further restriction is needed, because there the adversary chooses the challenge messages. If it chose $m_b = 0$ then $c^* = 0$ and $c' = c^*$ for every $r$, so the attack must pick two distinct non-zero challenge representatives, preferably coprime to $n$, before taking $r = 2$. Encapsulation cannot hand the KEM adversary that problem, since it samples $K$ from $[1, n-1]$.

The transform is not claiming that every ciphertext other than the challenge fails the check, and a strong answer avoids saying so. An attacker can always run encapsulation honestly and submit a well-formed $c'$, which passes by construction and yields its own key $H(m', c')$. What the transform buys is that an accepted ciphertext produces a key derived from its own plaintext, so nothing the oracle returns is algebraically tied to the challenge key.

The toy RSA-KEM is a weaker starting point than that, and the difference is worth stating. Textbook RSA has no encryption coins to derandomize, so the mauled $c' = c \cdot r^e$ is a legitimate encryption of $rK$ and would survive a re-encryption check. What defeats the attack in an FO-style KEM is that the shared secret is a hash of the recovered message rather than the message itself: the attacker obtains a hash of $rK$, which reveals nothing about the hash of $K$.

Exercise 3

Correctness, for every $K$ and not only the coprime ones. $\mathrm{Encap}$ samples $K$ uniformly from $\{1, \ldots, n-1\}$ with no coprimality test, and outputs $c = K^e \bmod n$. $\mathrm{Decap}$ computes $c^d \bmod n$. The RSA setup chooses $e, d$ with $ed \equiv 1 \pmod{\varphi(n)}$, so $ed = 1 + k(p-1)(q-1)$ for some non-negative integer $k$.

Work modulo each prime separately. If $p \nmid K$, Fermat’s little theorem gives $K^{p-1} \equiv 1 \pmod p$, so

$$K^{ed} = K \cdot \bigl(K^{p-1}\bigr)^{k(q-1)} \equiv K \pmod p.$$

If $p \mid K$, then both $K^{ed}$ and $K$ are $\equiv 0 \pmod p$, so the congruence holds trivially. Either way $K^{ed} \equiv K \pmod p$, and the identical argument gives $K^{ed} \equiv K \pmod q$. Since $p$ and $q$ are distinct primes, the Chinese remainder theorem lifts the two congruences to $K^{ed} \equiv K \pmod{pq}$. Both $K$ and the value $\mathrm{Decap}$ returns lie in $[0, n-1]$, so they are equal rather than merely congruent, and $\mathrm{Decap}(\mathrm{sk}, c) = K$ for every $K$ that $\mathrm{Encap}$ can produce.

Euler’s theorem from Chapter 4 proves only the case $\gcd(K, n) = 1$, because $K^{\varphi(n)} \equiv 1 \pmod n$ needs $K$ invertible. The per-prime argument above is what closes the remaining residues, and it is why the chapter can call the toy KEM’s correctness exact rather than probabilistic.

The non-coprime fraction. $K$ fails to be coprime to $n = pq$ exactly when $p \mid K$ or $q \mid K$. Let $A = \{K \in [1, n-1] : p \mid K\}$ and $B = \{K \in [1, n-1] : q \mid K\}$. Then $|A| = q - 1$ (the multiples of $p$ in $[1, n-1]$ are $p, 2p, \ldots, (q-1)p$), and similarly $|B| = p - 1$. The intersection $A \cap B$ is the set of multiples of $pq = n$ in $[1, n-1]$, which is empty. By inclusion-exclusion,

$$|A \cup B| = (q - 1) + (p - 1) - 0 = p + q - 2.$$

The exact probability is therefore $\frac{p + q - 2}{n - 1}$, and it is strictly below $\frac{1}{p} + \frac{1}{q} = \frac{p+q}{n}$. Cross-multiplying reduces that inequality to $p + q < 2n$, which holds for any primes $p, q \ge 2$ since $2pq - p - q = p(q-1) + q(p-1) \ge p + q$.

For the chapter snippet’s two 32-bit primes the exact fraction is about $6.27 \times 10^{-10}$, below $2^{-30} \approx 9.31 \times 10^{-10}$, which is the bound the chapter quotes.

What this fraction does not govern. Not $\mathrm{Decap}$ correctness, which the first half showed is exact on the whole range. And not the mauling attack of Exercise 2 either, which is the tempting misreading. That attack needs its blinding factor $r$ to be invertible, not the encapsulated $K$, and $r$ is chosen by the attacker rather than sampled: for an RSA modulus, which is odd, $r = 2$ is invertible with no test needed. Had $r$ been drawn uniformly the same count would give its rejection rate, which is the only sense in which the two quantities are related.

Real RSA-KEM samples a random integer much as this toy does. The difference is what it does with it, and it is not OAEP. RSA-KEM encrypts a random $z$ with raw RSA and derives the shared secret as $\mathrm{KDF}(z)$ rather than using $z$ as the key, so no padding is involved and every $z$ is admissible (Housley & Turner, 2025). RSAES-OAEP is a separate padded construction for encrypting a chosen message (Moriarty et al., 2016). The two are often conflated and should not be.

def coprime_failure_bound(p, q):
    n = p * q
    return (p + q - 2) / (n - 1)


for p, q in [(53, 61), (1009, 1013), (3184935163, 3199286161)]:
    print(f"p={p:>14} q={q:>14}  fraction={coprime_failure_bound(p, q):.3e}")
# ==> p=            53 q=            61  fraction=3.465e-02
# ==> p=          1009 q=          1013  fraction=1.976e-03
# ==> p=    3184935163 q=    3199286161  fraction=6.265e-10

The third row is the chapter snippet’s own modulus. The function returns the exact fraction, not the $1/p + 1/q$ upper bound.

Exercise 4

A reference statement to compare against your own version:

• Inputs. An IND-CPA-secure public-key encryption scheme $\Pi = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ that is $\delta$-correct, a key-derivation random oracle $H$, and a coin-derivation random oracle $G$.
• Output. A KEM $\Pi' = (\mathrm{Gen}', \mathrm{Encap}', \mathrm{Decap}')$ that is IND-CCA2-secure in the random oracle model. $\mathrm{Gen}'$ runs $\Pi.\mathrm{Gen}$ and also samples a uniform private seed $z \gets \mathcal{M}$, from the message space itself, which the decapsulation key carries. Naming the domain matters: the bound’s guessing term is written over $|\mathcal{M}|$, so an answer that samples $z$ from an independent $\lambda$-bit space owes a separate $q_H / 2^{\lambda}$ term for seed guessing. The query count is part of it, since the adversary gets one attempt per hash query. $\mathrm{Encap}'$ samples a plaintext $m$, computes the ciphertext $c = \mathrm{Enc}(\mathrm{pk}, m; G(m))$ with coins derived from $G(m)$, and sets the shared key to $K = H(m, c)$. $\mathrm{Decap}'$ runs $\mathrm{Dec}$ to get $m'$, re-encrypts under $G(m')$, and returns $H(m', c)$ on a byte-for-byte match. It takes the fallback branch on a mismatch and when $\mathrm{Dec}$ itself returns $\perp$. A statement that covers only the mismatch is incomplete.
• Role of the private seed $z$. On a failed re-encryption check, $\mathrm{Decap}'$ returns $\bar{K} = H(z, c)$ rather than a distinguished $\perp$ symbol. This is what makes the rejection implicit: the caller cannot tell a rejection from a success by inspecting the output. Because $z$ is secret and per-key, the adversary cannot compute the fallback itself; because the fallback depends on $c$, two different mauled ciphertexts get independently distributed fallback values, colliding only with negligible probability. Both properties are load-bearing, and neither holds for a fixed dummy key.
• Security game. IND-CCA2 for KEMs: the challenger returns $(c^*, K_b)$ where $K_0$ is the real encapsulated key and $K_1$ is uniform, and an adversary with a decapsulation oracle on every ciphertext except $c^*$ cannot guess $b$ with non-negligible advantage.
• Assumption. IND-CPA security of $\Pi$, $\delta$-correctness in the worst case over messages, a message space large enough that $q_{\mathrm{RO}} / |\mathcal{M}|$ is negligible, and the random oracle model for $G$ and $H$. The bound is $q_{\mathrm{RO}}\delta + 3 q_{\mathrm{RO}} / |\mathcal{M}| + 3\,\mathrm{Adv}^{\text{IND-CPA}}$ with $q_{\mathrm{RO}} = q_G + q_H$ (Hofheinz et al., 2017).
• Tightness. This IND-CPA-based reduction is tight: the advantage term carries only a constant factor of 3, with no factor of $q_{\mathrm{RO}}$ multiplying it. Calling the FO transform non-tight refers to the route from a one-way assumption instead, and to the QROM reductions. An answer that labels this reduction non-tight has the tightness picture backwards.

A complete answer also distinguishes the two rejection styles by name, $\mathrm{FO}^{\perp}$ versus $\mathrm{FO}^{\not\perp}$. It should state the QROM caveat too: the original FO theorem is in the classical ROM, and QROM tightness for ML-KEM’s variant is the subject of subsequent work (Chapter 11 returns to this).

One further point separates the teaching theorem from the deployed scheme. FIPS 203’s ML-KEM does not derive its success-path key as $H(m, c)$: it computes $(K, r) = G(m \,\|\, H(\mathrm{ek}))$, omitting the ciphertext, and uses $J(z \,\|\, c)$ for the implicit-rejection fallback. An answer that states the abstract theorem correctly and flags that ML-KEM deviates from it is stronger than one that conflates the two.

References

Adrian, D., Bhargavan, K., Durumeric, Z., Gaudry, P., Green, M., Halderman, J. A., Heninger, N., Springall, D., Thomé, E., Valenta, L., VanderSloot, B., Wustrow, E., Zanella-Béguelin, S., & Zimmermann, P. (2015). Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS 2015), 5–17. https://doi.org/10.1145/2810103.2813707

Hofheinz, D., Hövelmanns, K., & Kiltz, E. (2017). A modular analysis of the Fujisaki-Okamoto transformation. Theory of Cryptography – TCC 2017, Part I, 10677, 341–371. https://doi.org/10.1007/978-3-319-70500-2_12

Housley, R., & Turner, S. (2025). Use of the RSA-KEM Algorithm in the Cryptographic Message Syntax (CMS). IETF RFC 9690. https://doi.org/10.17487/RFC9690

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