rsa.rar_RSA算法_rsa

///////////////////////////////////////////////////////////////////////////// // 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: " <