Skip to content

07-01: Exercises

Question

Using RSA with the small primes:

  • p = 7
  • q = 13

  • Public exponent: e = 5

  • Compute the modulus n.

  • Compute Euler's totient φ(n).
  • Find a valid private exponent d such that e · d ≡ 1 (mod φ(n)).
  • Encrypt the message m = 4 using the public key (e, n).
  • Decrypt the resulting ciphertext using the private key (d, n) and confirm you recover m = 4.

Solution

Step 1: Compute n

n = p × q = 7 × 13 = 91

This n is the modulus used in both the public key (e, n) and the private key (d, n).

Step 2: Compute φ(n)

For two primes, Euler's totient is:

φ(n) = (p − 1)(q − 1) = (7 − 1)(13 − 1) = 6 × 12 = 72

Step 3: Verify e is a valid public exponent

We need e = 5 to satisfy 1 < e < φ(n) and gcd(e, φ(n)) = 1.

  • gcd(5, 72): factors of 5 are {1, 5}; 72 is not divisible by 5.
  • gcd(5, 72) = 1 ✓ valid choice.

Step 4: Find the private exponent d

We need d such that:

e · d ≡ 1 (mod φ(n)) 5 · d ≡ 1 (mod 72)

Try successive multiples of 72, adding 1, and check divisibility by 5:

k 72k + 1 ÷ 5?
1 73 no
2 145 145 / 5 = 29 ✓

So 5 · d = 145 → d = 145 / 5 = 29

Check: 5 × 29 = 145 = 2 × 72 + 1 → 145 mod 72 = 1 ✓

d = 29

Public key: (e = 5, n = 91) Private key: (d = 29, n = 91)

Step 5: Encrypt m = 4

Ciphertext formula: c = m^e mod n

c = 4^5 mod 91

Compute 4^5 step by step using repeated squaring:

  • 4^1 = 4
  • 4^2 = 16
  • 4^4 = 16^2 = 256 → 256 mod 91: 91 × 2 = 182, 256 − 182 = 74 → 4^4 mod 91 = 74
  • 4^5 = 4^4 × 4^1 = 74 × 4 = 296 → 296 mod 91: 91 × 3 = 273, 296 − 273 = 23

c = 23

Step 6: Decrypt c = 23

Plaintext recovery formula: m = c^d mod n = 23^29 mod 91

Use repeated squaring, reducing mod 91 at every step so numbers stay small:

  • 23^1 = 23
  • 23^2 = 529 → 529 mod 91: 91 × 5 = 455, 529 − 455 = 74 → 23^2 mod 91 = 74
  • 23^4 = (232)2 = 74^2 = 5476 → 5476 mod 91: 91 × 60 = 5460, 5476 − 5460 = 16 → 23^4 mod 91 = 16
  • 23^8 = (234)2 = 16^2 = 256 → 256 mod 91 = 74 (computed above) → 23^8 mod 91 = 74
  • 23^16 = (238)2 = 74^2 = 5476 → mod 91 = 16 (same as 23^4 above) → 23^16 mod 91 = 16

Now write 29 in binary to combine powers: 29 = 16 + 8 + 4 + 1

So:

23^29 = 23^16 × 23^8 × 23^4 × 23^1

Substitute the reduced values:

23^29 mod 91 = (16 × 74 × 16 × 23) mod 91

Multiply step by step, reducing mod 91 along the way:

  • 16 × 74 = 1184 → 1184 mod 91: 91 × 13 = 1183, 1184 − 1183 = 1
  • 1 × 16 = 16
  • 16 × 23 = 368 → 368 mod 91: 91 × 4 = 364, 368 − 364 = 4

m = 4 ✓ — matches the original plaintext.

Final Answer

  • n = 91
  • φ(n) = 72
  • Public key: (e = 5, n = 91)
  • Private key: (d = 29, n = 91)
  • Encryption of m = 4: ciphertext c = 23
  • Decryption of c = 23: recovered m = 4 (matches the original message, confirming the key pair works)