Question

Use C++

forehand e receiver creates a public key and a secret key as follows. Generate two distinct primes, p andq. Since they can be used to generate the secret key, they must be kept hidden. Let n-pg, phi(n) ((p-1)*(q-1) Select an integer e such that gcd(e, (p-100g-1))-1. The public key is the pair (e,n). This should be distributed widely. Compute d such that d-l(mod (p-1)(q-1). This can be done using the pulverizer. The secret key is the pair (d.n). This should be kept hidden Encoding: iven a messagem, the sender first checks thatgcd(m,n)-1.The sender then encrypts message m to produce m using the public key: ing: receiver decrypts message m' back to message m using the secret key: mrem(m'Y.n) Develop an application that will implement the RSA cryptosystem. Inputs: 1. Two prime numbers: p andg 2. The message to be encrypted (this is an integer): m Required features:+ 1. An independentmethod that could be used to compute gcdof two numbers using the Euclidean algorithm: geda,b)=gcd(b, rem(a,b))- 2. Ability to find the values of two integers s and tSuch that gcd(a,b) = sa +tb . This should be implemented as an independent method. This method is the Pulverizer or the Extended Euclidean algorithm 3. Compute the public and private keys. You need to think about an intelligent way to utilize the routines that you have developed in Step 1 and Step 2. 4. Perform encryption and decryption. 5. The application should print the encrypted message on the output screen and should also verify that decryption actually reproduce the original message 6. Your application should NOT be using any built in libraries. 7. Use the (%) operator to compute the remainder,d 8. You may compute rem a.b) using successive squaring as explained in an example on page 107 of the textbook. For example, all the congruences below hold modulo 17- 62 362 2 615-8-64-62-6-16-42-#23

Answer 1

Answer is as follwos :

The code in C++ :

#include <iostream>
#include<cmath>

using namespace std;
int gcd(int a, int h)
{
int temp;
while (1)
{
temp = a%h;
if (temp == 0)
return h;
a = h;
h = temp;
}
}
int main()
{
// Two random prime numbers
int p ;
int q ;
cout << "Enter p and q ";
cin >> p >> q ;

// First part of public key:
int n = p*q;

// Finding other part of public key.
// e stands for encrypt
int e = 2;
int phi = (p-1)*(q-1);
while (e < phi)
{
// e must be co-prime to phi and
// smaller than phi.
if (gcd(e, phi)==1)
break;
else
e++;
}

// Private key (d stands for decrypt)
// choosing d such that it satisfies
// d*e = 1 + k * totient
int k = 2; // A constant value
int d = (1 + (k*phi))/e;

// Message to be encrypted
int msg;
cout << "Enter Message : " ;
cin >> msg ;
  

// Encryption c = (msg ^ e) % n
int c = pow(msg, e);
c = fmod(c, n);
cout << "\nEncrypted data :" << c;

// Decryption m = (c ^ d) % n
int m = pow(c, d);
m = fmod(m, n);
cout << "\nDecrypted data :" << m;

return 0;
}

Output Screenshot :

Enter p and q 3 7 Enter Message 12 Encrypted data :3 Decrypted data :12

if there is any query please ask in comments...