Skip to content

Appendix C: Selected Exercise Solutions

This appendix provides complete solutions to selected exercises from each chapter.

Chapter 1: Mathematical Foundations

Solution. [Exercise 1.1] Compute \(17^{-1} \bmod 31\):

Apply extended Euclidean algorithm to \((31, 17)\):

\[\begin{align*} 31 &= 1 \cdot 17 + 14 \\ 17 &= 1 \cdot 14 + 3 \\ 14 &= 4 \cdot 3 + 2 \\ 3 &= 1 \cdot 2 + 1 \\ 2 &= 2 \cdot 1 \end{align*}\]

Back-substituting:

\[\begin{align*} 1 &= 3 - 1 \cdot 2 \\ &= 3 - 1 \cdot (14 - 4 \cdot 3) = 5 \cdot 3 - 14 \\ &= 5 \cdot (17 - 14) - 14 = 5 \cdot 17 - 6 \cdot 14 \\ &= 5 \cdot 17 - 6 \cdot (31 - 17) = 11 \cdot 17 - 6 \cdot 31 \end{align*}\]

So \(17^{-1} \equiv 11 \pmod{31}\). Check: \(17 \times 11 = 187 = 6 \times 31 + 1 \equiv 1 \pmod{31}\). ✓

Solution. [Exercise 1.3] Compute \(2^{100} \bmod 13\):

By Fermat’s Little Theorem, \(2^{12} \equiv 1 \pmod{13}\) (since 13 is prime and \(13 \nmid 2\)).

Write \(100 = 8 \times 12 + 4\), so:

\[2^{100} = 2^{8 \times 12 + 4} = (2^{12})^8 \cdot 2^4 \equiv 1^8 \cdot 16 \equiv 3 \pmod{13}\]

Solution. [Exercise 1.6] (a) \(H = \log_2(26^8) = 8\log_2 26 \approx 8 \times 4.700 = 37.6\) bits.

(b) Exhaustive search: \(26^8 = 208{,}827{,}064{,}576 \approx 2.1 \times 10^{11}\) passwords. At \(10^9\) per second: average \(\approx 10^{11}\) attempts \(\div 10^9\)/sec \(= 100\) seconds.

(c) For \(\geq 80\) bits: need alphabet size \(|\Sigma|^n \geq 2^{80}\). With \(n = 12\): \(|\Sigma| \geq 2^{80/12} = 2^{6.67} \approx 102\). Use printable ASCII (95 characters) with \(n \geq 13\), giving \(95^{13} \approx 2^{85}\) — above threshold.

Chapter 2: Symmetric Cryptography

Solution. [Exercise 2.2] GCM nonce reuse attack:

If nonces \(N\) are reused with the same key \(K\):

\[\begin{align*} C_1 &= M_1 \oplus \text{KS}_N, \quad T_1 = \text{GHASH}(H, C_1, \text{AAD}_1) \oplus E_K(\text{cnt}_0) \\ C_2 &= M_2 \oplus \text{KS}_N, \quad T_2 = \text{GHASH}(H, C_2, \text{AAD}_2) \oplus E_K(\text{cnt}_0) \end{align*}\]

Where \(H = E_K(0^{128})\) is the GHASH key.

From the two tag equations:

\[T_1 \oplus T_2 = \text{GHASH}(H, C_1, \text{AAD}_1) \oplus \text{GHASH}(H, C_2, \text{AAD}_2)\]

This is a polynomial equation in \(H\) over \(\mathbb{F}_{2^{128}}\). Since GHASH is polynomial with known coefficients (from known \(C_1, C_2, \text{AAD}_1, \text{AAD}_2\)), we can solve for \(H\) directly. With \(H\) known, we can forge authentication tags for any message. Also, \(M_1 \oplus M_2 = C_1 \oplus C_2\), revealing plaintext.

Chapter 3: Public-Key Cryptography

Solution. [Exercise 3.3] ECDSA nonce recovery:

Given same \(k\) for two messages with \(r = 13\), \(s_1 = 15\), \(s_2 = 25\), \(h_1 = 10\), \(h_2 = 20\), \(n = 37\):

From ECDSA: \(s = k^{-1}(h + rd) \bmod n\)

\[s_1 - s_2 = k^{-1}(h_1 - h_2) \bmod 37 = k^{-1}(10 - 20) = k^{-1}(-10) \bmod 37\]
\[15 - 25 = -10 \equiv 27 \pmod{37}\]

So \(k^{-1}(-10) \equiv 27 \pmod{37}\), thus \(k^{-1} \equiv 27 \cdot (-10)^{-1} \pmod{37}\).

\((-10)^{-1} \bmod 37\): \(-10 \equiv 27 \pmod{37}\); \(27^{-1} \bmod 37\): using extended GCD, \(27 \times 11 = 297 = 8 \times 37 + 1\), so \(27^{-1} = 11\).

\(k^{-1} = 27 \times 11 = 297 \equiv 297 - 8\times 37 = 1 \pmod{37}\). So \(k^{-1} = 1\), thus \(k = 1\).

Now recover \(d\): \(s_1 = k^{-1}(h_1 + rd) \bmod 37 \Rightarrow 15 = 1 \cdot (10 + 13d) \Rightarrow 13d = 5 \Rightarrow d = 5 \times 13^{-1} \bmod 37\).

\(13^{-1} \bmod 37\): \(13 \times 20 = 260 = 7 \times 37 + 1\), so \(13^{-1} = 20\).

\(d = 5 \times 20 = 100 \equiv 100 - 2 \times 37 = 26 \pmod{37}\).

Private key \(d = 26\).

Chapter 4: Hash Functions and MACs

Solution. [Exercise 4.4] Argon2id tuning:

(a) Target: \(\leq 500\)ms on server hardware. Benchmark Argon2id with different parameters on the target machine. On typical modern server hardware:

  • time_cost=3, memory_cost=65536 (64 MB), parallelism=4 gives \(\approx 200\)–\(400\)ms

  • Adjust time_cost to hit the \(\approx 500\)ms target

(b) GPU resistance for \(> 2^{50}\) iterations: With memory_cost=65536 (64 MB): GPU has limited VRAM; each GPU core needs 64 MB, severely limiting parallelism. Typical H100 GPU with 80 GB VRAM: \(80{,}000 / 64 = 1{,}250\) parallel hashes. At 500ms per hash on GPU (memory-hard): \(1{,}250 / 0.5 = 2{,}500\) H/s. To achieve \(2^{50}\) attempts: \(2^{50} / 2500 \approx 4.5 \times 10^{11}\) seconds \(\approx 14{,}000\) years.

Recommendation: time_cost=3, memory_cost=65536, parallelism=4.

Chapter 5: Key Management

Solution. [Exercise 5.1] Shamir \((3,5)\) secret sharing over \(\mathbb{F}_{97}\), secret \(S = 42\):

Choose random polynomial \(f(x) = 42 + a_1 x + a_2 x^2\) over \(\mathbb{F}_{97}\). Let \(a_1 = 13\), \(a_2 = 7\) (random).

Shares:

\[\begin{align*} f(1) &= 42 + 13 + 7 = 62 \\ f(2) &= 42 + 26 + 28 = 96 \\ f(3) &= 42 + 39 + 63 = 144 \equiv 47 \pmod{97} \\ f(4) &= 42 + 52 + 112 = 206 \equiv 12 \pmod{97} \\ f(5) &= 42 + 65 + 175 = 282 \equiv 88 \pmod{97} \end{align*}\]

Reconstruction from shares \((1,62), (2,96), (3,47)\): Lagrange interpolation to find \(f(0)\):

\[f(0) = 62 \cdot \frac{(0-2)(0-3)}{(1-2)(1-3)} + 96 \cdot \frac{(0-1)(0-3)}{(2-1)(2-3)} + 47 \cdot \frac{(0-1)(0-2)}{(3-1)(3-2)}\]
\[= 62 \cdot \frac{6}{2} + 96 \cdot \frac{3}{-1} + 47 \cdot \frac{2}{2} = 186 - 288 + 47 = -55 \equiv 42 \pmod{97}\]

Recovered secret: \(42\). ✓

Chapter 7: Post-Quantum Cryptography

Solution. [Exercise 7.4] AES-256 vs RSA-2048 against quantum computers:

RSA-2048: Security relies on the Integer Factoring Problem. Shor’s algorithm factors \(n\)-bit integers in \(O(n^3)\) quantum gate operations. For RSA-2048: approximately \(2^{11} \approx 2000\) logical qubits with error correction are needed—feasible on a CRQC. Security against quantum: 0 bits.

AES-256: Security relies on exhaustive key search. Grover’s algorithm provides a quadratic speedup: searches \(N\) items in \(O(\sqrt{N})\) quantum evaluations. For AES-256: \(\sqrt{2^{256}} = 2^{128}\) quantum AES evaluations needed. This is infeasible even with a quantum computer.

Key distinction: Shor’s algorithm provides exponential speedup (polynomial vs. exponential classical); Grover provides only quadratic speedup. AES-256 simply doubles key length to maintain security against Grover’s quadratic speedup.

Chapter 24: Exploit Development

Solution. [Sample: Stack Overflow Offset] Finding return address offset using pwntools cyclic pattern:

from pwn import *

# Generate cyclic pattern
pattern = cyclic(200)

# After crash, read EIP/RIP value from crash dump
# e.g., EIP = 0x6161616e ("naaa" in little-endian)

# Find offset
offset = cyclic_find(0x6161616e)  # or cyclic_find(b'naaa')
print(f"Offset to return address: {offset} bytes")

# Construct exploit
padding = b'A' * offset
ret_addr = p64(0xdeadbeef)  # Target address
payload = padding + ret_addr