[openssl-users] Generating large DH parameters

[Viktor Dukhovni]

On Wed, Jan 14, 2015 at 08:23:13AM -0600, jack seth wrote:

> Thanks for the explanation.  So I guess I just got lucky with
> the first one. :)   Do you have any kind of estimate of how long
> it will take to generate?

The density of strong primes is conjectured to be ~1.3*n/(ln(n))^2.

For 16k bit primes you're looking at one number out of 100 million.

For 2k bit primes the density is 64 times larger.

In addition to density-related factor of 64, one needs to take into
account the increased cost of testing the primality of each candidate.
I don't know how that scales with "log n" in OpenSSL, but it is
surely at least linear.

So this gives you a factor of at least 512 for the run-time of
generating DH 2k vs DH 16k.

DO NOT USE 16k bit prime DH groups.  Even 4k bit and definitely
anything larger is essentially impractical.

-- 
	Viktor.