Asymmetric Encryption & RSA: The Key Exchange Problem Solved (Part 3)

Share:

The Problem That Changed Everything

rsa asymmetric-encryption public-key diffie-hellman ecc

The Problem That Changed Everything

In Part 2, we mastered Symmetric Encryption—fast, secure AES protecting the world’s data. But we ended with a question that kept cryptographers awake at night for decades:

How do two people who have never met agree on a secret key over an insecure channel?

If Alice wants to send Bob an encrypted message, they need to share a key first. But if Alice sends the key over the internet, Eve (the eavesdropper) intercepts it. Now Eve has the key and can read everything.

This is the Key Distribution Problem, and in 1976, Whitfield Diffie and Martin Hellman solved it. Their solution—Public Key Cryptography—is arguably the most important invention in the history of secure communication.

---

The Breakthrough: Asymmetric Cryptography

The core insight is revolutionary: what if we use two different keys?

• Public Key: Shared openly with the world. Anyone can use it to encrypt a message for you.
• Private Key: Kept absolutely secret. Only you can use it to decrypt messages.

The Padlock Analogy

Imagine Bob has a special padlock:

1. Bob makes thousands of copies of the open padlock and distributes them everywhere (Public Key).
2. Bob keeps the only key that can open these padlocks (Private Key).
3. Alice finds one of Bob’s open padlocks, puts her message in a box, and clicks it shut.
4. Only Bob can open the box because only he has the key.

Eve can intercept the locked box, but without Bob’s private key, she cannot open it.

---

RSA: The First Practical Algorithm

One year after Diffie-Hellman’s theoretical breakthrough, Ron Rivest, Adi Shamir, and Leonard Adleman created RSA—the first practical public-key encryption algorithm. It remains widely used today (though ECC is gaining ground).

How RSA Works

RSA is built on a simple mathematical fact: multiplication is easy, but factoring is hard.

• Easy: What is 61 × 53? (Answer: 3233)
• Hard: What two primes multiply to give 3233?

For small numbers, both are trivial. But when the numbers have 2048 bits (over 600 digits), factoring becomes computationally infeasible.

The RSA Process

Key Generation

1. Choose two large random prime numbers: $p$ and $q$
2. Compute $n = p \times q$ (the modulus)
3. Compute $\phi(n) = (p-1)(q-1)$ (Euler’s totient)
4. Choose $e$ such that $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$ (commonly 65537)
5. Compute $d$ such that $d \times e \equiv 1 \pmod{\phi(n)}$ (modular inverse)

Public Key: $(n, e)$ Private Key: $(n, d)$

Encryption

To encrypt message $m$: \(c = m^e \mod n\)

Decryption

To decrypt ciphertext $c$: \(m = c^d \mod n\)

Why Is This Secure?

An attacker knows $n$ and $e$ (public). To find $d$, they need $\phi(n)$. To find $\phi(n)$, they need to factor $n$ into $p$ and $q$. With 2048-bit keys, this would take billions of years on current hardware.

---

Diffie-Hellman Key Exchange

While RSA can encrypt data directly, Diffie-Hellman (DH) takes a different approach. It allows two parties to agree on a shared secret over a public channel—without actually sending the secret.

The Color Mixing Analogy

1. Alice and Bob publicly agree on a starting color: Yellow.
2. Alice secretly picks Red. Bob secretly picks Blue.
3. Alice mixes Yellow + Red = Orange. Sends Orange to Bob.
4. Bob mixes Yellow + Blue = Green. Sends Green to Alice.
5. Alice takes Green and adds her secret Red = Brown.
6. Bob takes Orange and adds his secret Blue = Brown.

Both end up with Brown, but Eve only saw Yellow, Orange, and Green. Without knowing the secret colors, she cannot derive Brown.

The Math

1. Agree on public values: prime $p$ and generator $g$
2. Alice picks secret $a$, computes $A = g^a \mod p$, sends $A$
3. Bob picks secret $b$, computes $B = g^b \mod p$, sends $B$
4. Alice computes: $s = B^a \mod p$
5. Bob computes: $s = A^b \mod p$

Both get the same $s$ because: \(B^a = (g^b)^a = g^{ab} = (g^a)^b = A^b\)

This shared secret $s$ is then used as the key for symmetric encryption (AES).

---

Elliptic Curve Cryptography (ECC)

RSA keys need to be massive (2048-4096 bits) to be secure. ECC achieves equivalent security with much smaller keys (256-384 bits).

Why Does This Matter?

• Faster computations
• Less bandwidth
• Better for mobile devices and IoT
• Perfect for TLS/HTTPS handshakes

The Math (Simplified)

ECC operates on points on an elliptic curve defined by: \(y^2 = x^3 + ax + b\)

The “hard problem” is the Elliptic Curve Discrete Logarithm Problem (ECDLP). Given points $P$ and $Q = kP$ (where $k$ is a scalar and $kP$ means adding $P$ to itself $k$ times), finding $k$ is computationally infeasible.

Real-World Usage

• ECDH: Elliptic Curve Diffie-Hellman (key exchange)
• ECDSA: Elliptic Curve Digital Signature Algorithm (used in Bitcoin, TLS)
• Ed25519: Modern signing algorithm (used in SSH, Signal)

---

The Hybrid Approach: How TLS Works

In practice, we never use asymmetric encryption for bulk data—it’s too slow. Instead, we combine both:

1. Handshake Phase (Asymmetric):
   • Client and server use ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) to agree on a session key.
   • Server proves identity with RSA/ECDSA signature.
2. Data Transfer Phase (Symmetric):
   • All actual data is encrypted with AES-GCM using the agreed session key.

This gives us the best of both worlds: secure key exchange AND fast bulk encryption.

---

Security Considerations

Key Size Matters

Algorithm	Security Level	Recommended Minimum
RSA	2048-bit	3072-bit for 2030+
DH	2048-bit	3072-bit for 2030+
ECC	256-bit	384-bit for high security
AES	128-bit	256-bit for long-term

The Quantum Threat

Quantum computers running Shor’s Algorithm can break RSA, DH, and ECC in polynomial time. When (not if) large-scale quantum computers arrive:

• RSA: Broken
• ECC: Broken
• AES-256: Reduced to AES-128 equivalent (still secure)

This is why we’re racing to develop Post-Quantum Cryptography, which we’ll explore later in this series.

---

Summary

We’ve conquered the key distribution problem:

• RSA: Encrypt directly with public key, decrypt with private key.
• Diffie-Hellman: Agree on a shared secret without ever sending it.
• ECC: Same security, smaller keys, faster operations.

Next Part: We’ll dive into Hashing & Message Authentication Codes (MACs)—how we ensure data hasn’t been tampered with.

Discussion