please help code this in c++

____________________________

In this lab we will write a 32 bit, non-optimized version of the asymmetric public-private key encryption algorithm RSA. It is a simplified version of the algorithm that is currently being used with SSL and https. You wouldn't be able to use PayPal without it. There is high level theory behind this algorithm, and you are not required to understand all of it. Our goal is to implement the steps and get it to work.

The goal of asymmetric encryption is to allow anyone on the outside, a client, to send an encrypted message to a host, usually a web server, such that only the web server can decrypt the message. This allows the client and server to set up private communication. The public key allows any client to encrypt. No clients can decrypt. The private key is needed to decrypt, which only the server has. This makes it so only the server can decrypt the messages sent from clients requesting communication. Once the server receives and decrypts the request for communication, a symmetric encryption algorithm such as AES, where both the client and server can encrypt and decrypt, is used from then on.

The RSA algorithm is implemented as follows:

• Assume the message to be sent is an integer. For a message m, find integers e, d, and n such that:
  • ((me)d)%n=m
    • In other words, find a mod value and two exponents such that raising a number to the product of those exponents gives you the original number back
• Once those three numbers are found, asymmetric encryption is possible.
• To create an encrypted message c, also known as a cipher, use e and n:
  • c=(me)%n
• To decrypt, use d and n on the encrypted message:
  • (cd)%n=((me)d)%n=m
• Thus, the public key, which allows encryption of a message m, consists of:
  • e and n.
• The private key, which allows decryption of a cipher c, consists of:
  • d and n
• Note that since everything is being modded with n, m must be less than n in order to not wrap back around to zero
• To raise to an exponent and then mod is called modular exponentiation.
  • We will write a function for this

Functions

• Define the functions specified below in RSA.cpp
• We will put them together in main to implement the algorithm
• You should test them each individually to make sure they work before using them in main
• Use the following code for RSA.h:

#ifndef RSA_H_INCLUDED #define RSA_H_INCLUDED bool isPrime(unsigned long long n); unsigned long long getPrime(unsigned long long min, unsigned long long max); unsigned long long gcd(unsigned long long x, unsigned long long y); unsigned long long lcm(unsigned long long x, unsigned long long y); unsigned long long modInverse(unsigned long long e, unsigned long long lam); unsigned long long modExp(unsigned long long base,unsigned long long exp,unsigned long long n); #endif // RSA_H_INCLUDED

• Note that we are using unsigned long long instead of int. This is to prevent overflowing since we will be working with large numbers.
  • Just replace pretty much every occurrence of int in your code with unsigned long long to be safe, otherwise your algorithm might mysteriously not work due to overflows (this happened to me)
• isPrime
  • Return true if n is prime, false otherwise.
• getPrime
  • Return a random prime number in the range of [min...max]
  • Use rand(). There is a section in Zybooks for brushing up on this.
  • Use a loop:
    • Generate a random number in the range
    • while it is not prime, generate a new one
  • It is important that you do not call rand() more than necessary here or your output will not match my tester
• gcd
  • Return the greatest common divisor of x and y.
  • Use the Basic Euclidean Algorithm for GCD
• lcm
  • Return the least common multiple of x and y
  • The easiest and fastest way to do this is to return (x*y) / gcd(x,y)
• modInverse
  • Modular Inverse function.
  • Given e and lam as parameters, find a number d such that:
    • (de)%lam=1
  • There are many fancy ways to do this. We will take a simple, iterative approach:
    • Use a for loop to test the above equation for every possible value of d, from 1 to lam
    • If the left side of the above equation == 1, then return d
• modExp
  • Modular exponentiation
  • The goal is to raise to a power and then mod:
    • return (baseexp)%n
  • Unfortunately, if you try to compute the above expression, the power will get ridiculously large and overflow before the mod operation is done
  • To work around this, we will multiply the base once per iteration and then mod as we go to keep the number smaller. This is tricky to visualize so I will give you the code for this one:

unsigned long long modExp(unsigned long long base, unsigned long long exp, unsigned long long n) { unsigned long long ans = 1; for(unsigned long long i = 0; i 

main

• Don't forget to #include "RSA.h" so you can use the functions declared above
• declare unsigned long long variables p, q, n, lambda, d, e, m, and c
• declare unsigned int seed
• Ask the user to enter a seed
• Call srand() ONCE to seed your RNG
• Use getPrime to assign to p a random number in the range [UCHAR_MAX...USHRT_MAX]
  • This will assign it to a prime between 255 and 65535
  • You can access those constants with #include
  • This means that p is between 8 and 16 bits in length
• Do the same for q
• Output the values of p and q
• The modulus n is obtained by multiplying the two large prime numbers, p and q
  • Assign n = p * q
  • Output the value of n
• The next steps use modular arithmetic number theory to generate the variables. We will implement the steps, but fully understanding the theory behind them is not required.
  • Assign lambda to the lcm of p - 1 and q - 1
    • Output the value of lambda
    • Lambda is a value that we will use to generate e and d
  • In the next step we will generate e
    • e must be a prime smaller than lambda that does not divide evenly into lambda
    • Call getPrime to assign to e a random prime in the range [2...lambda - 1]
    • Use a loop to ensure that lambda is not divisible by e:
      • while lambda is divisible by e (lambda % e == 0), assign to e a new random prime in the range [2...lambda - 1]
    • Output the value of e
  • assign to d the modInverse of e and lambda
    • Output the value of d
• Output the public key, which is the values of n and e
• Output the private key, which is the values of n and d
• Prompt the user to enter the plain message m, which must be a positive number less than the value of n
  • input m
• Use modExp to assign to cipher c the modular exponent (me)%n
  • This is your encrypted value, which is what a client would send to a server
  • Output the value of the cipher
• Decrypt and output the cipher c by calculating the modular exponent (cd)%n
  • You should get the original message m
  • This is what the server, having the private key d and n, would do to decrypt the client's message

Sample Execution

Enter a seed: 2019 p: 26237 q: 46573 n: 1221935801 lambda: 305465748 e: 25361081 d: 162882113 Public key: n = 1221935801 e = 25361081 Private key: n = 1221935801 d = 162882113 Enter a positive number less than 1221935801: 1337 Cipher: 1132500679 Decrypted cipher: 1337

• This output was generated from the Power Server
  • If you run your code on Windows you will likely get different random primes p, q, and e, even though the encryption should still work.
• Ensure that your code creates the same values for the seed shown above
• If your decrypted cipher matches the original message m, then congrats your encryption works!
• If your encryption / decryption is working but your random numbers are different, make sure your calls to rand() in getPrime are using the correct ranges and that you are not calling rand() or srand() more often than necessary

/0 n (baseer") % n (me) %n (*) % n /0 n (baseer") % n (me) %n (*) % n