RSA Encryption
RSA (Rivest-Shamir-Adleman, 1977) is the most famous public-key cryptosystem. It combines all the math we've learned: primes, modular arithmetic, Euler's totient, and modular exponentiation.
The Big Idea: Anyone can encrypt with your public key, but only you can decrypt with your private key. Security relies on the difficulty of factoring large numbers.
Key Generation
Generate an RSA key pair from two prime numbers:
Enter two primes to generate keys...
The RSA Algorithm
Encryption
c = m^e mod n
Anyone with the public key (e, n) can encrypt.
Decryption
m = c^d mod n
Only the private key holder (d, n) can decrypt.
Encrypt & Decrypt
Encrypt
Generate keys first...
Decrypt
Generate keys first...
Why RSA Works
The magic comes from Euler's theorem! Here's why decryption recovers the original message:
- We choose d such that e × d ≡ 1 (mod φ(n))
- This means e × d = 1 + k × φ(n) for some integer k
- Decryption: c^d = (m^e)^d = m^(e×d) = m^(1 + k×φ(n))
- By Euler's theorem: m^φ(n) ≡ 1 (mod n)
- So: m^(1 + k×φ(n)) = m × (m^φ(n))^k ≡ m × 1^k = m (mod n)
Security: The Factoring Challenge
RSA security relies on the difficulty of factoring n. Try to "break" RSA by factoring:
Enter n to attempt factoring...
Note: These small numbers are easy to factor. Real RSA uses 2048-bit primes (617 digits), making factoring computationally infeasible.
Real-World RSA
| Key Size | n has... digits | Status |
|---|---|---|
| 512-bit | ~155 | Broken (1999) |
| 1024-bit | ~309 | Deprecated |
| 2048-bit | ~617 | Standard today |
| 4096-bit | ~1234 | High security |