22. Cryptography: Encryption

What this lecture covers

Following the previous lecture on hash functions, this lecture turns to encryption itself: how two parties encrypt and decrypt messages, and how they agree on a secret key in the first place. It moves from symmetric key encryption (a single shared secret) through the Diffie-Hellman key exchange protocol, into asymmetric (public-key) encryption and a full derivation of why RSA works. It closes by asking a deeper question: why RSA's security assumption, factoring, has held up for decades while public-key schemes built on other NP-complete problems, like knapsack, were quickly broken.

This is the second of two cryptography lectures in the course. After watching, you should be able to explain the difference between symmetric and asymmetric encryption, walk through the Diffie-Hellman key exchange and why it's vulnerable to a man-in-the-middle attack, derive why RSA encryption and decryption recover the original message, and explain why worst-case hardness (as in NP-completeness) is not the same as the average-case hardness cryptography actually needs.

Key ideas

• Symmetric key encryption: both parties share one secret key K; encryption and decryption (E(K,M) and D(K,C)) are often nearly identical operations built from reversible steps like permutation, addition/negation, and XOR (as in AES).
• Key exchange problem: symmetric encryption requires a secure way to share K first; the lecture illustrates this with a "pirate puzzle" solved by locking a box twice, in both orders, and unlocking one lock at a time - which requires the locks to commute.
• Diffie-Hellman key exchange: the mathematical analog of the pirate puzzle, using g^a mod p and g^b mod p; security rests on the discrete logarithm problem and the Diffie-Hellman problem both being computationally hard.
• Man-in-the-middle attack: Diffie-Hellman alone doesn't authenticate who you're exchanging keys with; an adversary can substitute their own exponent and intercept the "secure" channel unless public keys are certified by a trusted authority.
• Public-key (asymmetric) encryption: each party has a public key and a private key; anyone can encrypt with the public key, but only the holder of the private key can decrypt, and knowing the public key should not reveal the private key.
• RSA: built from two large secret primes p, q, with N = pq public along with an encryption exponent e; the decryption exponent d satisfies ed = 1 mod (p-1)(q-1), and Fermat's little theorem is used to prove M^(ed) = M mod N.
• RSA's hardness assumptions: factoring N into p and q must be hard, and recovering M from C = M^e mod N without the private key (the "RSA problem") must be hard.
• Average-case vs. worst-case hardness: NP-complete problems like three-colorability and knapsack are hard in the worst case but easy on average (e.g. a random large graph almost always contains an easy-to-spot four-clique), which is why crypto systems built directly on them were broken, while factoring stays hard on average for large numbers.

Walkthrough

Symmetric key encryption (3:04)

The lecture defines symmetric key encryption: a shared secret key K, plaintext M, ciphertext C = E(K,M), and decryption M = D(K,C). Unlike the one-way hash functions from the previous lecture, encryption must be reversible, so it's built from reversible primitives - permutation, XOR, and modular addition - which is roughly how AES works. The open question this raises is how Alice and Bob can share K securely in the first place.

The pirate puzzle and Diffie-Hellman key exchange (12:12)

The lecture poses a puzzle: Alice and Bob want to exchange a secret using boxes and padlocks carried by curious but non-destructive pirates who will steal any visible key but deliver any locked box. The solution - Alice locks the box and sends it, Bob adds his own lock and sends it back, Alice removes her lock and sends it again, then Bob removes his lock and reads the message - requires the two locks to commute, which rules out simply nesting one lock inside another. This maps directly onto Diffie-Hellman key exchange, where Alice and Bob each pick a secret exponent, exchange g^a mod p and g^b mod p, and each compute the same shared key g^(ab) mod p, relying on exponentiation's commutativity and the hardness of the discrete logarithm problem.

The man-in-the-middle attack (30:34)

The lecture identifies the protocol's weak point: nothing authenticates who is actually on the other end. An adversary who can generate their own exponent can intercept and substitute values in both directions, ending up sharing a key separately with Alice and with Bob while each thinks they're talking to the other. The fix requires authenticated, certified public keys (via a trusted authority) rather than Diffie-Hellman alone.

Public-key encryption and RSA setup (36:39)

The lecture formalizes public-key encryption: a message plus a recipient's public key produces ciphertext, and only the recipient's private key can recover the message, with the requirement that the public key reveal nothing about the private key. RSA's key generation is walked through step by step: Alice picks two large secret primes p and q, computes N = pq, chooses a small public encryption exponent e relatively prime to (p-1)(q-1), and derives the private decryption exponent d via the extended Euclidean algorithm so that ed = 1 mod (p-1)(q-1).

Proving RSA works (48:53)

Using Fermat's little theorem (M^(p-1) = 1 mod p for prime p), the lecture proves that encryption followed by decryption, M^(ed) mod N, recovers the original message M, handling the two cases where M is or isn't a multiple of p, then combining the results for p and q via the Chinese remainder-style argument to get the result mod N. It then states RSA's two hardness assumptions: factoring N into p and q must be hard, and recovering M from a given ciphertext without the private key (the RSA problem) must be hard.

Why average-case hardness matters (1:07:07)

The lecture closes by comparing factoring to other NP-complete problems like graph three-colorability and knapsack, both of which were tried as a basis for public-key crypto systems and broken. The key insight is that NP-completeness only guarantees worst-case hardness: a large random graph is almost always trivially provable as non-three-colorable by spotting a small clique, and early knapsack-based cryptosystems (like Merkle-Hellman, which disguises an easy "super-increasing" knapsack as a hard one) were broken because the disguised problem turned out to be easy on average. Factoring large numbers, by contrast, has remained hard in the average case, which is why RSA has survived for decades while those alternatives did not.

Before you watch

• Watch the previous lecture on cryptographic hash functions, since this one builds directly on the public/private key vocabulary and security mindset introduced there.
• Review modular arithmetic and the extended Euclidean algorithm, both used throughout the RSA derivation.
• Basic familiarity with NP-completeness from earlier in the course helps with the closing discussion of worst-case versus average-case hardness.

Check your understanding

1. Why must the two locks in the pirate puzzle commute, and what does this correspond to mathematically in Diffie-Hellman key exchange?
2. How can an adversary carry out a man-in-the-middle attack against plain Diffie-Hellman key exchange, and what stops it?
3. Walk through why M^(ed) mod N equals M in RSA, using Fermat's little theorem.
4. Why were knapsack-based public-key cryptosystems broken even though the general knapsack problem is NP-complete?