-1

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,
  1. 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);
Dimitry Ernot
  • 6,256
  • 2
  • 25
  • 37
Rohit Dharaviya
  • 1
  • 2
  • this is an [XY problem?](https://meta.stackexchange.com/q/66377/230282). You should ask how to calculate the modulo of a power instead. Possible duplicate of [Raising large number to large power and mod it by a large number?](https://stackoverflow.com/q/27153665/995714), [Calculate (a^b)%c where 0<=a,b,c<=10^18](https://stackoverflow.com/q/32485750/995714), [Calculating (a^b)%MOD](https://stackoverflow.com/q/11272437/995714), [a to power b modulus k](https://stackoverflow.com/q/30138020/995714)... Besides, mingw is very bad compared to mingw64 – phuclv May 10 '19 at 14:50

1 Answers1

0

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.

TonyK
  • 16,761
  • 4
  • 37
  • 72
  • that number far exceeds the total number of particles in the universe (~10⁸⁰) – phuclv May 10 '19 at 14:53
  • @TonyK thank you so much for your comment. I checked your Wikipedia link, and followed https://www.geeksforgeeks.org/exponential-squaring-fast-modulo-multiplication/ link, it seems working well, i changed data type from long int to Bigint. – Rohit Dharaviya May 14 '19 at 05:32
  • Hi all, I found other solution to solve this equation using Crypto++ library, Checkout the link https://www.cryptopp.com/docs/ref/class_integer.html#a3b3f94c11fbf120d78837483093dfc8b – Rohit Dharaviya Jun 11 '19 at 11:09