Assignment Objectives

Practice implementing an RSA key generation algorithm based on the explanation of RSA

Assignment Summary

In this assignment, you will finish the implementation of a program in C++ that generates an RSA public key and a private key pair given two positive prime numbers on the command line. Assignment Directions

A program usage message should appear on the screen, and the program should exit.Finish the implementation of the generateKeys() function, whose prototype is shown below and whose stubbed-out function definition is in the Name3.cpp file. This function is called from the main() function in the program3-driver.cpp file.

void generateKeys(int primeA, int primeB, int &encryptionExponent, int &decryptionExponent)

In doing the implementation of the generateKeys() function, you may also want to implement these three private (i.e., static) helper functions:

int relativelyPrime(int number) Purpose: Computes a value Y that is relatively prime to X Called by: generateKeys() function

int gcd(int numberV, int numberW) Purpose: Computes the greatest common divisor of V and W Called by: relativelyPrime() function

int inverse(int numberX, int modulusN) Purpose: Computes the multiplicative inverse of x mod N Called by: generateKeys() function

Note that your implementation of these functions should not prompt the user for any information nor should they directly produce any screen output. In addition, your implementation should not use the value 1 as a relatively prime number. In other words, it should start with the value 2 as the first possible value to check.

When you run the program, be sure to check the test case results displayed on the screen to help you in testing your key generation code. The sample-run.txt file shows sample command line input and program output.

Large Numbers and a Finite Implementation

To generate an RSA public and private key pair, we need to choose two "large" prime numbers for p and q. Because the RSA algorithm produces very large numbers from a very small input, we only have a limited set of values for p and q that we can use for testing. The numbers 3 and 11 fit into that window; therefore, you can safely use them as a test case for your software.

This limited set of input values can be somewhat overcome. This is done by implementing a repeated squaring algorithm for calculating the powers of numbers modulo N. However, we are not implementing that algorithm in this assignment.

As a side note, in a language such as Haskell, the range of values for positive integers is not limited by what the computer can store; consequently, a person can use large values for p and q.

Implementation Constraints

Follow the same coding standards given in previous assignments

Except for looking up the general-purpose GCD algorithm, avoid surfing the Web to find a solution to this implementation