Have you ever wondered how your sensitive information stays safe when you're shopping online or checking your bank balance? The answer lies in a clever mathematical trick called RSA cryptography. Today, we're going to unravel this mystery, starting from some basic math and building up to encrypting our own messages!
The Building Blocks: Euler's Totient Function and Theorem
Before we dive into RSA, we need to understand two key concepts: Euler's totient function and Euler's theorem.
Euler's Totient Function
Imagine you have a group of numbers from 1 to n. Euler's totient function, written as φ(n), counts how many of these numbers don't share any factors with n (except 1). We call these numbers "coprime" to n.
Let's look at an example:
For n = 10:
1, 3, 7, 9 are coprime to 10
So, φ(10) = 4
For prime numbers, it's even simpler. If p is prime, φ(p) = p - 1, because all numbers less than p are coprime to it.
Euler's Theorem
Now, here's where the magic happens. Euler discovered a fascinating property:
For any number M coprime to n:
M^φ(n) ≡ 1 (mod n)
In simple terms, if you multiply M by itself φ(n) times and divide by n, you'll always get a remainder of 1.
Let's see an example:
n = 9, φ(9) = 6
Choose M = 5 (coprime to 9)
5^6 = 15,625
15,625 ÷ 9 = 1,736 remainder 1
It works! This theorem is the foundation of RSA.
The RSA Insight
Here's where the creators of RSA had their brilliant idea. They realized:
1. If M^φ(n) ≡ 1 (mod n), then M^(φ(n) + 1) ≡ M (mod n)
2. We can split φ(n) + 1 into two numbers, let's call them e and d
3. If e d = k φ(n) + 1 (for some integer k), then M^(e*d) ≡ M (mod n)
This means we can raise M to the power of e, then raise the result to the power of d, and we'll get M back!
RSA in Action
Let's walk through a simple example:
1. Choose two prime numbers: p = 3, q = 11
2. Calculate n = p * q = 33
3. Calculate φ(n) = (p-1) (q-1) = 2 10 = 20
4. Choose e (coprime to 20): let's pick 3
5. Find d: 3 d ≡ 1 (mod 20), so d = 7 (because 3 7 = 21 ≡ 1 (mod 20))
Now we have:
- Public key: (n = 33, e = 3)
- Private key: (n = 33, d = 7)
Let's encrypt the message M = 5:
C = M^e mod n = 5^3 mod 33 = 125 mod 33 = 26
To decrypt:
M = C^d mod n = 26^7 mod 33 = 8,031,810,176 mod 33 = 5
We got our original message back!
Encrypting a String
To encrypt a string, we convert each character to a number (like its ASCII value) and encrypt each number separately. Here's a simple example:
Message: "HI"
H = 72, I = 73
Encrypt:
72^3 mod 33 = 6
73^3 mod 33 = 31
Our encrypted message is (6, 31)
Decrypt:
6^7 mod 33 = 72
31^7 mod 33 = 73
Convert back to letters: 72 = H, 73 = I
We've recovered our original message "HI"!
Wrapping Up
The public key (n, e) is shared openly and used for encryption. The private key (n, d) is kept secret and used for decryption. The security of RSA relies on the fact that it's very hard to figure out φ(n) if you only know n, especially when n is the product of two very large primes.
And there you have it! From Euler's insights to encrypting messages, you now understand the basics of RSA cryptography. Next time you make a secure online transaction, you'll know the mathematical magic happening behind the scenes!