Question

Suppose your RSA public-key factors are p  = 6323 and q  = 2833, and the public exponent e  is 31. Suppose you were sent the Ciphertext 6627708. Write a program that takes the above parameters as input and implements the RSA Decryption function to recover the plaintext. Use C or C++ programming language.

Answer 1

#include <iostream>

#include <math.h>

using namespace std;

// find gcd

int gcd(int a, int b)

{

int t;

while (1)

{

t = a % b;

if (t == 0)

return b;

a = b;

b = t;

}

}

//calculates the value of d

long int cd(long long x,long long phi)

{

long long k = 1;

while (1)

{

k = k + phi;

if (k % x == 0)

return (k / x);

}

}

//this method returns (x^y)%p

int power(long long x, unsigned long long y, long long p)

{

long long res = 1; // Initialize result

x = x % p; // Update x if it is more than or

// equal to p

if (x == 0) return 0; // In case x is divisible by p;

while (y > 0)

{

// If y is odd, multiply x with result

if (y & 1)

res = (res*x) % p;

// y must be even now

y = y>>1; // y = y/2

x = (x*x) % p;

}

return res;

}

int main()

{

//2 random prime numbers

long long p = 6323;

long long q = 2833;

long long n = p * q; //calculate n

long long track;

long long phi = (p - 1) * (q - 1); //calculate phi

//public key

//e stands for encrypt

long long e = 31;

//for checking that 1 < e < phi(n) and gcd(e, phi(n)) = 1; i.e., e and phi(n) are coprime.

while (e < phi)

{

track = gcd(e, phi);

if (track == 1)

break;

else

e++;

}

//private key

long long d = cd(e,phi);

long long c = 6627708;

long long m = power(c,d,n);

cout<<"p "<<p<<endl;

cout<<"q "<<q<<endl;

cout<<"n "<<n<<endl;

cout<<"phi "<<phi<<endl;

cout<<"e "<<e<<endl;

cout<<"d "<<d<<endl;

cout<<"Cipher "<<c<<endl;

cout<<"Decrypted "<<m<<endl;

return 0;

}