This year I took my school’s AP Calculus BC course. Instead of final exams for the second semester we were required to develop a final project and present it to the class. I, along with two classmates, decided to study RSA encryption. RSA, named for its three inventors, was created as a new form of public-key cryptography (I recommend you click that link and read through it, it’s incredibly interesting). As part of the project we were tasked with applying the mathematical concepts to something in the real world. I decided it would be a great idea to write a program capable of encoding and decoding messages using RSA encryption. I started working on the code during a long day election judging, but soon got stuck. I was using C++, the only language I know (yet), and I needed a way of storing large numbers. Now, my 64-bit laptop is at most capable of creating 64-bit unsigned integers. That works out to a maximum value of 18,446,744,073,709,551,615. While that is an incredibly large number, I soon realized that I would be working with much larger ones (think 2,917^3,697). I looked into various bignum libraries, but Xcode didn’t like that idea. I persisted for a few days, but alas, I did not succeed. I put the project on hold for a few weeks while I worked on schoolwork, but eventually realized I would have to write my own bignum functions.
I created addition, multiplication, exponentiation, and modulation functions for use with big integers. To do so, I first had to convert my entire program over to using massive arrays (currently 10,000 digits). Once I had that accomplished, I set out to re-learn basic addition and multiplication. This was actually surprisingly hard as I have used calculators for everything since middle school and had forgotten how to do computations by hand. I spent a few intensive days chasing bugs, and it finally worked! With all the mathematics working, I then had to create a nice pretty UI to show off to my calc class. Even though constantly cout-ing information probably slows down the program, it was necessary both to please the crowd and to give a visual indicator that my computer hadn’t just frozen. Last Friday (5/10/13) was the day of the presentation and it went swimmingly. The class of mostly non-programmers thought the numbers flashing by looked cool, and the decoded message was the same as the original. Now here’s hoping I get a semi-decent grade for the semester 😉 Cheers!
Here are the three source files for your enjoyment. They compile fine with Xcode on a mac (with one warning about time(null)), but I can’t speak for any other OS. The highlighted section in bignum.cpp is the method I originally used for the modulo function. For some reason it only worked in some situations, and I believe my current code (the part just above it) isn’t very consistent either.
Code is released into the public domain and open-source.
#include "header.h" #include <iostream> using namespace std; // Initialize message as an unsigned 64-bit integer uint64_t nMessage = 0; int main() { srand(time(NULL)); // Entire program contained within a loop while (true) { // Initialize all variables as unsigned 64-bit integers uint64_t nFactorP, nFactorQ; uint64_t nProduct; uint64_t nPhiN; uint64_t nPublicExponent; uint64_t nPrivateExponent = 0; // Find first prime for (nFactorP = rand() % 100 + 30; nFactorP > 1; nFactorP--) { int i; for (i = 2; i <= nFactorP / 2; i++) { if (!(nFactorP % i)) break; } if (i > nFactorP / 2) break; } // Find second prime for (nFactorQ = rand() % 100 + 30; nFactorQ > 1; nFactorQ--) { int i; for (i = 2; i <= nFactorQ / 2; i++) { if (!(nFactorQ % i)) break; } if (i > nFactorQ / 2) break; } // Find the product N of both primes P and Q nProduct = nFactorP * nFactorQ; // Find Phi of N (Euler's Totient Function) by multiplying (P - 1) by (Q - 1) nPhiN = (nFactorP - 1) * (nFactorQ - 1); // Find the public exponent E by finding a coprime of Phi of N for (nPublicExponent = rand() % 90 + 10; nPublicExponent > 1; nPublicExponent--) { if (gcd(nPublicExponent, nPhiN) == 1) break; } // Find the private exponent for (int i = 1; i < nPhiN; i++) { if (!((i * nPhiN + 1) % nPublicExponent)) { nPrivateExponent = (i * nPhiN + 1) / nPublicExponent; break; } } // Print a bunch of info cout << "\nP = " << nFactorP << endl; cout << "Q = " << nFactorQ << endl; cout << "N = " << nProduct << endl; cout << "Phi of N = " << nPhiN << endl; cout << "Public Exponent = " << nPublicExponent << endl; cout << "Private Exponent = " << nPrivateExponent << endl; // Request a number to encode cout << "\nPlease enter a 1-3 digit number" << endl; cin >> nMessage; cout << "\nOriginal message = " << nMessage << endl; // Store all values in arrays short anPublicExponent[nArraySize] = {}; uint64_t nPublicExponentTemp = nPublicExponent; for (int64_t i = 0; i < nArraySize; i++) { int nRemainder = nPublicExponentTemp % 10; anPublicExponent[nArraySize - i - 1] = nRemainder; nPublicExponentTemp -= nRemainder; nPublicExponentTemp /= 10; } short anPrivateExponent[nArraySize] = {}; uint64_t nPrivateExponentTemp = nPrivateExponent; for (int64_t i = 0; i < nArraySize; i++) { int nRemainder = nPrivateExponentTemp % 10; anPrivateExponent[nArraySize - i - 1] = nRemainder; nPrivateExponentTemp -= nRemainder; nPrivateExponentTemp /= 10; } short anProduct[nArraySize] = {}; uint64_t nProductTemp = nProduct; for (int64_t i = 0; i < nArraySize; i++) { int nRemainder = nProductTemp % 10; anProduct[nArraySize - i - 1] = nRemainder; nProductTemp -= nRemainder; nProductTemp /= 10; } short anMessage[nArraySize] = {}; uint64_t nMessageTemp = nMessage; for (int64_t i = 0; i < nArraySize; i++) { int nRemainder = nMessageTemp % 10; anMessage[nArraySize - i - 1] = nRemainder; nMessageTemp -= nRemainder; nMessageTemp /= 10; } // Store all values in arrays // Encode message short *pMessageEncoded = bignumExpMod(anMessage, anPublicExponent, anProduct); // Print a bunch of info cout << "\n\nP = " << nFactorP << endl; cout << "Q = " << nFactorQ << endl; cout << "N = " << nProduct << endl; cout << "Phi of N = " << nPhiN << endl; cout << "Public Exponent = " << nPublicExponent << endl; cout << "Private Exponent = " << nPrivateExponent << endl; cout << "\nOriginal message = " << nMessage << endl; cout << "\nEncoded message = "; // Print encoded message bool bZero = false; for (int64_t i = 0; i < nArraySize; i++) { if (*(pMessageEncoded + i)) bZero = true; if (bZero) cout << *(pMessageEncoded + i); } cout << endl; // Request to decode cout << "\n\nType any character to decode" << endl; char chDecode; cin >> chDecode; // Store encoded message in array short anMessageEncoded[nArraySize] = {}; for (int64_t i = 0; i < nArraySize; i++) anMessageEncoded[i] = *(pMessageEncoded + i); // Decode message short *pMessageDecoded = bignumExpMod(anMessageEncoded, anPrivateExponent, anProduct); // Print a bunch of info cout << "\n\nP = " << nFactorP << endl; cout << "Q = " << nFactorQ << endl; cout << "N = " << nProduct << endl; cout << "Phi of N = " << nPhiN << endl; cout << "Public Exponent = " << nPublicExponent << endl; cout << "Private Exponent = " << nPrivateExponent << endl; cout << "\nOriginal message = " << nMessage << endl; cout << "\nEncoded message = "; // Print encoded message bZero = false; for (int64_t i = 0; i < nArraySize; i++) { if (anMessageEncoded[i]) bZero = true; if (bZero) cout << anMessageEncoded[i]; } cout << endl; cout << "\nDecoded message = "; // Print decoded message bZero = false; for (int64_t i = 0; i < nArraySize; i++) { if (*(pMessageDecoded + i)) bZero = true; if (bZero) cout << *(pMessageDecoded + i); } cout << "\n\n" << endl; // Ask if the user would like to restart the program char chLoop; cout << "\nWould you like to run again? (y/n)" << endl; cin >> chLoop; if (chLoop == 'n') exit(0); } return 0; } uint64_t gcd(uint64_t x, uint64_t y) { // Function is recursive: it calls itself until x % y = 0 if (!(x % y)) return y; else return gcd(y, x % y); }
#include "header.h" #include <iostream> using namespace std; // Addition short * bignumAdd(short anNumber1[], short anNumber2[]) { // Initialize sum array static short anSum[nArraySize] = {}; // Initialize carry value to 0 int nCarry = 0; // Add the two arrays and the carry from the previous digit for (int64_t i = nArraySize - 1; i >= 0; i--) { anSum[i] = anNumber1[i] + anNumber2[i] + nCarry; // Calculate carry for next time through the loop if (anSum[i] > 9) { nCarry = 1; anSum[i] = anSum[i] % 10; } else nCarry = 0; } // Return the sum return anSum; } // Multiplication short * bignumMul(short anNumber1[], short anNumber2[]) { // Initialize product array static short anProduct[nArraySize] = {}; // Calculate product using the grid method for multiplication for (int64_t i = nArraySize - 1; i >= 0; i--) { for (int64_t ii = nArraySize - 1; ii >= 0; ii--) { int nProduct = anNumber1[ii] * anNumber2[i]; if ((ii + i - nArraySize + 1) > 0) anProduct[ii + i - nArraySize + 1] += nProduct; } } // Initialize carry value to 0 int nCarry = 0; // Factor in the carries for (int64_t i = nArraySize - 1; i >= 0; i--) { anProduct[i] += nCarry; // Calculate carry for next time through the loop if (anProduct[i] > 9) { int nRemainder = anProduct[i]; nRemainder -= (nRemainder % 10); nCarry = nRemainder / 10; anProduct[i] -= nRemainder; } else nCarry = 0; } // Return the product return anProduct; } // Exponentiation short * bignumExp(short anBase[], short anPower[]) { // Initialize product and temporary arrays static short anProduct[nArraySize] = {}; short anProductTemp[nArraySize]; // Set temp array equal to the base for (int64_t i = 0; i < nArraySize; i++) anProductTemp[i] = anBase[i]; // Loop multiplication portion while the power is greater than 1 while (true) { // Decrement the power array by 1 if (anPower[nArraySize - 1]) anPower[nArraySize - 1] -= 1; else { anPower[nArraySize - 1] = 9; for (int64_t i = nArraySize - 2; i >= 0; i--) { if (anPower[i]) { anPower[i] -= 1; break; } else anPower[i] = 9; } } // Initialize stop variable to true bool bStop = true; // If all elements of the power array are zero, bStop stays true for (int64_t i = 0; i < nArraySize; i++) if (anPower[i] > 0) bStop = false; // If power array is 0, break the loop if (bStop) break; // Calculate the number of significant digits in the temp array int64_t nSize1 = 0; for (int64_t i = 0; i < nArraySize; i++) { if (anProductTemp[i] > 0) { nSize1 = nArraySize - i; break; } } // Calculate the number of significant digits in the base array int64_t nSize2 = 0; for (int64_t i = 0; i < nArraySize; i++) { if (anBase[i] > 0) { nSize2 = nArraySize - i; break; } } // Calculate which array is the longest (temp or base) int64_t nSize = 0; if (nSize1 < nSize2) nSize = nSize2; else nSize = nSize1; // Set product array to 0 for (int64_t i = 0; i < nArraySize; i++) anProduct[i] = 0; // Calculate the product of the temp array and the base and store it in the product array (using grid method) for (int64_t i = nArraySize - 1; i >= nArraySize - nSize; i--) { for (int64_t ii = nArraySize - 1; ii >= nArraySize - nSize; ii--) { int nProduct = anProductTemp[i] * anBase[ii]; if ((ii + i - nArraySize + 1) > 0) anProduct[ii + i - nArraySize + 1] += nProduct; } } // Calculate the number of significant digits in the product array for (int64_t i = 0; i < nArraySize; i++) { if (anProduct[i] > 0) { nSize = nArraySize - i; break; } } // Initialize carry value to 0 int nCarry = 0; // Factor in the carries for (int64_t i = nArraySize - 1; i >= nArraySize - nSize - 1; i--) { anProduct[i] += nCarry; if (anProduct[i] > 9) { int nRemainder = anProduct[i]; nRemainder -= (nRemainder % 10); nCarry = nRemainder / 10; anProduct[i] -= nRemainder; } else nCarry = 0; } // Set the temp array equal to the product array for (int64_t i = 0; i < nArraySize; i++) anProductTemp[i] = anProduct[i]; // Calculate the number of significant digits in the product array int64_t nSize3 = 0; for (int64_t i = 0; i < nArraySize; i++) { if (anProduct[i] > 0) { nSize3 = nArraySize - i; break; } } //Print info bool bZero = false; cout << "Multiplications left: "; for (int64_t i = 0; i < nArraySize; i++) { if (anPower[i]) bZero = true; if (bZero) cout << anPower[i]; } cout << endl; bZero = false; cout << "Digits: " << nSize3 << " Product: "; for (int64_t i = 0; i < nArraySize; i++) { if (anProduct[i]) bZero = true; if (bZero) cout << anProduct[i]; } cout << endl; //Print info } // Return the product return anProduct; } // Modulation short * bignumMod(short anDividend[], short anModulus[]) { // Initialize the remainder and temporary arrays static short anRemainder[nArraySize] = {}; short anModulusTemp[nArraySize] = {}; // Loop subtraction portion while the remainder is greater than 0 while (true) { // Calculate the number of significant digits in the dividend array int64_t nSize1 = 0; for (int64_t i = 0; i < nArraySize; i++) { if (anDividend[i] > 0) { nSize1 = nArraySize - i; break; } } // Calculate the number of significant digits in the modulus array int64_t nSize2 = 0; for (int64_t i = 0; i < nArraySize; i++) { if (anModulus[i] > 0) { nSize2 = nArraySize - i; break; } } // Initialize stop variable to false bool bStop = false; if (nSize1 == nSize2) { // Check if the dividend is larger or smaller than the modulus for (int64_t i = nArraySize - nSize1; i < nArraySize; i++) { if (anDividend[i] - anModulus[i] > 0) break; else if (anDividend[i] - anModulus[i] < 0) { bStop = true; break; } } } else if (nSize1 < nSize2) bStop = true; // If the dividend is smaller than the modulus, set the remainder equal to it and break the loop if (bStop) { for (int64_t i = 0; i < nArraySize; i++) anRemainder[i] = anDividend[i]; break; } // If the modulus is shorter than the dividend then multiply it by 10 until it is one digit shorter than the dividend if ((nSize1 - nSize2) > 1) { for (int64_t i = 0; i < nArraySize - (nSize1 - nSize2 - 1); i++) anModulusTemp[i] = anModulus[i + (nSize1 - nSize2 - 1)]; // Set the temp array equal to the modulus for (int64_t i = nArraySize - (nSize1 - nSize2 - 1); i < nArraySize; i++) anModulusTemp[i] = 0; } else { // If not, just set the temp array equal to the modulus for (int64_t i = 0; i < nArraySize; i++) anModulusTemp[i] = anModulus[i]; } /* for (int64_t i = 0; i < nArraySize; i++) anModulusTemp[i] = anModulus[i]; for (int64_t i = 1; i < nSize1 - nSize2; i++) { for (int64_t ii = nArraySize - nSize1 - 1; ii < nArraySize - 1; ii++) { anModulusTemp[ii] = anModulusTemp[ii + 1]; if (ii == nArraySize - 2) anModulusTemp[nArraySize - 1] = 0; } } */ // Subtract the modulus from the dividend for (int64_t i = nArraySize - 1; i >= nArraySize - nSize1; i--) { if ((anDividend[i] - anModulusTemp[i]) < 0) { anDividend[i] += 10; anDividend[i - 1] -= 1; } anRemainder[i] = anDividend[i] - anModulusTemp[i]; } // Set the dividend equal to the remainder for (int64_t i = 0; i < nArraySize; i++) anDividend[i] = anRemainder[i]; // Calculate the number of zeros after the significant digits in the modulus array int64_t nSize3 = 0; for (int64_t i = nArraySize - 1; i >= 0; i--) { if (anModulusTemp[i] > 0) { nSize3 = nArraySize - i - 1; break; } } //Print info bool bZero = false; cout << "Modulus: "; for (int64_t i = 0; i < nArraySize; i++) { if (anModulus[i]) bZero = true; if (bZero) cout << anModulus[i]; } cout << "*10^" << nSize3 << endl; bZero = false; cout << "Digits: " << nSize1 << " Remainder: "; for (int64_t i = 0; i < nArraySize; i++) { if (anDividend[i]) bZero = true; if (bZero) cout << anDividend[i]; } cout << endl; //Print info } // Return the remainder return anRemainder; } // Exponentiation and subsequent modulation short * bignumExpMod(short anBase[], short anPower[], short anModulus[]) { // Modulate the base first to speed up computation short *pMod = bignumMod(anBase, anModulus); short anMod[nArraySize] = {}; for (int64_t i = 0; i < nArraySize; i++) anMod[i] = *(pMod + i); // Calculate the exponent short *pExp = bignumExp(anMod, anPower); short anExp[nArraySize] = {}; for (int64_t i = 0; i < nArraySize; i++) anExp[i] = *(pExp + i); // Modulate the exponentiated number short *pExpMod = bignumMod(anExp, anModulus); static short anExpMod[nArraySize] = {}; for (int64_t i = 0; i < nArraySize; i++) anExpMod[i] = *(pExpMod + i); // Return the final value return anExpMod; }
#ifndef Calculus_RSA_Project_header_h #define Calculus_RSA_Project_header_h #include <iostream> // Functions in main.cpp uint64_t gcd(uint64_t, uint64_t); // Functions in bignum.cpp short * bignumAdd(short[], short[]); short * bignumMul(short[], short[]); short * bignumExp(short[], short[]); short * bignumMod(short[], short[]); short * bignumExpMod(short[], short[], short[]); // Global variables const uint64_t nArraySize = 10000; #endif