Unlocking RSA: How & Why It Really Works 🔐 (No Experience Needed)

In this video, I am going to show you why RSA encryption works. I will prove the correctness of RSA from scratch, so no prior knowledge will be required. All results from number theory needed to understand why RSA works will be proven along the way.

00:00 1. Introduction, outline and disclaimer

02:08 2. Recap: How RSA works
02:12 2.1. Key generation
04:49 2.2. Why RSA is secure
05:56 2.3. Encryption/decryption

07:41 3. Crash course: Modular arithmetic
09:05 3.1. Modular Multiplication
12:05 3.2. Modular Division
16:00 3.3. What numbers can we divide by?
17:17 3.4. Bezout's identity

18:48 4. Proof of Bézout's identity
19:26 4.1. "smallest positive linear combination" ≥ gcd
20:54 4.2. "smallest positive linear combination" ≤ gcd
23:36 4.3. Why did we do this again?

24:25 5. Euclid's lemma + proof

27:44 6. Fermat's little theorem + proof
28:52 6.1. The first p - 1 multiples of "a" yield 1, 2, …, p - 1 exactly once each
32:56 6.2 Multiplying multiples

36:19 7. RSA: Proof of correctnesss
38:17 7.1. Modulo p
38:36 7.1.1. "gcd(m, p) = p" case
39:15 7.1.2. "gcd(m, p) = 1" case
42:25 7.2. Modulo q
42:40 7.3. Bringing it all together