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)\):
Back-substituting:
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:
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\):
Where \(H = E_K(0^{128})\) is the GHASH key.
From the two tag equations:
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\)
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:
Reconstruction from shares \((1,62), (2,96), (3,47)\): Lagrange interpolation to find \(f(0)\):
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