Public-Key Cryptography
Every time you visit an HTTPS website, your browser negotiates a secret key with a server it has never spoken to before — over a completely open network. That should feel impossible. Public-key cryptography is why it is not. This module explains the idea from first principles: why symmetric encryption alone fails at scale, how asymmetric keypairs solve the problem, and what attacks remain.
The key-distribution problem
Symmetric encryption (AES, for example) is fast and strong, but it requires both parties to share the same secret key before they can communicate. If you want to talk privately to 1,000 strangers, you need 1,000 separate keys, each delivered securely somehow. On the open internet there is no prior secure channel — so how do you ever get that first key across?
This is the key-distribution problem. It was the central unsolved challenge in cryptography until 1976.
The asymmetric keypair model
Public-key (asymmetric) cryptography breaks the symmetry. Instead of one shared secret, each party generates a keypair:
- Public key (pk) — published openly; anyone can see it.
- Private key (sk) — kept secret by its owner; never transmitted.
The defining property is that knowing pk and the encryption algorithm gives you no practical way to recover sk. The mathematical relationship between them is a one-way function: easy to compute in one direction, computationally infeasible to reverse without special knowledge (the private key).
Two usage directions
| Goal | Who holds the key used | Operation |
|---|---|---|
| Confidentiality (send a secret message to Bob) | Alice uses Bob's public key to encrypt | Only Bob, who has sk, can decrypt |
| Authenticity (prove a message came from Alice) | Alice uses her own private key to sign | Anyone with Alice's pk can verify |
The formal correctness condition for encryption is:
Dec_sk( Enc_pk( m ) ) = m
Hard-problem foundations
All practical public-key systems reduce security to a mathematical problem believed to be computationally intractable:
| Algorithm | Hard problem | Typical use |
|---|---|---|
| RSA | Factoring a large composite n = p * q into its prime factors |
Encryption, digital signatures |
| Diffie-Hellman / ElGamal | Discrete logarithm: given g, p, and g^x mod p, find x |
Key exchange, encryption |
Both problems are easy to check but hard to invert. RSA (Rivest, Shamir, Adleman, 1978 — 2002 Turing Award) is the most widely deployed public-key algorithm and has withstood decades of cryptanalysis.
Diffie-Hellman key exchange
Diffie and Hellman's 1976 paper "New Directions in Cryptography" (IEEE Trans. Information Theory) introduced the first practical solution to the key-distribution problem and the concept of a public-key cryptosystem. Diffie and Hellman received the 2015 ACM Turing Award for this work.
The goal: Alice and Bob want to agree on a shared secret over an insecure channel so they can then use it as a symmetric key (e.g. for AES). An eavesdropper can see everything they send but still cannot learn the secret.
The paint-mixing analogy: Imagine both parties start with a publicly known paint color (yellow). Each mixes in their own secret color (Alice: orange; Bob: teal). They exchange the resulting mixtures publicly. Each then mixes the other's public mixture with their own secret color, arriving at the same final color. A passive observer sees only the public colors; separating a paint mixture is assumed to be hard.
The actual protocol uses modular exponentiation. Alice and Bob first agree publicly on:
p— a large prime (e.g. 2048 bits)g— a small prime generator (e.g. 2 or 3)
Then:
Alice Bob
────────────────────────────────────────────────────
Pick secret integer x Pick secret integer y
Send A = g^x mod p ──────────────►
◄───────────── Send B = g^y mod p
Compute K = B^x mod p Compute K = A^y mod p
= g^xy mod p = g^xy mod p
Both sides arrive at the same K = g^xy mod p. An eavesdropper sees g, p, A = g^x mod p, and B = g^y mod p, but recovering x from g^x mod p is the discrete logarithm problem — believed to be computationally infeasible for large p.
Worked example (toy numbers, p = 23, g = 5):
Alice chooses a = 4: A = 5^4 mod 23 = 4 (sent to Bob)
Bob chooses b = 3: B = 5^3 mod 23 = 10 (sent to Alice)
Alice: s = B^a mod 23 = 10^4 mod 23 = 18
Bob: s = A^b mod 23 = 4^3 mod 23 = 18 ✓ shared secret = 18
The shared key used by symmetric encryption is typically k = hash(s).
The man-in-the-middle (MITM) problem
Diffie-Hellman solves eavesdropping, but not impersonation. An active attacker, Mallory, who sits on the network can intercept and replace the public values:
Alice ── g^a ──► Mallory ── g^v ──► Bob
Alice ◄── g^u ── Mallory ◄── g^b ── Bob
Alice now shares key g^au with Mallory; Bob shares key g^bv with Mallory. Each believes they are talking to the other. Mallory can read and modify every message. DH gives you a secure channel but not identity assurance: you don't know who is on the other end.
Defenses against MITM:
- Out-of-band verification (e.g. compare a fingerprint over the phone).
- Combine DH with user authentication (password, existing session credential).
- Use digital signatures — the real-world solution that leads to PKI.
Hybrid encryption
Pure public-key encryption (e.g. RSA) is several orders of magnitude slower than AES. The practical solution used in every real protocol (TLS, PGP, SSH) is hybrid encryption:
- Use public-key crypto to exchange a fresh symmetric key (the "session key").
- Use that session key with a fast symmetric cipher (AES) to bulk-encrypt the actual data.
The public-key step solves key distribution; the symmetric step gives performance.
Digital signatures (conceptual overview)
A digital signature provides authenticity and non-repudiation. The signer uses their private key to produce a signature over a message (or its hash); anyone with the corresponding public key can verify it — but only the holder of the private key could have produced it.
This is the reverse of confidentiality encryption:
| Operation | Key used | Anyone can… |
|---|---|---|
| Sign | Sender's private key | Verify with sender's public key |
| Encrypt | Receiver's public key | Only receiver decrypts |
Combining encryption and signatures gives both confidentiality and authenticity.
Why this all motivates PKI
Digital signatures solve the MITM problem for DH — but only if you can trust the public key you received actually belongs to who you think. Mallory could publish her own public key and claim it is Bob's. This is the key authenticity problem and it motivates the Public Key Infrastructure (PKI): a hierarchy of trusted Certificate Authorities (CAs) that sign public keys, binding them to verified identities. Your browser's padlock relies on exactly this chain of trust.
Key takeaways
- Symmetric encryption requires a pre-shared secret; the key-distribution problem asks how to establish that secret over an insecure channel.
- Public-key (asymmetric) crypto uses a public/private keypair: encrypt with the public key, decrypt with the private key; sign with the private key, verify with the public key.
- Security rests on hard problems: factoring (RSA) and the discrete logarithm (Diffie-Hellman, ElGamal).
- Diffie-Hellman key exchange (1976) lets two parties agree on a shared secret over a public channel — the first practical solution to key distribution.
- DH is vulnerable to MITM attacks: the protocol provides confidentiality against eavesdroppers but not identity assurance. Defense requires authentication, typically via digital signatures.
- Hybrid encryption combines public-key for key exchange with AES for bulk data — the architecture used by TLS, SSH, and PGP.
- Digital signatures (private key signs, public key verifies) provide authenticity and non-repudiation, and motivate PKI as the solution to the key-authenticity problem.