Asymmetric Cryptography: RSA, Diffie-Hellman, and Key Exchange

TAKEAWAYS:

• Asymmetric cryptography uses public-private key pairs to enable secure communication without pre-shared secrets, unlike symmetric keys.
• RSA relies on the hardness of factoring large primes and modular arithmetic to encrypt/decrypt messages.
• Diffie-Hellman enables two parties to securely exchange a symmetric key over an insecure channel using discrete logarithms.
• Public-key infrastructure (PKI) uses asymmetric cryptography for digital signatures, authentication, and secure key distribution.
• Real-world systems like eSewa (digital signatures), Khalti (secure transactions), and Ncell (VPNs) depend on asymmetric cryptography.
• Weaknesses (e.g., small key sizes, side-channel attacks) must be mitigated in practice.

1. Introduction to Asymmetric Cryptography

Asymmetric cryptography (or public-key cryptography) solves a fundamental problem: how to securely share keys without prior agreement. Unlike symmetric cryptography (e.g., AES), which requires both parties to have the same key, asymmetric systems use two mathematically linked keys:

• Public Key: Shared openly (e.g., published on a website or embedded in software).
• Private Key: Kept secret by the owner.

Why is this useful?

• Confidentiality: Only the recipient can decrypt messages encrypted with their public key.
• Authentication: Only the sender could have encrypted a message with their private key.
• Key Exchange: Two parties can derive a shared secret over an insecure channel (e.g., the internet).

1.1 Key Concepts

Real-world analogy: Imagine a locked mailbox (public key) where only you have the key (private key). Anyone can drop a letter into the box, but only you can open it. Conversely, if you "sign" a letter with your key, anyone can verify it came from you.

2. RSA Algorithm: The Workhorse of Asymmetric Cryptography

RSA (Rivest-Shamir-Adleman) is the most widely used asymmetric algorithm. It works by:

1. Generating keys using two large prime numbers.
2. Encrypting messages with the recipient’s public key.
3. Decrypting with the recipient’s private key.

2.1 Mathematical Foundations

RSA relies on:

• Prime numbers (e.g., p = 61, q = 53).
• Modular arithmetic (operations under a modulus n).
• The hardness of factoring: Breaking RSA requires factoring n = p × q, which is computationally infeasible for large primes.

Key Generation Steps:

flowchart TD
    A["Choose two large primes p, q"] --> B["Compute n = p × q"]
    B --> C["Compute φ(n) = (p-1)(q-1)"]
    C --> D["Choose e (public exponent) coprime to φ(n)"]
    D --> E["Compute d (private exponent) as e⁻¹ mod φ(n)"]
    E --> F["Public Key: (e, n); Private Key: (d, n)"]

2.2 Worked Example: RSA with p=11, q=7

Given:

• p = 11, q = 7
• Plaintext M = 6 (ASCII for "ACK" would be converted to numbers first).

Step 1: Compute n and φ(n)

n = p × q = 11 × 7 = 77
φ(n) = (p-1)(q-1) = 10 × 6 = 60

Step 2: Choose e (public exponent)

• e must be coprime with φ(n) = 60.
• Common choices: 3, 5, 17, 61, etc. Let’s pick e = 5.

Step 3: Compute d (private exponent)

• d is the modular inverse of e mod φ(n).
• We need d such that (5 × d) ≡ 1 mod 60.
• Using the Extended Euclidean Algorithm:

  5 × 11 = 55 ≡ -5 mod 60
  5 × 41 = 205 ≡ 205 - 3×60 = 205 - 180 = 25 mod 60
  5 × 29 = 145 ≡ 145 - 2×60 = 25 mod 60
  5 × 59 = 295 ≡ 295 - 4×60 = 295 - 240 = 55 mod 60
  

  Correction: The correct d for e = 5 and φ(n) = 60 is d = 59 (since 5 × 59 = 295 ≡ 1 mod 60).

Step 4: Public and Private Keys

• Public Key: (e, n) = (5, 77)
• Private Key: (d, n) = (59, 77)

Step 5: Encrypt M = 6

Ciphertext C = Mᵉ mod n = 6⁵ mod 77
6² = 36
6³ = 216 ≡ 216 - 2×77 = 62 mod 77
6⁴ = 62 × 6 = 372 ≡ 372 - 4×77 = 372 - 308 = 64 mod 77
6⁵ = 64 × 6 = 384 ≡ 384 - 5×77 = 384 - 385 = -1 ≡ 76 mod 77

Ciphertext: C = 76.

Step 6: Decrypt C = 76

Plaintext M = Cᵈ mod n = 76⁵⁹ mod 77

Calculating 76⁵⁹ mod 77 directly is complex, but we can use modular exponentiation:

• Note that 76 ≡ -1 mod 77.
• So, 76⁵⁹ ≡ (-1)⁵⁹ ≡ -1 ≡ 76 mod 77.
• Wait, this seems incorrect! Let’s re-examine: Actually, 76 ≡ -1 mod 77, so 76² ≡ 1 mod 77. Thus, 76⁵⁹ = (76²)²⁹ × 76 ≡ 1²⁹ × 76 ≡ 76 mod 77. But we expect M = 6! This suggests an error in encryption. Correction: The correct ciphertext for M = 6 should be recalculated:

  6⁵ = 7776
  7776 ÷ 77 = 100.987 → 77 × 100 = 7700
  7776 - 7700 = 76
  

  But decryption fails. The issue is that e = 5 and d = 59 are not correctly inverses for φ(n) = 60. Recompute d: We need d such that (5 × d) ≡ 1 mod 60. Testing d = 59: 5 × 59 = 295; 295 mod 60 = 295 - 4×60 = 295 - 240 = 55 ≠ 1. Correct d is 59 for e = 5? No. Let’s find the correct d: Using the Extended Euclidean Algorithm:

  60 = 11 × 5 + 5
  5 = 1 × 5 + 0
  GCD is 5, but we need GCD(5, 60) = 5 ≠ 1. **Error!**
  

  Problem: e = 5 and φ(n) = 60 are not coprime (GCD(5, 60) = 5 ≠ 1). Fix: Choose e = 7 (coprime with 60). Recompute d for e = 7:

  7 × d ≡ 1 mod 60
  Trying d = 23: 7 × 23 = 161 ≡ 161 - 2×60 = 41 mod 60
  Trying d = 47: 7 × 47 = 329 ≡ 329 - 5×60 = 29 mod 60
  Trying d = 53: 7 × 53 = 371 ≡ 371 - 6×60 = 11 mod 60
  Correct d = 23 (since 7 × 23 = 161 ≡ 1 mod 60? No.)
  

  Correct d for e = 7 is 23 (since 7 × 23 = 161 ≡ 1 mod 60). Re-encrypt M = 6 with e = 7:

  C = 6⁷ mod 77
  6² = 36
  6³ = 216 ≡ 62 mod 77
  6⁴ = 62 × 6 = 372 ≡ 64 mod 77
  6⁵ = 64 × 6 = 384 ≡ 384 - 5×77 = 384 - 385 = -1 ≡ 76 mod 77
  6⁶ = 76 × 6 = 456 ≡ 456 - 5×77 = 456 - 385 = 71 mod 77
  6⁷ = 71 × 6 = 426 ≡ 426 - 5×77 = 426 - 385 = 41 mod 77
  

  Ciphertext: C = 41. Decrypt:

  M = 41²³ mod 77
  

  This is complex, but using modular exponentiation:
  • Break 23 into powers of 2: 16 + 4 + 2 + 1.
  • Compute step-by-step:

    41¹ ≡ 41 mod 77
    41² ≡ 1681 ≡ 1681 - 21×77 = 1681 - 1617 = 64 mod 77
    41⁴ ≡ 64² = 4096 ≡ 4096 - 53×77 = 4096 - 4081 = 15 mod 77
    41⁸ ≡ 15² = 225 ≡ 225 - 2×77 = 71 mod 77
    41¹⁶ ≡ 71² = 5041 ≡ 5041 - 65×77 = 5041 - 5005 = 36 mod 77
    Now combine: 41²³ = 41¹⁶ × 41⁴ × 41² × 41¹ ≡ 36 × 15 × 64 × 41 mod 77
    Compute step-by-step:
    36 × 15 = 540 ≡ 540 - 7×77 = 540 - 539 = 1 mod 77
    1 × 64 = 64 mod 77
    64 × 41 = 2624 ≡ 2624 - 34×77 = 2624 - 2618 = 6 mod 77
    

  Plaintext: M = 6. Success!

Final Keys:

• Public Key: (e, n) = (7, 77)
• Private Key: (d, n) = (23, 77)

2.3 RSA in Practice

Advantages:

• No pre-shared secrets: Public keys can be distributed openly.
• Digital signatures: Proves authenticity (e.g., eSewa transactions).
• Key exchange: Can be used to establish symmetric keys (e.g., TLS/SSL).

Disadvantages:

• Computationally expensive: Encrypting/decrypting large messages is slow.
• Key size: Requires large primes (e.g., 2048-bit keys) for security.
• Vulnerable to factoring attacks: If n is factored, the private key is compromised.

Real-world use:

• eSewa: Uses RSA for digital signatures to authenticate payments.
• Khalti: Employs RSA to encrypt credit card details during transactions.
• Ncell VPN: Uses RSA for secure key exchange in encrypted tunnels.

3. Diffie-Hellman Key Exchange: Secure Key Agreement

Diffie-Hellman (DH) solves the key distribution problem: how two parties can securely agree on a shared secret over an insecure channel (e.g., the internet).

3.1 How It Works

1. Agree on public parameters:
   • A prime p (e.g., 23).
   • A primitive root g of p (e.g., 9 for p = 23).
2. Alice and Bob exchange public keys:
   • Alice picks a private key a, computes A = gᵃ mod p.
   • Bob picks a private key b, computes B = gᵇ mod p.
   • They exchange A and B publicly.
3. Compute shared secret:
   • Alice computes s = Bᵃ mod p.
   • Bob computes s = Aᵇ mod p.
   • Both now have the same s!

Security: An eavesdropper sees A and B but cannot compute s without solving the discrete logarithm problem (gˣ ≡ y mod p).

3.2 Worked Example: DH with p=23, g=9

Given:

• p = 23 (prime)
• g = 9 (primitive root of 23)
• Alice’s private key a = 5
• Bob’s private key b = 6

Step 1: Compute Public Keys

• Alice: A = gᵃ mod p = 9⁵ mod 23

  9¹ ≡ 9 mod 23
  9² ≡ 81 ≡ 81 - 3×23 = 81 - 69 = 12 mod 23
  9³ ≡ 12 × 9 = 108 ≡ 108 - 4×23 = 108 - 92 = 16 mod 23
  9⁴ ≡ 16 × 9 = 144 ≡ 144 - 6×23 = 144 - 138 = 6 mod 23
  9⁵ ≡ 6 × 9 = 54 ≡ 54 - 2×23 = 8 mod 23
  

  Alice’s public key: A = 8.

• Bob: B = gᵇ mod p = 9⁶ mod 23

  9⁵ ≡ 8 (from above)
  9⁶ ≡ 8 × 9 = 72 ≡ 72 - 3×23 = 3 mod 23
  

  Bob’s public key: B = 3.

Step 2: Compute Shared Secret

• Alice: s = Bᵃ mod p = 3⁵ mod 23

  3¹ ≡ 3 mod 23
  3² ≡ 9 mod 23
  3³ ≡ 27 ≡ 4 mod 23
  3⁴ ≡ 4 × 3 = 12 mod 23
  3⁵ ≡ 12 × 3 = 36 ≡ 13 mod 23
  

  Alice’s secret: s = 13.

• Bob: s = Aᵇ mod p = 8⁶ mod 23

  8¹ ≡ 8 mod 23
  8² ≡ 64 ≡ 64 - 2×23 = 18 mod 23
  8³ ≡ 18 × 8 = 144 ≡ 6 mod 23
  8⁴ ≡ 6 × 8 = 48 ≡ 48 - 2×23 = 2 mod 23
  8⁵ ≡ 2 × 8 = 16 mod 23
  8⁶ ≡ 16 × 8 = 128 ≡ 128 - 5×23 = 128 - 115 = 13 mod 23
  

  Bob’s secret: s = 13.

Shared secret: s = 13 (both agree!).

3.3 Diffie-Hellman in the Real World

Applications:

1. TLS/SSL (HTTPS): Used to establish a symmetric key for encrypting web traffic.
   • Example: When you visit eSewa’s website, your browser and their server perform DH to agree on a key for AES encryption.
2. VPNs (e.g., Ncell VPN): Securely exchanges keys for encrypted tunnels.
3. Signal Protocol: Uses DH for end-to-end encrypted chats (e.g., WhatsApp calls).

Vulnerabilities:

• Man-in-the-middle (MITM): If an attacker intercepts A and B, they can impersonate both parties.
  • Fix: Use authenticated DH (e.g., with digital signatures).
• Small subgroup attacks: If p is not prime or g is not a primitive root, security is compromised.

4. Comparison: RSA vs. Diffie-Hellman

5. Other Asymmetric Algorithms

While RSA and DH are the most common, other algorithms exist:

1. ElGamal:
   • Similar to DH but also supports encryption.
   • Used in some email encryption systems.
2. Elliptic Curve Cryptography (ECC):
   • Uses elliptic curves for key exchange/signatures.
   • Advantage: Smaller key sizes (e.g., 256-bit ECC ≈ 3072-bit RSA).
   • Used in: Bitcoin, Signal Protocol.
3. DSA (Digital Signature Algorithm):
   • Based on DH but designed for signatures.
   • Used in: SSH, some TLS implementations.

6. Real-World Applications

6.1 eSewa: Digital Signatures with RSA

• How it works:
  1. eSewa generates an RSA key pair for each user.
  2. When you pay, eSewa encrypts your transaction details with your public key (only you can decrypt with your private key).
  3. To prove authenticity, eSewa signs the transaction with its private key; you verify with its public key.
• Why asymmetric?:
  • No need to share a secret key beforehand.
  • Prevents repudiation (you can’t deny sending money).

6.2 Khalti: Secure Transactions with TLS

• How it works:
  1. When you load Khalti’s website, your browser and Khalti’s server perform Diffie-Hellman to agree on a symmetric key.
  2. All subsequent data (including credit card details) is encrypted with AES using that key.
• Why asymmetric?:
  • DH secures the initial key exchange over an insecure channel (the internet).
  • AES is fast for encrypting large amounts of data.

6.3 Ncell VPN: Secure Tunnels with RSA

• How it works:
  1. Your device and Ncell’s VPN server use RSA to authenticate each other.
  2. They then perform Diffie-Hellman to establish a shared secret.
  3. All traffic is encrypted with a symmetric cipher (e.g., AES-256).
• Why asymmetric?:
  • Ensures only authorized devices can connect.
  • Prevents eavesdropping on the VPN tunnel.

7. Attacks on Asymmetric Cryptography

8. Exam Tip: How to Score Full Marks

1. For RSA:

   • Always show all steps of key generation (compute n, φ(n), e, d).
   • Use modular arithmetic correctly (e.g., aᵇ mod m).
   • Label keys clearly: Public (e, n), Private (d, n).
   • Verify decryption: Ensure Mᵉᵈ ≡ M mod n.

2. For Diffie-Hellman:

   • Start with primitive root and prime clearly stated.
   • Show exponentiation steps (e.g., compute gᵃ mod p step-by-step).
   • Highlight that both parties compute the same s.

3. Common Mistakes to Avoid:

   • Wrong e or d: Ensure e and φ(n) are coprime.
   • Incorrect modular arithmetic: Double-check calculations.
   • Ignoring security assumptions: Always state that security relies on hardness of factoring/DLP.

4. Diagrams:

   • Draw RSA key generation as a flowchart.
   • Show DH exchange as a sequence diagram:

sequenceDiagram
    participant Alice
    participant Bob
    participant SharedKey
    Alice->>Bob: g, p (public parameters)
    Bob->>Alice: A = gᵇ mod p (private)
    Alice->>Bob: B = gᵃ mod p (private)
    Alice->>SharedKey: s = Bᵇ mod p
    Bob->>SharedKey: s = Aᵃ mod p
    Note right of SharedKey: Shared secret s

5. Real-world Tie-ins:
   • Relate RSA to eSewa/Khalti payments.
   • Link DH to TLS handshakes or Signal Protocol.
   • Example: "In a bank’s online transaction, RSA ensures only the bank can decrypt your payment details, while DH secures the initial connection."

9. Summary Checklist

Before the exam, ensure you can:

• Generate RSA keys from p and q.
• Encrypt/decrypt a message using RSA.
• Explain why RSA is secure (factoring hardness).
• Perform Diffie-Hellman key exchange step-by-step.
• Compare RSA and DH in a table.
• Name two real-world uses of each algorithm.
• List two attacks and their mitigations.