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

Compute $K_b^e \bmod n$ and guess “real” exactly when it equals $c^*$. The encapsulated key always matches, and a fresh random key matches with probability about $1/n$, so the guess is almost always right without a single decapsulation query. Correctness constrains what the honest parties compute and says nothing about what an attacker can learn: the toy decapsulates every ciphertext correctly and still loses the KEM game outright. Real RSA-KEM outputs $\mathrm{KDF}(z)$ rather than $z$ (Housley & Turner, 2025), so testing a candidate key needs $z$, which needs inverting RSA.

A weak answer reaches for the mauling attack, which uses a query, or blames the 64-bit modulus.

Exercise 2

(a) Any receiver that processes ciphertexts an attacker supplies and reveals something computed from the result. A padding or format error is one, as in Bleichenbacher’s attack. A reply encrypted under the key the receiver derived is another. (b) Answering $c^*$ would let the attacker beat every KEM, by comparing the answer with $K_b$. (c) A real receiver cannot tell which ciphertexts an attacker derived from which, so the definition must not either, and that is exactly the freedom the ElGamal attack uses.

A weak answer treats the oracle as the attacker holding the private key, or says $c^*$ is excluded “because it is secret”.

Exercise 3

(a) Encrypt $m_0$ under the public key and compare the result with $c^*$. Textbook RSA is deterministic, so the two are equal exactly when $b = 0$. Against ElGamal the comparison fails even when $m_b = m_0$, because each encryption draws a fresh $r$. (b) Submit $(c_1, 4c_2)$, which is a different ciphertext from $c^*$, and divide the answer by 4 to recover $m_b$, which names $b$. (c) IND-CPA gives the attacker less, no decryption access, so more schemes pass it. The ElGamal attack uses algebra rather than computation, so it works at every key size, and a longer key cannot stop it.

A weak answer says weaker means fewer bits of security.

Exercise 4

With the changed fallback the three lines are True, then False, then False True True. The honest round trip and the re-encryption comparison never reach the fallback, so the first two lines are unchanged. The third changes: two decapsulations of the same rejected ciphertext now return different values, which a successful decapsulation never does.

(a) With fresh randomness Bob cannot recompute the ciphertext and has nothing to compare against. With $r = G(m)$ the ciphertext is a function of $m$ and the public key, so Bob can recompute it from the $m'$ he decrypts and compare. A ciphertext passes exactly when it is the encryption of its own decryption. That tests consistency, not whether the sender knew the plaintext, so a modified ciphertext can still pass by luck.

(b) The third line is half the answer. Fresh random bytes let the attacker recognize a rejection by querying twice and comparing, since a success always returns the same key. A fixed dummy key is predictable, so the attacker could recognize a rejection, and two mauled ciphertexts would share it. $H(z, c)$ is unpredictable without $z$ and stable for each ciphertext, so it looks like a key.

A weak answer says the fallback is random and therefore safe, or that implicit rejection is what makes the KEM CCA-secure.

Exercise 5

The ciphertext length is $32(d_u k + d_v) = 32(10 \cdot 3 + 4) = 1{,}088$ bytes.

(a) The 1,087-byte input fails the ciphertext check, so ML-KEM.Decaps shall not run. The caller sees whatever error the implementation uses for a failed input check, since FIPS 203 does not prescribe one. The random 1,088-byte string passes the ciphertext check, so with a checked decapsulation key, decapsulation runs and returns 32 bytes with no error. Almost certainly they are the fallback $J(z \,\|\, c)$. A ciphertext passes re-encryption only if it is the encryption of its own decryption, and at most $2^{256}$ of the $2^{8704}$ strings of that length are, one for each message. If the string did pass, the caller would receive the success-path key.

(b) Anyone with the encapsulation key can make a ciphertext that decapsulates, so success authenticates nobody, and authentication needs a signature or an authenticated protocol. CCA security comes from re-encryption with derived randomness plus hashing to the key. Explicit-rejection variants also have proofs, and implicit rejection removes the rejection signal from the interface.

(c) $G$, $H$ and $J$ are SHA3-512, SHA3-256 and SHAKE256 (National Institute of Standards and Technology, 2024, sec. 4.1), fixed public functions rather than random oracles, and a quantum attacker can query them in superposition, which is why post-quantum arguments use the QROM.

A weak answer says the random string “returns an error” or “returns $\perp$”.

Exercise 6

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. In 2015 the Logjam analysis estimated the number field sieve’s precomputation against a single 1024-bit prime at about 45 million core-years, “not necessarily out of reach for a nation state” (Adrian et al., 2015, sec. 4.1). It recommended that servers move to groups of 2048 bits or more (Adrian et al., 2015, sec. 5). NIST’s key-management guidance rates finite-field Diffie-Hellman with a 2048-bit prime and a 224-bit private key at 112 bits of security, and with a 1024-bit prime and a 160-bit private key at 80 bits or less (Barker, 2020, sec. 5.6.1.1). It no longer approves anything below 112 bits for protecting federal government information (Barker, 2020, sec. 5.6.1.1). This answer takes 2048 bits as its working minimum.

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

Exercise 7

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 game excludes the challenge ciphertext from the oracle, 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 8

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 7 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 9

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 HHK theorem above 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

Barker, E. (2020). Recommendation for Key Management, Part 1: General Revision 5. NIST Special Publication 800-57 Part 1 Revision 5. https://doi.org/10.6028/NIST.SP.800-57pt1r5

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

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