Asymmetric Encryption

Asymmetric encryption, also called public-key cryptography, uses a pair of mathematically related keys: a public key and a private key. It solves the fundamental problem of symmetric encryption — how to share a secret key securely.

---

The Key Distribution Problem

With symmetric encryption, both parties need the same key. But how do you share that key securely?

• Send it by email? — can be intercepted
• Share it in person? — impractical at scale
• Use another encryption key? — who shares that one?

Whitfield Diffie and Martin Hellman solved this problem in 1976 by inventing public-key cryptography, one of the most important breakthroughs in the history of information security.

---

How Asymmetric Encryption Works

Each user generates a key pair:

Key	Properties
Public key	Shared openly with anyone
Private key	Kept secret — never shared

Encryption

Sender:    Plaintext ──▶ [Encrypt with Recipient's PUBLIC key] ──▶ Ciphertext
Receiver:  Ciphertext ──▶ [Decrypt with Recipient's PRIVATE key] ──▶ Plaintext

Only the recipient's private key can decrypt data encrypted with their public key.

Digital Signatures (Preview)

Signer:    Message ──▶ [Sign with Signer's PRIVATE key] ──▶ Signature
Verifier:  Signature ──▶ [Verify with Signer's PUBLIC key] ──▶ Valid/Invalid

Only the signer's private key can produce the signature; anyone with the public key can verify it.

---

Diffie-Hellman Key Exchange

Diffie-Hellman (DH) allows two parties to agree on a shared secret over an insecure channel without transmitting the secret itself.

The Process (Simplified)

1. Alice and Bob agree on public parameters: a large prime p and a generator g
2. Alice chooses a secret a, computes A = g^a mod p, and sends A to Bob
3. Bob chooses a secret b, computes B = g^b mod p, and sends B to Alice
4. Alice computes the shared secret: s = B^a mod p
5. Bob computes the shared secret: s = A^b mod p
6. Both arrive at the same shared secret without ever transmitting it

Alice                          Bob
  │                              │
  │  Public: p, g                │
  │─────────────────────────────▶│
  │                              │
  │  secret a                    │  secret b
  │  A = g^a mod p               │  B = g^b mod p
  │                              │
  │  ◀─────── A ───────▶         │
  │  ◀─────── B ───────▶         │
  │                              │
  │  s = B^a mod p               │  s = A^b mod p
  │  (same shared secret)        │  (same shared secret)

Security basis: The discrete logarithm problem — it is computationally infeasible to derive the private exponent from the public value.

Ephemeral Diffie-Hellman (DHE / ECDHE)

• Generates a new key pair for every session
• Provides forward secrecy: if a long-term private key is compromised, past sessions remain secure
• ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) is the modern standard, used in TLS 1.3

---

RSA (Rivest-Shamir-Adleman)

RSA, published in 1977, was the first practical public-key encryption algorithm:

Key Generation

1. Choose two large prime numbers p and q
2. Compute n = p × q (the modulus)
3. Compute φ(n) = (p-1)(q-1) (Euler's totient)
4. Choose a public exponent e (commonly 65537)
5. Compute the private exponent d such that e × d ≡ 1 (mod φ(n))
6. Public key = (n, e), Private key = (n, d)

Encryption and Decryption

Encryption:  c = m^e mod n    (using public key)
Decryption:  m = c^d mod n    (using private key)

RSA Security