RSA Cryptography Foundations

Number Theory · Axiom Academy

REAL WORLD RSA Cryptography Foundations How ancient number theory powers modern internet security Every Second, Billions of Secrets Right now, as you read this, billions of encrypted messages are flying across the internet: bank transactions, private messages, password logins, medical records. All of this relies on a mathematical trick discovered by mathematicians studying pure number theory centuries ago. The encryption system protecting most of this data is called RSA (named after Rivest, Shamir, and Adleman who invented it in 1977). But the mathematics behind it goes back to Fermat in the 1600s and Euler in the 1700s. The central question: How can you create a lock that everyone can see and use, but only you can open? RSA works with a brilliant asymmetry: there's a public key (that anyone can use to encrypt) and a private key (that only you can use to decrypt). Let's see a simple example with small numbers. Anyone can use this to encrypt Only you know this for decrypting We chose two prime numbers: p = 3 and q = 11 Then: n = p × q = 3 × 11 = 33 The encryption and decryption formulas are beautifully symmetric: Where m is the message (as a number), c is the encrypted ciphertext, and all arithmetic is done modulo n . Let's encrypt and decrypt a simple message: m = 4 Let's compute: 31 7 = 27,512,614,111 27,512,614,111 ÷ 33 = 833,715,579 remainder 4 Result: We got our original message back! m = 4 Why does this work? What guarantees that m ed ≡ m (mod n)?

This is the written version of the interactive lesson above. See the full Number Theory course.