28-04 — Asymmetric Encryption: RSA and Diffie-Hellman

Phase: Cryptography | Subject: 28-04 Prerequisites: 28-03-symmetric-encryption.md, 28-01-modular-arithmetic-review.md Next subject: 28-05-hash-functions-digital-signatures.md

Learning Objectives

By the end of this subject, you will be able to:

1. Explain the key distribution problem that asymmetric cryptography solves
2. Generate RSA key pairs and perform encryption/decryption
3. Prove RSA correctness using Euler's theorem
4. Implement and analyze the Diffie-Hellman key exchange protocol
5. Identify security requirements for RSA and DH (key sizes, padding)

Core Content

The Key Distribution Problem

Symmetric cryptography requires both parties to share a secret key. How do you securely share it? Asymmetric (public-key) cryptography solves this: each party has a public key (can be shared openly) and a private key (kept secret).

RSA Cryptosystem

Invented by Rivest, Shamir, and Adleman (1977). Security is based on the hardness of factoring large integers.

Key Generation: 1. Choose two large random primes $p$ and $q$ (e.g., 1024+ bits each) 2. Compute $n = p \cdot q$ (the modulus) 3. Compute $\varphi(n) = (p-1)(q-1)$ 4. Choose $e$ such that $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$ - Common choice: $e = 65537$ ($2^{16} + 1$, prime, small Hamming weight for fast encryption) 5. Compute $d \equiv e^{-1} \pmod{\varphi(n)}$ (the private exponent)

Public key: $(n, e)$. Private key: $(n, d)$ (or $(p, q, d)$).

Encryption: $$c \equiv m^e \pmod{n}$$

Decryption: $$m \equiv c^d \pmod{n}$$

Proof of correctness: $m \equiv (m^e)^d \equiv m^{ed} \pmod{n}$.

Since $ed \equiv 1 \pmod{\varphi(n)}$, we have $ed = 1 + k\varphi(n)$ for some integer $k$.

$m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^{k}$.

If $\gcd(m, n) = 1$, Euler's theorem gives $m^{\varphi(n)} \equiv 1 \pmod{n}$, so $m^{ed} \equiv m \pmod{n}$.

If $\gcd(m, n) \neq 1$, the proof still holds using CRT (since $m^p \equiv m \pmod{p}$ and similarly for $q$). This holds for ALL $m \in [0, n-1]$.

⚠️ CRITICAL: Textbook RSA (raw $m^e \bmod n$) is insecure. Real implementations use padding schemes (OAEP) to prevent deterministic encryption, small-$e$ attacks, and chosen-ciphertext attacks.

RSA Security

RSA security relies on: 1. Factoring problem: given $n = pq$, find $p$ and $q$ 2. RSA problem: given $(n, e, c)$, find $m$ (equivalent to factoring, believed) 3. Key sizes: 2048-bit RSA ≈ 112-bit symmetric security; 3072-bit ≈ 128-bit security

Common attacks on naive RSA: - Small $m$: if $m^e < n$, then $c = m^e$ over integers — just take the $e$-th root - Common modulus: if two users share $n$, each can decrypt the other's messages - Small $d$ (Wiener's attack): if $d < n^{0.25}/3$, it can be recovered from $(n, e)$ - Håstad's broadcast attack: same $m$ encrypted with $e=3$ to three different $n$'s — CRT recovers $m$

Diffie-Hellman Key Exchange

Published by Diffie and Hellman (1976). Enables two parties to agree on a shared secret over a public channel.

Protocol: 1. Agree on public parameters: large prime $p$ and generator $g$ of $\mathbb{Z}_p^*$ 2. Alice chooses random $a \in [1, p-2]$, sends $A = g^a \bmod p$ 3. Bob chooses random $b \in [1, p-2]$, sends $B = g^b \bmod p$ 4. Shared secret: $K = B^a \bmod p = A^b \bmod p = g^{ab} \bmod p$

Security: based on the Discrete Logarithm Problem (DLP) — given $(g, g^a \bmod p)$, find $a$.

Computational Diffie-Hellman (CDH): given $(g, g^a, g^b)$, compute $g^{ab}$.

Decisional Diffie-Hellman (DDH): distinguish $(g^a, g^b, g^{ab})$ from $(g^a, g^b, g^c)$ for random $c$.

Security considerations: - $p$ should be at least 2048 bits - $g$ should generate a large prime-order subgroup - Vulnerable to man-in-the-middle attacks without authentication - Safe primes ($p = 2q + 1$ where $q$ is prime) are often used

ElGamal Encryption

Extension of Diffie-Hellman to encryption:

Key generation: private key $x$, public key $h = g^x \bmod p$.

Encryption of message $m$: - Choose random $r$ - $c_1 = g^r \bmod p$ - $c_2 = m \cdot h^r \bmod p$

Decryption: $m = c_2 \cdot (c_1^x)^{-1} \bmod p$.

RSA vs Diffie-Hellman at a Glance

Key Terms

• Public-Key Cryptography — asymmetric; separate keys for encryption and decryption
• RSA — factoring-based public-key encryption and signature scheme
• Modulus $n = pq$ — product of two large secret primes
• Public Exponent $e$ — typically 65537
• Private Exponent $d$ — $e^{-1} \bmod \varphi(n)$
• Diffie-Hellman Key Exchange — discrete-log-based key agreement
• Discrete Logarithm Problem (DLP) — given $g^x$, find $x$
• Generator — element whose powers generate the whole group
• Man-in-the-Middle Attack — attacker intercepts and relays messages
• OAEP (Optimal Asymmetric Encryption Padding) — secure padding for RSA encryption

Worked Examples

Example 1: RSA Key Generation and Encryption

Generate keys with $p = 11$, $q = 13$, $e = 7$. Encrypt $m = 5$.

Solution:

$n = 11 \cdot 13 = 143$. $\varphi(n) = 10 \cdot 12 = 120$.

Check $\gcd(7, 120) = 1$ ✓.

$d \equiv 7^{-1} \pmod{120}$. Extended Euclidean: $120 = 17 \cdot 7 + 1 \Rightarrow 1 = 120 - 17 \cdot 7$, so $d \equiv -17 \equiv 103 \pmod{120}$.

Check: $7 \cdot 103 = 721 = 6 \cdot 120 + 1$ ✓.

Public key: $(143, 7)$. Private key: $(143, 103)$.

Encrypt $m = 5$: $c = 5^7 \bmod 143$. $5^2 = 25$, $5^4 = 25^2 = 625 \equiv 625 - 4 \cdot 143 = 625 - 572 = 53$. $5^7 = 5^4 \cdot 5^2 \cdot 5^1 = 53 \cdot 25 \cdot 5 = 53 \cdot 125$.

$125 \equiv 125 - 143 = -18 \equiv 125$ (wait, $125 < 143$, so $125$). $53 \cdot 125 = 6625$. $6625 \div 143 = 46 \cdot 143 = 6578$, remainder $47$. $c = 47$.

Decrypt: $47^{103} \bmod 143$. By Euler: $47^{120} \equiv 1 \pmod{143}$ (since $\gcd(47, 143)=1$). $103 = 120 - 17$. $47^{103} \equiv 47^{-17} \equiv (47^{-1})^{17}$... or simply compute $47^{103} \bmod 143$ using the fact it should be $5$. Indeed, $47^{103} \bmod 143 = 5$. ✓

Example 2: Diffie-Hellman Key Exchange

Use $p = 23$, $g = 5$. Alice picks $a = 6$, Bob picks $b = 15$. Compute the shared secret.

Solution:

Alice computes $A = 5^6 \bmod 23 = 15625 \bmod 23$. $5^2 = 25 \equiv 2$, $5^4 \equiv 2^2 = 4$, $5^6 = 5^4 \cdot 5^2 \equiv 4 \cdot 2 = 8$. So $A = 8$.

Bob computes $B = 5^{15} \bmod 23$. $5^2 \equiv 2$, $5^4 \equiv 4$, $5^8 \equiv 4^2 = 16$, $5^{15} = 5^8 \cdot 5^4 \cdot 5^2 \cdot 5^1 \equiv 16 \cdot 4 \cdot 2 \cdot 5 = 640$. $640 \div 23 = 27 \cdot 23 = 621$, remainder $19$. So $B = 19$.

Alice computes $K_A = B^a \bmod 23 = 19^6 \bmod 23$. $19 \equiv -4 \pmod{23}$. $(-4)^2 = 16$, $(-4)^4 = 16^2 = 256 \equiv 256 - 11 \cdot 23 = 256 - 253 = 3$. $(-4)^6 = (-4)^4 \cdot (-4)^2 \equiv 3 \cdot 16 = 48 \equiv 2 \pmod{23}$.

Bob computes $K_B = A^b \bmod 23 = 8^{15} \bmod 23$. $8^2 = 64 \equiv 64 - 2 \cdot 23 = 18 \equiv -5$. $8^4 \equiv (-5)^2 = 25 \equiv 2$. $8^8 \equiv 2^2 = 4$. $8^{15} = 8^8 \cdot 8^4 \cdot 8^2 \cdot 8^1 \equiv 4 \cdot 2 \cdot 18 \cdot 8 = 1152$. $1152 \div 23 = 50 \cdot 23 = 1150$, remainder $2$.

Both get $K = 2$. ✓

Example 3: Small-$e$ Attack

Alice, Bob, and Charlie each have RSA keys with $e = 3$. Their moduli are $n_A = 377$, $n_B = 391$, $n_C = 589$. The same message $m$ is sent to all three, producing $c_A, c_B, c_C$. What's the vulnerability?

Solution:

With $e=3$, $c_A = m^3 \bmod n_A$, etc. If $m^3 < n_A n_B n_C$, then CRT recovers $m^3$ as an integer. Taking the cube root yields $m$. The attack works because $n_A, n_B, n_C$ are pairwise coprime.

This is why RSA needs random padding (OAEP) — each encryption produces a DIFFERENT padded message, so CRT doesn't help.

Quiz

Q1: What does the concept of Discrete Logarithm Problem (DLP) primarily refer to in this subject?

A) A computational error related to Discrete Logarithm Problem (DLP) B) A visual representation of Discrete Logarithm Problem (DLP) C) The definition and application of Discrete Logarithm Problem (DLP) D) A historical anecdote about Discrete Logarithm Problem (DLP)

Correct: C)

• If you chose A: This is incorrect. Discrete Logarithm Problem (DLP) is defined as: the definition and application of discrete logarithm problem (dlp). The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Discrete Logarithm Problem (DLP) is defined as: the definition and application of discrete logarithm problem (dlp). The other options describe different aspects that are not the primary focus.
• If you chose C: Discrete Logarithm Problem (DLP) is defined as: the definition and application of discrete logarithm problem (dlp). The other options describe different aspects that are not the primary focus. Correct!
• If you chose D: This is incorrect. Discrete Logarithm Problem (DLP) is defined as: the definition and application of discrete logarithm problem (dlp). The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) n = p \cdot q B) An unrelated formula from a different topic C) A simplified version of n = p \cdot q... D) The inverse operation of the formula in question

Correct: A)

• If you chose A: The formula n = p \cdot q is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose B: This is incorrect. The formula n = p \cdot q is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula n = p \cdot q is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula n = p \cdot q is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Public-Key Cryptography?

A) It is used to public-key cryptography in mathematical analysis B) It is primarily a historical notation system C) It replaces all other methods in this domain D) It is used only in advanced research contexts

Correct: A)

• If you chose A: Public-Key Cryptography serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose B: This is incorrect. Public-Key Cryptography serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: This is incorrect. Public-Key Cryptography serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: This is incorrect. Public-Key Cryptography serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Diffie-Hellman Key Exchange is TRUE?

A) Diffie-Hellman Key Exchange is not related to this subject B) Diffie-Hellman Key Exchange is mentioned only as a historical footnote C) Diffie-Hellman Key Exchange is a fundamental concept covered in this subject D) Diffie-Hellman Key Exchange is an advanced topic beyond this subject's scope

Correct: C)

• If you chose A: This is incorrect. Diffie-Hellman Key Exchange is a fundamental concept covered in this subject. This subject covers Diffie-Hellman Key Exchange as part of its core content.
• If you chose B: This is incorrect. Diffie-Hellman Key Exchange is a fundamental concept covered in this subject. This subject covers Diffie-Hellman Key Exchange as part of its core content.
• If you chose C: Diffie-Hellman Key Exchange is a fundamental concept covered in this subject. This subject covers Diffie-Hellman Key Exchange as part of its core content. Correct!
• If you chose D: This is incorrect. Diffie-Hellman Key Exchange is a fundamental concept covered in this subject. This subject covers Diffie-Hellman Key Exchange as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) The inverse of the correct answer B) A different result from a common mistake C) An unrelated numerical value D) Diffie-Hellman Key Exchange

Correct: D)

• If you chose A: This is incorrect. The worked examples show that the result is Diffie-Hellman Key Exchange. The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is Diffie-Hellman Key Exchange. The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is Diffie-Hellman Key Exchange. The other options represent common errors.
• If you chose D: The worked examples show that the result is Diffie-Hellman Key Exchange. The other options represent common errors. Correct!

Q6: How are Diffie-Hellman Key Exchange and Generator related?

A) Diffie-Hellman Key Exchange and Generator are completely unrelated topics B) Diffie-Hellman Key Exchange is the inverse of Generator C) Diffie-Hellman Key Exchange and Generator are closely related concepts D) Diffie-Hellman Key Exchange is a special case of Generator

Correct: C)

• If you chose A: This is incorrect. Both Diffie-Hellman Key Exchange and Generator are covered in this subject as interconnected topics.
• If you chose B: This is incorrect. Both Diffie-Hellman Key Exchange and Generator are covered in this subject as interconnected topics.
• If you chose C: Both Diffie-Hellman Key Exchange and Generator are covered in this subject as interconnected topics. Correct!
• If you chose D: This is incorrect. Both Diffie-Hellman Key Exchange and Generator are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Man-in-the-Middle Attack?

A) The main error with Man-in-the-Middle Attack is using it when it is not needed B) Man-in-the-Middle Attack is always computed the same way in all contexts C) A common mistake is confusing Man-in-the-Middle Attack with a similar concept D) Man-in-the-Middle Attack has no common misconceptions

Correct: C)

• If you chose A: This is incorrect. Students often confuse Man-in-the-Middle Attack with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: This is incorrect. Students often confuse Man-in-the-Middle Attack with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: Students often confuse Man-in-the-Middle Attack with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose D: This is incorrect. Students often confuse Man-in-the-Middle Attack with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply OAEP (Optimal Asymmetric Encryption Padding)?

A) Avoid OAEP (Optimal Asymmetric Encryption Padding) unless explicitly instructed B) OAEP (Optimal Asymmetric Encryption Padding) is not practically useful C) Apply OAEP (Optimal Asymmetric Encryption Padding) to solve problems in this subject's domain D) Use OAEP (Optimal Asymmetric Encryption Padding) only in pure mathematics contexts

Correct: C)

• If you chose A: This is incorrect. OAEP (Optimal Asymmetric Encryption Padding) is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. OAEP (Optimal Asymmetric Encryption Padding) is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: OAEP (Optimal Asymmetric Encryption Padding) is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose D: This is incorrect. OAEP (Optimal Asymmetric Encryption Padding) is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. For RSA with $p=7$, $q=17$, $e=5$, find $d$.
   

   Click for answer

   $n=119$, $\varphi=96$. Ext Euclid: $96=19\cdot 5+1$, $1=96-19\cdot 5$, $d\equiv -19\equiv 77 \pmod{96}$. Check: $5\cdot 77=385=4\cdot 96+1$. ✓

2. Diffie-Hellman with $p=11$, $g=2$, $a=4$, $b=3$. Find the shared secret.
   

   Click for answer

   $A=2^4=16\equiv 5$, $B=2^3=8$. Alice: $8^4\equiv (8^2)^2\equiv 64^2\equiv 9^2=81\equiv 4$. Bob: $5^3=125\equiv 4$. Shared: $4$.

3. Why is $e=3$ a bad choice for RSA without padding?
   

   Click for answer

   If $m^3 < n$, the cube root over integers directly recovers $m$. Also Håstad's broadcast attack. $e=65537$ is standard.

4. What makes Diffie-Hellman vulnerable to man-in-the-middle attacks?
   

   Click for answer

   DH authenticates nothing. An attacker can establish separate shared secrets with Alice and Bob, relaying traffic. Authentication (digital signatures or certificates) is needed.

5. Compute $\varphi(143)$ and verify that $e=7$ is valid.
   

   Click for answer

   $143=11\cdot 13$. $\varphi=10\cdot 12=120$. $\gcd(7,120)=1$, so $e=7$ is valid. Any $e$ coprime to 120 works.

Summary

Key takeaways:

• RSA: $n=pq$, $ed \equiv 1 \pmod{\varphi(n)}$, encryption $c=m^e$, decryption $m=c^d$
• Security rests on factoring; 2048-bit RSA is the current minimum
• Diffie-Hellman enables key agreement over public channels
• Both RSA and DH are vulnerable to Shor's quantum algorithm
• Textbook RSA is insecure; always use proper padding (OAEP)

Pitfalls

• Using textbook RSA without padding. Raw $c = m^e \bmod n$ is deterministic (same message → same ciphertext), vulnerable to small-$e$ attacks when $m^e < n$, and susceptible to chosen-ciphertext attacks. Always use OAEP or equivalent padding in practice.
• Assuming Diffie-Hellman provides authentication. DH is a key agreement protocol — it lets two parties agree on a shared secret, but it does not authenticate either party. Without digital signatures or certificates, DH is vulnerable to man-in-the-middle attacks.
• Choosing $e=3$ without understanding the risks. A small public exponent enables the Håstad broadcast attack (same message sent to three recipients with $e=3$ allows CRT-based recovery) and the small-$m$ root-extraction attack. The standard choice is $e=65537$.
• Miscomputing $\phi(n)$ for RSA. $\phi(n) = (p-1)(q-1)$ only when $p$ and $q$ are distinct primes. For prime powers ($n = p^k$), $\phi(n) = p^{k-1}(p-1)$. Confusing $\phi(n)$ with $n-1$ or using it incorrectly means $d$ won't be a valid decryption exponent.
• Ignoring quantum vulnerability. Both RSA (factoring) and Diffie-Hellman (discrete log) are broken by Shor's algorithm running on a sufficiently large quantum computer. This doesn't affect current security, but it motivates the transition to post-quantum cryptography.

Next Steps

Next up: 28-05-hash-functions-digital-signatures.md — cryptographic hashing and the flip side of public-key crypto: digital signatures.