Question

Write public and private key where p = 13, q = 37 and n = 481. Totient is 432. E is 19 and d is 91. Write public key as (n = , e =) and private key as (n = , d =)

Answer 1

We proceed step by step, to verify all given information.

• p = 13, q = 37

• Thus, totient function (n) = (p - 1) * (q - 1) = 12 * 36 = 432
  • Thus, totient function is as expected.

• We need to chose e < n, so that GCD (e, n) = 1
  • e = 19 and n = 481 are relatively coprime, as GCD (19, 481) = 1. So, value of e is as expected.

• Also, d should be chosen, so that when (e * d) is divided by totient function, the remainder is 1.
  • e * d = 19 * 91 = 1729
  • Also, 1729 = 1728 + 1 = (432 * 4) + 1 = (n) + 1
  • So, d is also fine.

Thus, the keys are

• public key = (n, e) = (481, 19)
• private key = (n, d) = (481, 91)