The Lumenary · Early undergraduate

Cryptography

Name: ______________________

Date: ______________________

You will learn to

Implement RSA key generation, encryption and decryption, and prove that decryption works for every message using Fermat's little theorem and the Chinese remainder theorem
Compute modular powers by repeated squaring and prove that it uses $O(\log e)$ multiplications
Carry out a Diffie–Hellman key exchange and explain its reliance on the difficulty of discrete logarithms
Prove that the one-time pad has perfect secrecy, and explain why practical systems rely instead on unproved hardness assumptions
Explain why textbook RSA is unsafe in practice and why encryption alone does not guarantee authenticity

1.
A toy RSA public key is $(n, e) = (33, 3)$ , where $33 = 3 \cdot 11$ . Encrypt the message $m = 5$ : compute $c = m^e \bmod n$ .
2.
For the toy key $p = 5$ , $q = 11$ , $n = 55$ and $e = 3$ , find the private exponent $d$ with $0 < d < 40$ and $ed \equiv 1 \pmod{(p - 1)(q - 1)}$ .
3.
With the key $n = 55$ , $e = 3$ , $d = 27$ , a ciphertext $c = 13$ arrives. Decrypt it: find $m = c^d \bmod 55$ . (Hint: you can check your answer by encrypting it.)
4.
Ama and Bolat use Diffie–Hellman with $p = 29$ and $g = 2$ . Ama's secret is $a = 5$ , Bolat's is $b = 12$ . Ama sends $A = 2^5 \bmod 29 = 3$ and Bolat sends $B = 2^{12} \bmod 29 = 7$ . What shared key do they compute?
5.
An attacker knows the public key $(n, e)$ of an RSA user. Which additional pieces of information would let the attacker compute the private exponent $d$ efficiently, with known methods? (Choose all that apply.)
- A.the factors $p$ and $q$ of $n$
- B.the number $\varphi(n) = (p - 1)(q - 1)$
- C.one message $m$ together with its ciphertext $m^e \bmod n$
- D.nothing more: $d$ can be computed from $n$ and $e$ by repeated squaring
6.
Textbook RSA with $e = 3$ and a 2048-bit modulus $n$ is used to send a 100-bit number $m$ , as $c = m^3 \bmod n$ . What can an eavesdropper do?
- A.Recover $m$ as the ordinary integer cube root of $c$
- B.Nothing, because recovering $m$ requires factoring $n$
- C.Compute $d$ from $c$ by Euclid's algorithm
- D.Use Fermat's little theorem modulo $n$ to undo the cube
7.
Which Lean statement is a true formalisation of RSA correctness, as proved in the lesson?
- A.theorem t {p q e d : ℕ} (hp : p.Prime) (hq : q.Prime) (hpq : p ≠ q) (hed : e * d ≡ 1 [MOD (p - 1) * (q - 1)]) (m : ℕ) : (m ^ e) ^ d ≡ m [MOD p * q]
- B.theorem t {p q e d : ℕ} (hp : p.Prime) (hq : q.Prime) (hed : e * d ≡ 1 [MOD (p - 1) * (q - 1)]) (m : ℕ) : (m ^ e) ^ d ≡ m [MOD p * q]
- C.theorem t {p q e d : ℕ} (hp : p.Prime) (hq : q.Prime) (hpq : p ≠ q) (m : ℕ) : (m ^ e) ^ d ≡ m [MOD p * q]
- D.theorem t (n e : ℕ) : ¬ ∃ d, ∀ m, (m ^ e) ^ d ≡ m [MOD n]
8.
Implement pow_mod(b, e, n) by repeated squaring without using Python's three-argument pow: return $b^e \bmod n$ . It must handle exponents with hundreds of digits instantly.
Computational — Practice

Answer key — Cryptography

1.
$5^3 = 125 = 3 \cdot 33 + 26$ , so $c = 26$ .
2.
$(p - 1)(q - 1) = 40$ and $3 \cdot 27 = 81 = 2 \cdot 40 + 1$ , so $d = 27$ . (Euclid: $40 = 13 \cdot 3 + 1$ , so $1 = 40 - 13 \cdot 3$ and $d \equiv -13 \equiv 27$ .)
3.
Modulo $5$ : $13^{27} \equiv 3^{27} \equiv 3^3 = 27 \equiv 2$ . Modulo $11$ : $13^{27} \equiv 2^{27} \equiv 2^7 = 128 \equiv 7$ . The number below $55$ that is $\equiv 7 \pmod{11}$ and $\equiv 2 \pmod 5$ is $7$ . Check: $7^3 = 343 = 6 \cdot 55 + 13$ . (Decrypting modulo $p$ and $q$ separately and recombining is exactly how real RSA implementations speed up decryption.)
4.
$7^5 \bmod 29$ : $7^2 \equiv 20$ , $7^4 \equiv 20^2 = 400 = 13 \cdot 29 + 23 \equiv 23$ , $7^5 \equiv 23 \cdot 7 = 161 = 5 \cdot 29 + 16 \equiv 16$ . Bolat gets the same from $3^{12} \bmod 29$ , since both equal $2^{60} \bmod 29$ . The key is $16$ .
5.
The factors, or $\varphi(n)$ , reveal $d$ : with $\varphi(n)$ known, Euclid's algorithm inverts $e$ . Knowing $\varphi(n)$ is equivalent to knowing the factors, since $p + q = n - \varphi(n) + 1$ and $pq = n$ . Plaintext–ciphertext pairs are free to anyone with the public key. Whether $(n, e)$ alone suffices is exactly the question of whether factoring is hard.
6.
$m < 2^{100}$ gives $m^3 < 2^{300} < n$ , so $c = m^3$ as an integer and $m = \sqrt[3]{c}$ is found by ordinary root extraction (for example by bisection). This is one of several reasons why real RSA pads messages with randomness before encrypting.
7.
Option (a) is rsa_correct. Dropping $p \neq q$ (b) breaks the Chinese remainder step and the theorem: modulo $9$ , $3^5 \equiv 0 \neq 3$ . Dropping the key condition (c) makes the statement false. Option (d) is not correctness at all, and is false.
8.
```
def pow_mod(b, e, n):
    result, base = 1 % n, b % n
    while e > 0:
        if e & 1:
            result = result * base % n
        base = base * base % n
        e >>= 1
    return result
```
The loop runs once per bit of $e$ — about $1000$ times for a $300$ -digit exponent — and every number stays below $n^2$ . This is the right-to-left version of the lesson's recursion: the bits of $e$ decide which squares $b^{2^j}$ go into the product.