RSA Example with Small Primes
What you'll learn: You'll work through a complete RSA encryption and decryption cycle using small prime numbers to see every step in action.
The Complete Picture
Now that you understand each piece of RSA individually, let's walk through a full example from start to finish. We'll use tiny primes so you can follow every calculation without a calculator obscuring the logic.
Step-by-Step RSA Example
Setup Phase:
Let's choose primes p = 11 and q = 13.
- Compute
n = p × q = 11 × 13 = 143 - Compute
φ(n) = (p-1)(q-1) = 10 × 12 = 120 - Choose public exponent
e = 7(must be coprime to 120) - Find private exponent
dwheree × d ≡ 1 (mod 120)- Using the Extended Euclidean Algorithm:
d = 103 - Verify:
7 × 103 = 721 = 6 × 120 + 1✓
- Using the Extended Euclidean Algorithm:
Public key: (e=7, n=143)
Private key: (d=103, n=143)
Encryption and Decryption
Suppose our message is M = 5.
Encrypt: C = M^e mod n = 5^7 mod 143
5^7 = 78,12578,125 mod 143 = 47- Ciphertext:
C = 47
Decrypt: M = C^d mod n = 47^103 mod 143
- Using repeated squaring to compute this efficiently
- Result:
M = 5(our original message!) ✓
The magic is that raising to the e-th power scrambles the message in a way only the d-th power (known only to you) can unscramble, thanks to Euler's Theorem guaranteeing M^(ed) ≡ M (mod n).
Key Takeaway: RSA with small primes demonstrates the complete encrypt-decrypt cycle: choose primes, compute moduli and exponents, encrypt with the public key, and recover the original message with the private key—all mechanics you can verify by hand.