Generate a private and public key for RSA encryption using t

Generate a private and public key for RSA encryption using two distinct prime numbers between 20 and 100.

Solution

Following are the steps of RSA Algorithm-

1. n = pq, where p and q are distinct primes.
2. phi, = (p-1)(q-1)
3. e < n such that gcd(e, phi)=1
4. d = e^-1 mod phi.
5. c = m^e mod n, 1<m<n.
6. m = c^d mod n.

Example-

1. suppose two primes are p=23 and q=41

2. n=pq=23*41=943
phi=(p-1)(q-1)=22*40=880

3. choose e=7
check gcd(e,(p-1))=gcd(7,22)=1
check gcd(e,(q-1))=gcd(7,40)=1
therefore gcd(e,phi)=gcd(7,880)=1

4. compute d = e^-1 mod phi = 7^-1 mod 880 = 503
therefore d = 503

5. Public key (n,e) = (943,7)
  Private key (n,d) = (943,503)