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