AlgorVonKruskal AlgorVonKruskal - 29 days ago 12
C++ Question

C++ GMP random number generation for Diffie-Hellman Key Exchange

I need to calculate a private key (privateKey) for Diffie-Hellman key exchange. I have given a big prime prime and now I just need to choose a number that is less than p. This is my code:

mpz_class privateKey;
unsigned long seed;
mpz_init(privateKey.get_mpz_t());

gmp_randstate_t rstate;
gmp_randinit_mt(rstate);
gmp_randseed_ui(rstate, seed);

mpz_urandomm(privateKey.get_mpz_t(), rstate, prime.get_mpz_t());


I don't really understand why I'm always getting the same "random" number.

Answer Source

You never initialize the seed variable, so your program is obviously wrong and your compiler should have warned you about this. If it didn't, look up how to configure your compiler correctly (e.g. for GCC make sure you pass at least -O -Wall).

You'll always get the same random number if you initialize the RNG with the same seed. That's probably what's happening in your program: seed is not initialized, so its value is whatever was on the stack at this address previously, and that turns out to be always the same if you're calling this function in the same way.

Since this is a cryptographic application, you need to seed the random number generator with a high-entropy source. Ask your operating system for it (there's no way to generate entropy inside a program): read from /dev/urandom on Linux, call CryptGenRandom on Windows.

Also, since this is a cryptographic application, don't call gmp_randinit_mt. This creates a Mersenne twister, which is fast and good enough for a physics simulation, but not suitable for cryptography because its state can be reconstructed from its outputs. I'm not familiar with GMP, but looking at the documentation, I see that it offers several algorithms for random number generation but none are suitable for security applications. You can use the OS source like /dev/urandom or CryptGenRandom directly as a source of random bits, but then you'd need to use that to implement the gmp_randstate_t interface in order to hook it up with mpz_urandomm. I don't know how difficult that is.

If this is a school exercise, do whatever your teacher tells you. If this is for an actual application, use an existing cryptography library such as libtom, which comes with all you need to generate cryptographic-quality random numbers and to perform the Diffie-Hellman computations, is very easy to integrate into a project, and has a license that allows it to be integrated into any project.