Question

Consider an RSA system with p = 7109 and q = 7919. Generate a public and private key pair based on the given p and q. Show the STEPS

Answer 1

Given:

p = 7109 and q = 7919

Public and Private keys can be find using belwo steps:

• Find Derived Number (e)

  • Number e must be greater than 1 and less than (p − 1)(q − 1).

  • There must be no common factor for e and (p − 1)(q − 1) except for 1. In other words two numbers e and (p – 1)(q – 1) are coprime.

Let n = p * q = 7109 * 7919 = 56,296,171

Let m = (p-1) * (q-1) = 56,281,144

now, e = 3

• Form the public key

  • The pair of numbers (n, e) form the RSA public key and is made public.

  • public key = (56296171 , 3)

• Generate the private key

  • Private Key d is calculated from p, q, and e. For given n and e, there is unique number d.

  • Number d is the inverse of e modulo (p - 1)(q – 1). This means that d is the number less than (p - 1)(q - 1) such that when multiplied by e, it is equal to 1 modulo (p - 1)(q - 1).

  • This relationship is written mathematically as follows −

ed = 1 mod (p − 1)(q − 1)