D1SC0's tech

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

Hello, my name is Jordi. I’m currently a high school senior, but I will be graduating in a few weeks, after which I will be attending university with a major in Electrical Engineering. I’ve been a long-time follower of the diydrones community and have made a few posts in the past. In August of last year I made a blog post entitled “Introducing Glowduino!”. I had created a board that was designed to control multicolored LEDs on various unmanned vehicles. I ordered the boards and assembled them, but made the stupid mistake of using a TQFP ATMega328 and not including an ICSP header. I had known this would be a problem, so I also designed some small breakout boards for programming. I simply pressed the chip onto the board to program it, and then soldered it to the Glowduino. Once everything was assembled I plugged it in and…it didn’t work. After a good deal of searching I realized that I had accidentally flashed the wrong Arduino bootloader to the chip. I was using a 16Mhz crystal, yet I flashed a 8Mhz crystal-less bootloader. I don’t have a hot-air rework station, and desoldering it didn’t work so well (believe me, I tried). With the board bricked and my hopes dashed, I put the project aside to focus on school work.

A month or two ago I decided to come back to the project and see if I could at least get it into a working state. I designed and ordered some breakouts for the various chips that are used on the project and began breadboarding the design (I know I know, I should have done that first :)) and writing some code. I soon realized that the entire concept behind Glowduino might be more successful if the system were more modular. This got me looking into viable Arduino-compatible microcontrollers, and I soon came across the Arduino Micro. While all of its features are very well suited to my needs, I didn’t really like the form factor, among a few other small things. For these reasons I decided to set out to create a ‘better’ Arduino Micro. I barely changed anything from the original design. The only changes I made were to include higher capacity regulators and to shrink the size of the board. I shrank the width by 0.1″ and the length by 0.3″. This meant that instead of having two rows of 17 pins it now has two rows of 16, and they are 0.5 inches apart (1 row closer together on a breadboard). I also rearranged the order of the pins to better match the larger Arduino Uno and Leonardo pinouts. All this came with a price, however, and no matter how hard I tried I simply could not route the board on two layers.

I only have the free version of Cadsoft’s Eagle which only allows the creation of 2-layer boards. I had heard of Kicad and it sounds awesome, but after weeks of trying to migrate all my libraries and design files over to it I realized that I would be forced to stay with Eagle for the time being. After laying this project on the shelf for a bit I remembered that I had a friend who owned the full professional Eagle software. I asked him if I could use it and he agreed, and after a long bit of routing, ripping up, and re-routing I had a 100% routed 4-layer board that could be purchased from OSHPark. This time, however, I didn’t immediately order the boards. Instead, I bought an ATMega32u4 and breakout from Futurlec and set to work breadboarding the project. I have made all the necessary connections and I am currently trying to get my usbasp to talk to the chip so that I can flash a bootloader. I haven’t made too much progress on this front yet, tho, as AP Tests are coming up, final projects for my classes are due soon, and I am acting in my school’s current musical.

In the above photos, the purple board is a breakout for the TLC5947. It is larger than my final Arduino clone will be 🙂

With the completion of this new microcontroller the Glowduino has been turned into a ‘shield’ for it. The idea is that the system will be super modular, with the option for more ‘shields’ in the future. In fact, it would be almost trivial to create an adapter for using preexisting Arduino shields with this microcontroller. Users could have the option of only installing one shield on each vehicle and simply plugging the microcontroller into whichever one they wish to use. Additionally, expansion boards could be designed that extend the Glowduino’s capabilities, such as the ability to control EL wire or LED matrixes (thank you Jonathan Lederer!).

I know I will at least make a few of these boards for my friends and I, but this is where I would like some feedback. Is this a good idea? Would you buy it? What ideas do you have for something you could do with it? Is there anything you’d like to see? What is a reasonable price-point? I’m completely into open-sourcing everything, so the design files, schematics, bill of materials etc. will all be released completely once the project is finished. I will be updating my flickr (which is currently quite sparse) with photos soon, here’s the link: Flickr Photostream. I would love to be able to actually build these in the future, and I very much appreciate your feedback. Thank you!

Original blog post: diydrones.com

D1SC0's tech

Google Docs and QR Codes

RSA Encryption

An Arduino Micro Clone