31.7

Exercises 31.7-1

---

Consider an RSA key set with p = 11, q = 29, n = 319, and e = 3. What value of d should be used in the secret key? What is the encryption of the message M = 100?

Answer

We follow the procedure of RSA cryptosystem.

1. n = pq = 319
2. phi(n) = (p-1)(q-1) = 280
3. For fixed e = 3, apply Euclidean algorithm to find its inverse modulo (p-1)(q-1). We find 1 = 280 - 3 x 93 and the inverse of e is -93 mod 280 = 187
4. Hence, (e, n) = (3, 319) is the public key and (d, n) = (187, 319) is the private key.
5. For M = 100, the cipher text is 100^3 mod 319 = 254.