Openssl dhparam 2048 posted February 2016

While some people would tell you to use pre-defined Diffie-Hellman parameters (rfc3526, rfc5114) so as not to mess something up during the generation (hum hum socat), others would tell you "hey, look at what happened with logjam and their hardcoded DH params!" and will point you to openssl dhparam to generate your own customized parameters.

But how does it really work? The high level code is less than 450 lines long. It's basically taking several stuff into consideration ("do you want to use 2 or 5 as a generator? No? Let's use 2 anyway!") and then using some DH_generate_parameters() function that will set up everything.

Inside of that function relies probable_prime_dh_safe() that will look for a particular kind of prime as the DH modulus: a safe prime.

A safe prime looks like this: \(2p + 1\) with \(p\) a prime as well.

Actually, we can also say that the function looks for a Sophie Germain prime, a prime \(p\) such that \(2p+1\) is also prime.

Like that you know =), safe primes are not the same as Sophie Germain prime, but they are closely related.

(Not to mix up with strong prime as well, which are just primes that have some properties.)

Another important thing: the function returns a safe probable primes. That is a function that has not been mathematically proven to be a prime (but is close enough).

To do that, first a random number is generated. Then a test called the Miller-Rabin test is applied to the random number a number of time. The more you run the test and the more certainty you get that it is a prime, if the test ever fail you know for sure that the number is not a prime (so a composite) and you need to regenerate a new random number and start again with the tests.

How many times should you apply this test? Enough time so that if everyone tried to generate primes every second for the lifespan of earth we would still have low chances to find a false positive (a composite number passing X tests of Miller-Rabin). The numbers used in OpenSSL come from the table 4.4 in the Handbook of Applied Cryptography.

(To make the test faster a bunch of small primes are first tested as divisors, then some trial divisions follow.)