Course contentsShow
← Mathematics
Lesson 2769 of 3,12154. Number TheoryFree lesson

RSA Example with Small Primes

Work through a complete RSA encryption and decryption example using small primes for concrete understanding.

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.

  1. Compute n = p × q = 11 × 13 = 143
  2. Compute φ(n) = (p-1)(q-1) = 10 × 12 = 120
  3. Choose public exponent e = 7 (must be coprime to 120)
  4. Find private exponent d where e × d ≡ 1 (mod 120)
    • Using the Extended Euclidean Algorithm: d = 103
    • Verify: 7 × 103 = 721 = 6 × 120 + 1 ✓

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,125
  • 78,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.