How to deal with 128bit variable in MinGM32 bit compiler for Encryption (Diffie Hellman Algorithm) in Qt

Question

I want to use the below equation in one of the code

A = g^a mod p; //g raise to a modulus p.

(something like 2^5 % 3) = 32%3 = 2

(This equation looks like Diffie Hellman algorithm for security)

Where:

• ^ is (power)
• g is fixed number 0x05
• a is 128bit(16bytes) randomly generated number,
• p is fixed hex number of 128bit(16bytes). Something like (0x0xD4A283974897234CE908B3478387A3).

I am using:

• Qt 4.8.7
• Compiler MinGW32 (checked with boost library boost 1.70)

The solutions which I found which didn`t work for me are listed below:

1. one can use __int128 but to support that one should have used latest GCC compiler or MinGW64 bit compiler, neither of that I am using now.

2. I found one latest version of Qt has QSslDiffieHellmanParameters class, but again not supported in our Qt version.

3. I found some libraries like boost/multiprecision/cpp_int.hpp (boost 1.70)) that does have data type such as int128_t and int256_t, but due to our compiler isssue or something else, we are not able to store 128bit number, meaning if I do:

    int128_t ptval128 = 0xAB1232423243434343BAE3453345E34B;
    cout << "ptval128 = " << std::hex << ptval128 << endl;
    //will print only 0xAB12324232434343;//half digits only,

4. I tried using Bigint which much more useful, but again 5^(128bit number) is way too big, it takes hours to compute things, (I waited till 1 hour and 16 mins and kill the application).

    int myGval = 0x05;
    128_bit_data_type myPVal= 0xD4A283974897234CE908B3478387A3; 

    128_bit_data_type 128_bit_variable = 128_bit_random_data;
    myVal = (myGval)^(128_bit_variable) % (myPVal);

Answer 1

That is not how to do modular exponentiation! The first problem is that 5 ^ 128_bit_variable is huge, so big that it won't fit into memory in any computers available today. To keep the required storage space within bounds, you have to take the remainder % myPVal after every operation.

The second problem is that you can't compute 5 ^ 128_bit_variable simply by multiplying by 5 by itself 128_bit_variable times -- that would take longer than the age of the universe. You need to use an exponentiation ladder, which requires just 128 squarings and at most 128 multiplications. See this Wikipedia article for the details. In the end, the operation 5 ^ 128_bit_number should take a fraction of a second.