Question

Write a C++ program that involves implementing the RSA cryptosystem. In practice for the encryption to be secure and to handle larger messages you would need to utilize a class for large integers. However, for this assignment you can use built-in types to store integers, e.g., unsigned long long int. Also, rather than using the ASCII table for this assignment use BEARCATII, which restricts the characters to the blank character and the lower-case letters of the alphabet as follows: blank character is assigned the value 0. A, …, Z are assigned the values 1, …, 26, respectively. The message M will be represented by replacing each character in the message with its assigned integer base 27. For example, the message M = “TEST” will be represented as N = 20 5 19 20 Translating this to decimal we obtain: D = 20 + 19*27 + 5*272 + 20*273 = 397838 Note that to convert back to base 27, we simply apply the algorithm we discussed in class, i.e., the least significant digit (rightmost) is obtained by performing the operations D mod 27 and performing a recursive call with D/27. For the example above we obtain, 397838 / 27, 397838 mod 27 = 14734, 20 → 14734 / 27, 14734 mod 27, 20 = 545, 19, 20 → 545/27, 545 mod 20, 19, 20 = 20, 5, 19, 20 = N Find primes p and q by choosing positive integers at random and testing for primality using Miller-Rabin probabilistic algorithm. Your program should prompt the user to input a positive integer representing the public key e. If the user enters a number that is not relatively prime to n = pq, then have the user reenter and keep doing this until e and n are coprime, i.e., gcd(e,φ(n)) = 1. Also prompt the user to enter the message M (as a character string). For handing purposes, run your program with M = “TEST”. Output p, q, n, M, C, P where C is the encrypted message, i.e., cyber text, and P is the decrypted message, i.e., plaintext. If your program is working correctly then M should be equal to P.

Answer 1

RSA is an asymmetric cryptography algorithm which works on two keys-public key and private key.

Algorithms
Begin
1. Choose two prime numbers p and q.
2. Compute n = p*q.
3. Calculate phi = (p-1) * (q-1).
4. Choose an integer e such that 1 < e < phi(n) and gcd(e, phi(n)) = 1; i.e., e and phi(n) are coprime.
5. Calculate d as d ≡ e−1 (mod phi(n)); here, d is the modular multiplicative inverse of e modulo phi(n).
6. For encryption, c = me mod n, where m = original message.
7. For decryption, m = c d mod n.
End

#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;
   }
}
int main() {
   //2 random prime numbers
   double p = 13;
   double q = 11;
   double n=p*q;//calculate n
   double track;
   double phi= (p-1)*(q-1);//calculate phi
   //public key
   //e stands for encrypt
   double e=7;
   //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
   //d stands for decrypt
   //choosing d such that it satisfies d*e = 1 mod phi
   double d1=1/e;
   double d=fmod(d1,phi);
   double message = 9;
   double c = pow(message,e); //encrypt the message
   double m = pow(c,d);
   c=fmod(c,n);
   m=fmod(m,n);
   cout<<"Original Message = "<<message;
   cout<<"\n"<<"p = "<<p;
   cout<<"\n"<<"q = "<<q;
   cout<<"\n"<<"n = pq = "<<n;
   cout<<"\n"<<"phi = "<<phi;
   cout<<"\n"<<"e = "<<e;
   cout<<"\n"<<"d = "<<d;
   cout<<"\n"<<"Encrypted message = "<<c;
   cout<<"\n"<<"Decrypted message = "<<m;
   return 0;
}


Output
p = 13
q = 11
n = pq = 143
phi = 120
e = 7
d = 0.142857
Original Message = 9

Encrypted message = 48
Decrypted message = 9