/***************************************************************************** * * * Myron Kennedy * * CMSC443 - Dr. Stephens * * * * Bignum RSA scheme * * * ***************************************************************************** * * * This program implements an interactive RSA scheme. 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. With this program, a user could create an RSA system by * * generating large primes, then using the rest of the program to compute * * all of the necessary info. Then with a scheme to encrypt plain texts, * * the user could perform the encryption rules to encrypt, and do the * * inverse, decrypt. To solve these RSA ciphers, use the Quick RSA decrypt * * (or encrypt if you want to encrypt from a file (very fast!!) that goes * * with this program as a supplement. * * * * To compile: g++ -o executable filename.C * * To run: executable * * * *****************************************************************************/ #include #include #include #include #include #include #define MAX_ANSWER_LENGTH 1000 Integer MAX_TIME(atoIntRep("1000000000000000")); void PrintMenu(); Integer Jacobi(const Integer &, const Integer &); void Factor(const Integer &, Integer &, Integer &); void PollardRho(const Integer &, Integer &, Integer &); Integer Inverse(const Integer &, const Integer &); Integer FastExp(const Integer &, const Integer &, const Integer &); main() { char answer[MAX_ANSWER_LENGTH]; int choice; Integer i, num, factor1 = 1, factor2 = 1, phi, m, e, d, exp, fastexp, n1, n2, number, a, n, jacobi, result, count; int is_continue = 1; int factored = 0; n = 0; num = 0; phi = 0; e = 0; d = 0; while(is_continue) { PrintMenu(); cout << "Please select one operation: "; cin >> answer; choice = atoi(answer); switch (choice) { case 1: /* 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 << " "; cin >> answer; n = atoI(answer); while (n <= 0) { cout << "\t Number is negative!" << endl; cout << endl << " Enter a positive integer: "; cin >> answer; n = atoI(answer); } cout << endl; cout << " Probabilistic primes between " << n << " and "; cout << (n + 5000) << endl; srandom(time(NULL)); count = 0; if (n % 2 == 0) /* start with an odd number */ n = n - 1; if (n == 1 || n == 2) /* avoid division by zero error */ n = 3; for (i = n; i <= (n + 5000); i = i + 2) { a = (Integer) (random() % (i - 1)); if (gcd(a, n) == 1) { jacobi = Jacobi(a, i); result = FastExp(a, (i - 1)/2, i); if (jacobi == result) { if (count % 4 == 0) cout << endl << " "; cout << " " << i; count++; } } } cout << endl; factored = 1; break; case 2: /* compose a number with only 2 factors, 2 primes */ cout << endl; cout << " Enter the 1st prime number: "; cin >> answer; n1 = atoI(answer); while (n1 <= 0) { cout << "\t Number is negative!" << endl; cout << endl << " Enter the 1st prime number: "; cin >> answer; n1 = atoI(answer); } cout << " Enter the 2nd prime number: "; cin >> answer; n2 = atoI(answer); while (n2 <= 0) { cout << "\t Number is negative!" << endl; cout << endl << " Enter the 2nd prime number: "; cin >> answer; n2 = atoI(answer); } number = n1 * n2; cout << endl << " The number you computed is: " << endl; cout << " " << number << endl; break; case 3: /* perform trial division factoring */ cout << endl << "Enter a positive integer to see if it is prime: "; cin >> answer; num = atoI(answer); while (num <= 0) { cout << "\t Number is negative!\n"; cout << "\n Enter a positive integer to see if it is prime: "; cin >> answer; num = atoI(answer); } cout << " Trial division factors of " << num << ":" << endl; cout << endl; Factor(num, factor1, factor2); factored = 1; break; case 4: /* perform Pollard Rho factoring */ cout << endl << "Enter a positive integer to see if it is prime: "; cin >> answer; num = atoI(answer); while (num <= 0) { cout << "\t Number is negative!" << endl; cout << endl << "Enter a positive integer: "; cin >> answer; num = atoI(answer); } cout << " Pollard's factors of " << num << ":" << endl; cout << endl; PollardRho(num, factor1, factor2); factored = 1; break; case 5: /* compute phi(n) */ cout << endl; if ((n == 0) || (num == 0)) cout << " Need to have 2 prime numbers as factors first! " << endl; else { cout << " Enter 1st factor: "; cin >> answer; factor1 = atoI(answer); while (factor1 <= 0) { cout << "\t Number is negative!\n"; cout << "\n Enter a positive integer to see if it is prime: "; cin >> answer; factor1 = atoI(answer); } cout << endl << " Enter 2nd factor: "; cin >> answer; factor2 = atoI(answer); while (factor2 <= 0) { cout << "\t Number is negative!\n"; cout << "\n Enter a positive integer to see if it is prime: "; cin >> answer; factor2 = atoI(answer); } cout << endl << "\t Phi(N) = " << (factor1 - 1) << " * "; cout << (factor2 - 1) << " = "; phi = ((factor1 - 1) * (factor2 - 1)); cout << phi << endl; } break; case 6: /* generate encryption exponent */ if (phi == 0) cout << endl << " Compute phi(N) first!" << endl; else { int invalid = 1; srandom(time(NULL)); while (invalid) { e = (Integer)(random() % phi); if (gcd(e, phi) == 1) { cout << endl; cout << "\t Encryption exponent is: " << e << endl; invalid = 0; } } } break; case 7: /* find Inverse */ cout << endl << "Enter a positive number: "; cin >> num; cout << "Enter a positive modulus: "; cin >> m; while ((num < 0) || (m < 0)) { cout << endl << endl << "\t *** Your input was not accepted. ***"; cout << endl << "Enter a positive modulus: "; cin >> m; cout << endl << "Enter a positive number: "; cin >> num; } d = Inverse(m, num); cout << endl << endl; break; case 8: /* display data */ cout << endl; if (num == 0) cout << "\t n was not supplied as input." << endl; else cout << "\t n = " << num << endl; if (phi == 0) cout << "\t phi(n) was not computed." << endl; else cout << "\t phi(n) = " << phi << endl; if (e == 0) cout << "\t e was not computed." << endl; else cout << "\t e = " << e << endl; if (d == 0) cout << "\t d was not computed." << endl; else cout << "\t d = " << d << endl; break; case 9: /* perform fast exponentiation */ cout << endl << "Enter a positive number: "; cin >> num; cout << "Enter a positive exponent: "; cin >> exp; cout << "Enter a positive modulus: "; cin >> m; while ((num < 0) || (m < 0) || (exp < 0)) { cout << endl << endl << "\t *** Your input was not accepted. ***"; cout << endl << "Enter a positive number: "; cin >> num; cout << "Enter a positive exponent"; cin >> exp; cout << "Enter a positive modulus: "; cin >> m; } fastexp = FastExp(num, exp, m); cout << endl; cout << num << "^" << exp << " mod " << m << " = " << fastexp << endl; break; case 10: /* exit */ is_continue = 0; break; default: cout << endl << endl << "\t *** Your input was not accepted. ***"; cout << endl; break; } } cout << endl << "\t *** Thank you for using MK's RSA program! ***" << endl; } /***************************** PrintMenu *********************************** This function simply prints the header for the user menu. *****************************************************************************/ void PrintMenu() { cout << endl; cout << "\t *****************************************************" << endl; cout << "\t * *" << endl; cout << "\t * (1) Generate probabilistic primes *" << endl; cout << "\t * (2) Compute N as product of 2 primes *" << endl; cout << "\t * (3) Perform trial division factoring *" << endl; cout << "\t * (4) Find prime factors of a number (Pollard) *" << endl; cout << "\t * (5) Compute phi(N) *" << endl; cout << "\t * (6) Randomly choose encryption exponent *" << endl; cout << "\t * (7) Find an inverse in a mod system *" << endl; cout << "\t * (8) Display N, phi(N), e, and d *" << endl; cout << "\t * (9) Perform exponentiation in a mod system *" << endl; cout << "\t * (10) Exit *" << endl; cout << "\t * *" << endl; cout << "\t *****************************************************" << endl; cout << endl << endl; } /***************************** Jacobi ************************************** This function evaluates the jacobi symbol for use with the Solovay-Strassen primality test. It is a recursive definition that is implemented without knowledge of the prime factorization of its random number. ***************************************************************************/ Integer Jacobi (const Integer & rand_num, const Integer & num) { Integer d, p1, temp; if (rand_num == 1) return 1; d = gcd(rand_num, num); if (d > 1) return 0; else { if (rand_num % 2== 0) { temp = (num*num-1)/8; if (temp % 2 == 0) { p1 = rand_num/2; return Jacobi(p1,num); } else { p1 = rand_num/2; return -1*Jacobi(p1,num); } } else { temp = (rand_num - 1)*(num - 1)/4; if (temp % 2 == 0) { p1 = num % rand_num ; return Jacobi(p1,rand_num); } else { p1 = num % rand_num ; return -1*Jacobi(p1,rand_num); } } } } /****************************** Factor ************************************ This function makes an attempt at brute force factoring. It only tests odd numbers, assuming that the number that you are trying to factor is the product of 2 primes. ****************************************************************************/ void Factor (const Integer &number, Integer &f1, Integer &f2) { Integer factor_count(atoIntRep("0")); int is_true = 1; for (Integer i = 2; i <= sqrt(number); i++) { while(is_true) /* divide out by small primes to increase */ { /* speed; assume number that you are trying */ if (i % 2 == 0) /* to factor is the product of primes > 101 */ i++; /* could include a larger list of primes to */ else if (i % 3 == 0) /* factor out to decrease computing time */ i++; /* even more, add more 'if' tests as a */ else if (i % 5 == 0) /* modification */ i++; else if (i % 7 == 0) i++; else if (i % 11 == 0) i++; else if (i % 13 == 0) i++; else if (i % 17 == 0) i++; else if (i % 19 == 0) i++; else if (i % 23 == 0) i++; else if (i % 29 == 0) i++; else if (i % 31 == 0) i++; else if (i % 43 == 0) i++; else if (i % 47 == 0) i++; else if (i % 53 == 0) i++; else if (i % 59 == 0) i++; else if (i % 67 == 0) i++; else if (i % 83 == 0) i++; else if (i % 89 == 0) i++; else if (i % 97 == 0) i++; else if (i % 101 == 0) i++; else is_true = 0; } is_true = 1; cout << i << endl; if (number % i == 0) { f1 = i; /* 'i' is a factor of 'number' */ cout << "\t" << f1; f2 = (number/f1); cout << "\t" << f2 << endl; factor_count = 1; i = number; } if (i == MAX_TIME) { cout << endl << " Taking too much CPU time......Aborting...." << endl; i = sqrt(number) + 2; } } if (factor_count == 0) cout << endl << "\t" << number << " is prime"; cout << endl << endl; } /**************************** PollardRho ********************************* This function attempts to factor large integers using the PollardRho factoring algorithm, assuming that the number to be factored is the product of 2 primes. ***************************************************************************/ void PollardRho (const Integer &number, Integer &f1, Integer &f2) { Integer t(atoIntRep("1")); Integer a = t; Integer b = t; int count = 0; Integer c; while (t == 1) { a = ((a * a) + 1) % number; b = ((b * b) - 1) % number; c = abs(a - b) % number; count++; if (count == MAX_TIME) { cout << endl << " Taking too much computer time...Aborting..." << endl; t = -1; } if (count < MAX_TIME) t = gcd(c, number); } if (t != -1) { f1 = t; cout << "\t" << f1; f2 = (number/f1); cout << "\t" << f2 << endl; } } /****************************** Inverse ********************************* This function computes the inverse of a number in a mod system, if it exists. **************************************************************************/ Integer Inverse (const Integer &m, const Integer &num) { Integer n0, inv, b0, t, t0, q, r, temp; n0 = m; b0 = num; t0 = 0; t = 1; q = (Integer) (n0/b0); r = n0 - q * b0; while (r > 0) { temp = t0 - q * t; if (temp >= 0) temp = temp % m; else if (temp < 0) temp = m - ((-temp) % m); t0 = t; t = temp; n0 = b0; b0 = r; q = (Integer) (n0/b0); r = n0 - q * b0; } if (b0 != 1) cout << endl << "\t" << num << " has no inverse modulo " << m << endl; else { inv = t % m; cout << endl; cout << "\t" << num << "'s inverse modulo " << m << " = " << inv << endl; } return inv; } /***************************** FastExp ************************************* This function does fast exponentiation in a mod system when the cipher text, exponent, and modulus are passed in as parameters. ***************************************************************************/ Integer FastExp (const Integer &ciph, const Integer &exp, const Integer &n) { Integer c1, exp1, x; c1 = ciph; exp1 = exp; x = 1; while (exp1 != 0) { while ((exp1 % 2) == 0) { exp1 = exp1/2; c1 = (c1 * c1) % n; } exp1 = exp1 - 1; x = (x * c1) % n; } return x; }