C++ big numbers

Question

i am trying to implement RSA for a project and I am stuck at the phase where I need numbers larger than 19 digits( long long i think has 19 digits). I've tried giving unsigned long long but i still don't have 1 digit and the value is incorrect. I can't even check if my encryption/decryption works.

I've tried some libraries but i can't do crossover operations with that type and int... any help?

Here is what i have:

void En() {
crypted= text;
unsigned long long temp=0;
unsigned long long enc = 0;
for (int i = 0; i < text.length() / 2; i++)
{
    if (text[i]>='a' && text[i] <= 'z')
    {
        temp = (text[i] - 96) * 26 + text[i + 1] - 96;
        enc = pow(temp, public_key);
        enc= enc % N
        cout << enc << endl;
        enc_v2 = enc;
    }

}

cout << "Enc: " << enc << endl;}

void De() {
unsigned long long c = 0;
unsigned long long temp2 = 0;
unsigned long long temp = 0;
char ch=' ', ch2=' ';
for (int i = 0; i < text.length()/2; i++)
{
    cout << enc_v2 << private_key;
    temp = pow(enc_v2, private_key);
    cout << "Temp :" << temp;
    temp = temp % N;
    cout << "Temp modulo :" << temp;
    temp2 = temp;
    temp = temp / 26;
    cout << " Temp char 1 :"<< temp;
    ch = temp + 96;


    temp2 = temp2 - temp * 26;
    cout << " Temp char 1 :" << temp2;
    ch2 = temp2 + 96;


}
cout << "Text: " << ch << ch2;}

Thank you!

Answer 1

For larger numbers you need modular exponentiation within a single function. This means that you perform the modulus while you are doing the calculation. Of course doing the operation afterwards can be done, however:

1. it takes up much more bits and
2. it is not nearly as efficient.

As an (inefficient) example, you can see exponentiation as performing multiplication with the base, then taking the modulus and repeating the process until you have performed e multiplications (starting with a 1 value instead of the base, of course).

In most (crypto) libraries you have some kind of bignum library providing a modPow method. Beware that having such functionality in itself is not enough to create secure RSA operations; generally some kind of protection against time or power based side channel attacks also needs to be implemented.

Answer 2

In order to represent integers that are larger than any primitive type, you can use an array of integers where each number of the array represent different bytes of the larger number. This is called arbitrary precision arithmetic. Each arithmetic operation as well as input and output must be implemented separately for such "big" number type.