Full Detailed RSA Numerical Example

(Exactly the way examiners expect you to write in the exam — step-by-step, every calculation shown)

Question:
Perform complete RSA cryptosystem setup and show encryption & decryption for the following:
Choose two prime numbers p = 11 and q = 17.
Select e = 7.
Message (plaintext) M = 25.
Show all steps clearly.

Answer (Write like this in exam → 15–18 marks guaranteed)

Step 1: Select two prime numbers
p = 11, q = 17 (both prime ✓)

Step 2: Compute n = p × q
n = 11 × 17 = 187
∴ n = 187

Step 3: Compute Euler’s totient function φ(n)
φ(n) = (p − 1)(q − 1) = (11 − 1)(17 − 1) = 10 × 16 = 160
∴ φ(n) = 160

Step 4: Choose public exponent e
Given e = 7
Check: gcd(e, φ(n)) = gcd(7, 160)
7 is prime, 160 = 2⁵ × 5 → no common factors → gcd(7, 160) = 1 ✓
So e = 7 is valid.

Public key = (e, n) = (7, 187)

Step 5: Compute private exponent d
We need d such that:
e × d ≡ 1 (mod φ(n))
⇒ 7d ≡ 1 (mod 160)
⇒ Find multiplicative inverse of 7 modulo 160

Use Extended Euclidean Algorithm:

Now back-substitute to express 1 as combination:

1 = 7 − 1×6
But 6 = 160 − 22×7
∴ 1 = 7 − 1×(160 − 22×7)
= 7 − 160 + 22×7
= 23×7 − 160
∴ 23×7 − 1×160 = 1
⇒ 7×23 ≡ 1 (mod 160)
∴ d = 23

Private key = d = 23
(Private key pair is (d, n) = (23, 187))

Step 6: Encryption (Sender side)
Plaintext message M = 25
Ciphertext c = M^e mod n
c = 25⁷ mod 187

Compute 25⁷ mod 187 using Successive Squaring (Binary Exponentiation):

25¹ = 25
25² = 625 ≡ 625 − 3×187 = 625 − 561 = 64
25⁴ = (25²)² = 64² = 4096 ≡ 4096 − 21×187 = 4096 − 3927 = 169
25⁶ = 25⁴ × 25² = 169 × 64
169 × 64 = 10816
10816 ÷ 187 ≈ 57.8 → 57×187 = 10659
10816 − 10659 = 157 → 25⁶ ≡ 157
25⁷ = 25⁶ × 25 = 157 × 25 = 3925
3925 ÷ 187 ≈ 21 exactly → 21×187 = 3927
3925 − 3927 = -2 → add 187 → -2 + 187 = 185
∴ 25⁷ ≡ 185 mod 187

Ciphertext c = 185

Step 7: Decryption (Receiver side)
Plaintext recovered = c^d mod n
= 185²³ mod 187

Again use successive squaring (write only main steps in exam):

First compute powers of 185 mod 187
Note: 185 ≡ −2 mod 187 (because 187 − 2 = 185) → easier!

So 185²³ ≡ (−2)²³ mod 187 = − 2²³ mod 187
(negative at end because 23 is odd)

Now compute 2²³ mod 187:

2¹ = 2
2² = 4
2⁴ = 16
2⁸ = 256 ≡ 256 − 187 = 69
2¹⁶ = 69² = 4761 ≡ 4761 − 25×187 = 4761 − 4675 = 86

Now 2²³ = 2¹⁶ × 2⁴ × 2² × 2¹ = 86 × 16 × 4 × 2

86 × 16 = 1376 → 1376 − 7×187 = 1376 − 1309 = 67
67 × 4 = 268 → 268 − 1×187 = 81
81 × 2 = 162

∴ 2²³ ≡ 162 mod 187
⇒ (−2)²³ ≡ −162 ≡ 187 − 162 = 25 mod 187

Recovered plaintext = 25 ✓

Final Result Summary (Write this table at the end):

Verification using formula:
Check: e × d = 7 × 23 = 161 = 160 + 1 = 1 × φ(n) + 1 → satisfies ed ≡ 1 (mod φ(n)) ✓

This is a 100% complete, exam-perfect RSA numerical — copy this format and you will get full marks in any university exam! 🚀