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
D1SC0's tech 