Question

Choose two prime numbers p and q (these are your inputs). Suppose that you need to send a message to your friend, and you implement the RSA algorithm for secure key generation. You need public and private keys (these are your outputs). You are free to choose other parameters or inputs if you need any. Write a program for the RSA algorithm using any programing language you know (such as C++) to generate your public and private key.

Answer 1

Answer:

#include <iostream>

#include<math.h>

using namespace std;

int findGcd(int x, int y) {

int t;

while(1) {

t= x%y;

if(t==0)

return y;

x = y;

y= t;

}

}

int main() {

int v1,v2,p,q,flag = 0;

cout<<"Please enter 1st prime number: ";

cin>>p;

v1 = p/2;

cout<<"Please enter 2nd prime number: ";

cin>>q;

v2 = q/2;

for(int i = 2; i <= v1; i++)

{

if(p%i == 0)

{

cout<<"The number is not prime";

flag = 1;

return 0 ;

}

}

for(int i = 2; i <= v1; i++)

{

if(q%i == 0)

{

cout<<"You entered a number which is not prime";

flag = 1;

return 0;

}

}

double n=p*q;

double tr;

double phi= (p-1)*(q-1);

double e=7;

if( flag == 0)

{

while(e<phi) {

tr = findGcd(e,phi);

if(tr==1)

break;

else

e++;

}

cout<<"public key: "<<e<<endl;

double d1=1/e;

double d=fmod(d1,phi);

cout<<"private key: "<<d<<endl;

double message;

cout<<"please enter a message: ";

cin>>message;

double cipher = pow(message,e);

double m = pow(cipher,d);

cipher = fmod(cipher,n);

m = fmod(m,n);

cout<<"Encrypted message: "<<cipher;

}

}

Explanation:

• Find n = p*q and calculate phi = (p-1) * (q-1).
• Select a number e such that 1 < e < phi(n) and findGcd(e, phi(n)) = 1.
• Find d which is private key  as d = e−1 (mod phi(n)).
• As m is original message so encrypt using, cipher = m*e mod n.