In: Computer Science
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
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)