C++ RSA Implementation

Question

A while ago I wrote an implementation of RSA with C++, that takes in a simple string,encrypts and then decrypts it. It's pretty much the only substantial thing I have written in C++ and while it works (kinda), it is slow at encrypting and extremely slow at decrypting (It takes about ~80 seconds to decrypt a 200 character string using 20 digit primes). So I was wondering what can be done to speed it up and any C++ code tips and best practices. Note that the code is just for a fun implementation and is not going to be used in production.

#include "stdafx.h"
#include "BigInt.h"
#include <iostream>
#include <string>
#include <time.h>

const int PRIME_LENGTH = 20;
const int COPRIME = 65537;

// Creates a random number, not my class, inherited from BigInt
BigInt MakeRandom(BigInt &number, unsigned long int digitCount)
{
    srand(time(NULL));

    // The new number will be created using a string object and later converted into a BigInt
    std::string newNum;
    newNum.resize(digitCount);

    unsigned long int tempDigitCount(0);

    // Generate random digits
    while (tempDigitCount < digitCount)
    {
        unsigned long int newRand(std::rand());

        // 10 is chosen to skip the first digit, because it might be statistically <= n, where n is the first digit of RAND_MAX
        while (newRand >= 10)
        {
            newNum[tempDigitCount++] = (newRand % 10) + '0';
            newRand /= 10;
            if (tempDigitCount == digitCount)
                break;
        }
    }

    // Make sure the leading digit is not zero
    if (newNum[0] == '0')
        newNum[0] = (std::rand() % 9) + 1 + '0';
    number = newNum;
    return number;
}

// Creates a random number, not my class, inherited from BigInt
BigInt makeRandom(BigInt &number, const BigInt &top)
{
    // Randomly select the number of digits for the random number
    unsigned long int newDigitCount = (rand() % top.Length()) + 1;
    MakeRandom(number, newDigitCount);

    // Make sure number < top
    while (number >= top)
        MakeRandom(number, newDigitCount);
    return number;
}

// A Miller Rabin primality test that checks to see if a number is prime ,larger value of z increases accuracy of test

bool isPrime(BigInt &n, int z)
{
    BigInt d = n - 1;
    BigInt two = 2;
    BigInt m;
    BigInt k = 1;
    BigInt remainder;
    BigInt a;
    BigInt x;
    int i = 0;

    // Generates the largest number than can express d as 2k·d
    while (remainder.EqualsZero())
    {
        m = n / two.GetPower(k);
        remainder = m % two;
        k++;
    }

    while (i < z)
    {
        i++;
        BigInt b = makeRandom(a, d - 1);
        x = b.GetPowerMod(d, n);
        if (x == 1 || x == d)
            continue;
        for (int j = 0; j < k - 1; j++)
        {
            x = x.GetPowerMod(two, n);
            if (x == 1)
            {
                // Number is definitely not prime
                return false;
            }
            if (x == d)
                continue;
        }
        // Number is definitely not prime
        return false;
    }

    // Number is probably prime
    return true;
}

// Function that generates the prime number
BigInt primeGeneration(BigInt prime)
{
    BigInt c;

    // If the number is even make it odd
    if (prime % 2 == BigIntZero)
    {
        prime = prime + BigIntOne;
    }

    bool test = isPrime(prime, 40);

    // If the number generated is not prime but odd add two to the number and recheck
    while (test == false)
    {
        prime = prime + 2;
        std::cout << prime << "\n";
        bool test = isPrime(prime, 40);

        if (test == true)
        {
            break;
        }
    }
    return prime;
}

// Calculates the modular multiplicative inverse of e and the totient
BigInt modMultiInverse(BigInt e, BigInt totient)
{
    BigInt b0 = totient, t, q;
    BigInt x0 = BigIntZero, x1 = BigIntOne;
    if (totient == 1) std::cout << BigIntOne << "\n";
    while (e > 1) {
        q = e / totient;
        t = totient, totient = e % totient, e = t;
        t = x0, x0 = x1 - q * x0, x1 = t;
    }
    if (x1 < BigIntZero) x1 += b0;

    return x1;
}

//Encryption method, uses the coprime and the product of the two keys to encrypt
BigInt encryption(BigInt encodedmessage, BigInt coprime, BigInt n)
{
    std::string ciphertext = encodedmessage.GetPowerMod(coprime, n);
    std::cout << ciphertext;
    return ciphertext;
}

// A more efficient way of decrypting; using the Chinese Remainder Theorem
BigInt chineseRemainderTheorem(BigInt d, BigInt p, BigInt q, BigInt c, BigInt e, BigInt n)
{
    BigInt dp = d % (p - 1);
    BigInt dq = d % (q - 1);
    BigInt cTwo = modMultiInverse(p, q);
    BigInt cDp = c.GetPowerMod(dp, p);
    BigInt cDq = c.GetPowerMod(dq, q);
    BigInt u = ((cDq - cDp)*(cTwo) % q);

    //sometimes u is negative which will give an incorrect answer, to make it positive but to keep the mod ratio we add q to it
    if (u < BigIntZero)
    {
        u = u + q;
    }

    return cDp + (u*p);
}

int main()
{
    // Used to seed for the MakeRandom function
    srand(time(NULL));

    BigInt i;
    BigInt p;
    BigInt q;
    BigInt n;
    BigInt d;

    // Coprime is constant and this is a common coprime to use
    BigInt coprime = COPRIME;
    BigInt totient;

    // Generate the first random number to use in the primeGeneration function
    BigInt m = MakeRandom(i, PRIME_LENGTH);

    time_t keyStart, keyEnd;
    time_t encryptionStart, encryptionEnd;
    time_t decryptionStart, decryptionEnd;
    time_t programStart, programEnd;
    time(&keyStart);
    p = primeGeneration(m);

    // Reseed to prevent duplicate primes
    m = MakeRandom(i, PRIME_LENGTH);
    std::cout << "first prime number is:" << "\n";
    std::cout << p << "\n";
    q = primeGeneration(m);
    std::cout << "second prime number is:" << "\n";
    std::cout << q << "\n";
    time(&keyEnd);
    float keyDif = difftime(keyEnd, keyStart);
    std::cout << "\n";
    printf("Elasped time for key generation is %.2lf seconds.\n", keyDif);

    // Generate other figures needed for encryption and decryption
    n = p * q;
    std::cout << n << "\n";
    totient = (p - 1) * (q - 1);
    std::cout << totient << "\n";
    d = modMultiInverse(coprime, totient);
    std::cout << d << "\n";

    std::string plaintext;

    std::cout << "Please enter the string you wish to encrypt:\n";
    getline(std::cin, plaintext);
    time(&programStart);
    BigInt* encode = new BigInt[plaintext.size()];
    BigInt* encrypted = new BigInt[plaintext.size()];
    BigInt* decrypted = new BigInt[plaintext.size()];
    std::string* decode = new std::string[plaintext.size()];

    std::cout << "Encoded string is \n";

    // Encode string to ASCII characters
    for (int i = 0; i < plaintext.size(); i++)
    {
        encode[i] = (BigInt)plaintext[i];
        std::cout << encode[i];
    }

    std::cout << "\n Encrypted string is \n";

    time(&encryptionStart);

    for (int i = 0; i < plaintext.size(); i++)
    {
        encrypted[i] = encryption(encode[i], coprime, n);
    }

    time(&encryptionEnd);

    float encryptionDif = difftime(encryptionEnd, encryptionStart);
    std::cout << "\n";
    printf("Elasped time for encryption is %.2lf seconds.\n", encryptionDif);
    std::cout << "\n Decrypted string is \n";
    time(&decryptionStart);

    for (int i = 0; i < plaintext.size(); i++)
    {
        decrypted[i] = chineseRemainderTheorem(d, p, q, encrypted[i], coprime, n);
        std::cout << decrypted[i];
    }
    time(&decryptionEnd);
    float decryptionDif = difftime(decryptionEnd, decryptionStart);
    std::cout << "\n";
    printf("Elasped time for decryption is %.2lf seconds.\n", decryptionDif);

    // clean up dymanic arrays created earlier
    delete[]encode;
    delete[]encrypted;
    delete[]decrypted;
    delete[]decode;
    time(&programEnd);
    float programDif = difftime(programEnd, programStart);
    std::cout << "\n";
    printf("Elasped time for the program is %.2lf seconds.\n", programDif);
}

Answer 1

Code Style and General Issues

I will get straight to the main point of this answer: What you wrote is basically C. You use basically nothing of the things C++ offers you.

While that is generally a valid thing to do, you posted your question with regards to C++ coding improvements, so a big part of my answer will focus on making your code more C++-like. In addition, there are some other issues which have nothing to do with whether you are working in C or C++ that should be addressed as well. Let's get started!

1. Please don't #include "stdafx.h". It's use is uncommon nowadays, and you are unlikely to encounter it in code that is supposed to compile on any compiler that is not MSVC. Only choose to include it if you can show that it has a significant benefit.
2. Don't #include <time.h>. Do #include <ctime> instead. time.h is a C header, ctime is its C++ equivalent.
3. Speaking of includes, you are missing #include <cstdlib> which is required for std::rand.
4. Don't use rand and srand. Starting from C++11, C++ has rich random number generation facilities in the standard library, which allow for much more fine-grained control of the underlying RNGs and distributions.
5. If you use C legacy functions (such as rand), only use the functions supplied in the std namespace (i.e. std::srand instead of srand). The existence of these functions in the global namespace is not mandated by the standard.
6. Pass parameters by reference or const reference where appropriate. For example, modMultiInverse should likely be taking both its arguments by const reference since they are not modified and probably above the size threshold for efficiently passable objects (although I don't know anything about the big integer library you are using).
7. Don't do timekeeping with time. Use the facilities provided in the chrono header. They are much nicer to work with, enable fine-grained control and are less prone to unit conversion errors etc. (same as with rand/random).
8. Your main-function is doing way too much work. Split it up into multiple different functions with clearly defined responsibilities.
9. Don't start your functions off by declaring every variable you are going to use at some point throughout it. This kind of forward declaration is an old pre-standardized C legacy; neither reasonably modern C nor any version of C++ require it in any way. In fact, it hinders readability to an extent, because the reader has to keep juggling all those variable names mentally, most of which will not be used until much further down in the function.
10. Don't use getline, use std::cin for reading things from the commandline instead.
11. Also, don't use printf, use the format capabilities of std::cout. Again, both getline and printf are legacy C functions and are somewhat restricted in their use.
12. Don't use C-style casts (i.e. casts of the form (newtype) expression). Instead, use on of static_cast, reinterpret_cast and dynamic_cast where appropriate.

13. The following line (taken from main) is almost surely undefined behavior:

    encode[i] = (BigInt)plaintext[i];
    

    You cannot just cast a char to a BigInt and pretend that is right and reasonable. I am also not sure what you are trying to achieve here, but anyhow, you need to call a conversion function here and properly assign to your storage location.

14. Speaking of storage: A surefire way to terrify people with your code is using raw, unchecked new and delete. One of the biggest advantages of C++ compared to C is that you can encapsulate possibly dangerous actions, such as allocating and freeing memory. There are many good reasons why manual memory management is heavily frowned upon in the C++ community: First of all, you can quickly cause undefined behavior by accessing dangling pointers. Secondly, forgetting to free memory can cause your program to gradually feast on available memory, hindering all other applications and eventually causing it to die painfully from out-of-memory.

    Luckily, the STL offers a variety of pre-made utilities to prevent these kinds of disaster: For dynamic, resizable arrays (which happens to be just what you want here), there is std::vector. There are also classes for various other types of containers, and classes such as std::unique_ptr which help mitigate the dangers of raw ownership somewhat.

...and some other things more, but these are the most urgent issues in my opinion.

Why is your code so slow?

You do not provide any benchmark data or other performance evaluation, so I can only make some guesses. However, there are some things that, from a performance point of view, are quite alarming:

1. MakeRandom is a very inefficient function. First of all, you calling srand every time, which you should not do because there is absolutely not point to it and you are actually making your random number generator partly useless. Secondly, you are doing string operations which may imply heap allocations. This also leads you on the path of int-to-string-conversions, which is not good: You are basically taking the route number to string to number, which is two conversions too much, one of which is actually a loop on single digits. Instead, you would likely want some kind of shift-or operation to generate large random numbers more efficiently.

2. while (number >= top)
       MakeRandom(number, newDigitCount);
   

   You have no guarantee that this code will terminate soon. You could be spending a lot of cycles here just guessing at the right answer.

3. Again, I do not know where your BigInt class comes from, but doing big integer arithmetic fast can be kind of tricky. Should one of the slowdowns come from your use of this class, I would suggest you switch to a well-tested and well-acclaimed multi-precision library instead (such as GMP, for example).

Still, one of the most important rules in performance optimizations is: Measure everything you care about. As long as you do not measure, what you are saying is basically that you do not care about performance. Optimization only works if you can identify the culprits and bottlenecks that make your code slow.