Back to Clrs

31.7

C31-Number-Theoretic-Algorithms/31.7.md

latest625 B
Original Source

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.