/////////////////////////////////////////////////////////////////////////////
// File: rsa.C
// Contents: See below.
// Written originally by Myron Kennedy, Fall 1995,
// Modified in Spring 1997 by Ron Hannebohn
// Please read the rsa.README file for the list of revisions and other
// comments.
/*****************************************************************************
* originally written by *
* Myron Kennedy *
* modified by Ron Hannebohn and B. Stephens *
* for students in CMSC443 - *
* Bignum RSA scheme *
* because of patent restrictions this program *
* should only be used for 443 projects *
*****************************************************************************
* *
* This program implements interactive RSA tools. It supports a *
* menu structure that allows a user to generate probabilistic primes, *
* compute N as the product of two probabilistic primes; factor a number; *
* compute phi(N); randomly generate an encryption exponent; find an *
* inverse in a mod system; display N, phi(N), the encryption exponent, *
* and the decryption exponent; and perform exponentiation in a mod *
* system. *
* *
* *
* To compile: g++ -o rsa rsa.C -lg++ *
* To run: rsa *
* *
*****************************************************************************/
#include "Integer.h"
#include <stdlib.h>
#include <ctype.h>
#include <iostream.h>
#include <time.h>
#include <math.h>
#include "rsa.H"
main()
{
char answer[MAX_ANSWER_LENGTH];
Integer i, num, factor1 = 1, factor2 = 1, phi, m, e, d, exp, fastexp,
n1, n2, number = 0, a, n, jacobi, result, count, temp;
Integer primes[750];
int is_continue = 1, factored = 0, choice, invalid, current_prime_count = 0;
int ii,j;
int numtests;
int test;
n = 0;
num = 0;
phi = 0;
e = 0, d = 0;
numtests = 12;
// Generate an initial list of primes between 1 and 5000. This is for if
// the user immediately decides to find phi, or generate an encryption
// exponent, or some other operation requiring the prime list, without
// first generating the primes.
cout << "Please wait while initial list of primes is generated...." << endl;
n = 3;
for (i = n; i <= (n + 5000); i = i + 2)
{
a = (Integer) (random() % (i - 1));
if (gcd(a, n) == 1)
{
if (current_prime_count >= MAX_SIZE)
break;
test = 0;
for (ii=1;ii<=numtests;ii++)
{
jacobi = Jacobi(a, i);
result = FastExp(a, (i - 1)/2, i);
if (jacobi == result)
test = 1;
else
test = 0;
a = (Integer) (random() % (i - 1));
}
if (test == 1)
primes[current_prime_count++] = i;
}
}
while(is_continue)
{
PrintMenu();
cout << "Please select one operation: ";
cin >> answer;
choice = atoi(answer);
switch (choice)
{
case GENERATE_PRIMES: // generate some probabilistic primes
cout << endl << endl;
cout << " Enter a number and probabilistic primes will be " << endl;
cout << " generated in the interval (number < p < number + 5000)";
cout << endl << " where p would be a prime:";
cout << endl << endl << " Enter number: ";
n = GetPositiveInt("Enter number: ");
cout << endl << " Probabilistic primes between " << n << " and ";
cout << (n + 5000) << endl;
current_prime_count = 0;
srandom(time(NULL));
count = 0;
if (n % 2 == 0) /* be sure to start with an odd number */
n = n - 1;
if (n == 1)
n = 3;
// To determine if the number is prime, for each candidate generate
// one random number in the mod of the candidate, and if this random
// number passes the Jacobi test numtest times, it is assumed to be
// prime. numtests now set to 8.
for (i = n; i <= (n + 5000); i = i + 2)
{
test = 0;
a = (Integer) (random() % (i - 1));
if (current_prime_count >= MAX_SIZE)
break;
for (ii=1;ii<=numtests;ii++)
{
jacobi = Jacobi(a, i);
result = FastExp(a, (i - 1)/2, i);
if (jacobi == result)
test = 1;
else
test = 0;
a = (Integer) (random() % (i - 1));
}
if (test == 1)
{
if (current_prime_count >= MAX_SIZE)
break;
primes[current_prime_count++] = i;
if (count % 8 == 0)
cout << endl << "\t";
cout << " " << i;
count = count + 1;
}
}
cout << endl;
factored = 1;
break;
case DISPLAY_PRIMES:
DisplayPrimeList(primes, current_prime_count);
cout << endl;
break;
case COMPUTE_N_AS_PPROD: // compose a number with only 2 prime factors.
count = 1;
while(1)
{
cout << endl << " Enter the 1st prime number: ";
n1 = GetPositiveInt("Enter the 1st prime number: ");
cout << " Enter the 2nd prime number: ";
n2 = GetPositiveInt("Enter the 2nd prime number: ");
// if (n1 == n2 ||
// !InPrimeList(n1, primes, current_prime_count) ||
// !InPrimeList(n2, primes, current_prime_count))
// {
// cout << "Numbers equal or not in the current primes list." << endl;
// count = count + 1;
// if (count % 3 == 0)
// DisplayPrimeList(primes, current_prime_count);
// continue;
// }
// else
break;
}
number = n1 * n2;
cout << endl << " The number you computed is: " << endl;
cout << " " << number << endl;
e = d = phi = 0;
break;
case TRIAL_DIV_FACTORING: // perform trial division factoring
cout << endl << "Enter a positive integer to see if it is prime: ";
num = GetPositiveInt("Enter positive integer to see if it is prime: ");
cout << " Trial division factors of " << num << ":" << endl << endl;
Factor(num, factor1, factor2);
factored = 1;
break;
case POLLARD_FACTOR: /* perform Pollard Rho factoring */
cout << endl << "Enter a positive integer to see if it is prime: ";
num = GetPositiveInt("Enter positive integer to see if its prime: ");
cout << " Pollard's factors of " << num << ":" << endl;
cout << endl;
PollardRho(num, factor1, factor2);
factor1 = factor2 = 1;
factored = 1;
break;
case PHI: /* compute phi(n) */
phi = GetPhi(factor1, factor2, primes, current_prime_count);
number = factor1 * factor2;
factor1 = factor2 = 1;
e = d = 0;
break;
case RANDOM_E: /* generate encryption exponent */
if (phi == 0)
{
cout << endl << " Phi(N) has not been computed." << endl;
phi = GetPhi(factor1, factor2, primes, current_prime_count);
number = factor1 * factor2;
factor1 = factor2 = 1;
}
invalid = 1;
srandom(time(NULL));
while (invalid)
{
e = (Integer)(random() % phi);
// Automatically calculate d by taking e's inverse.
d = Inverse(phi, e);
if (gcd(e, phi) == 1 && e != d)
{
cout << endl;
cout << "\t Encryption exponent is: " << e << endl;
cout << "\t Decryption exponent (e's-inverse) is: " <
评论0