I need to generate a EDH group on the fly in one has not been specified in a config file. Diffie-Hellman is kind of expensive in terms of computation, so I'd like to reduce the cost if possible.

Is there any benefit to selecting a generator of 5 versus 3 or 2 in an attempt to keep the costs minimized? Is this a misguided optimization?

Related: are there any libraries that allows you to specify, for example, {2,3,5} are acceptable generators for a group? Or do you normally just specify a subgroup order? (I know OpenSSL has for example, DH_GENERATOR_2, but I'm not aware its a bit mask value).

  • 2
    $\begingroup$ Why don't you simply hardcode a default group? $\endgroup$ Jan 15, 2014 at 20:18
  • 1
    $\begingroup$ When using ephemeral DH you do not have to choose fresh group parameters all the time, but only a new exponent on every key exchange. $\endgroup$
    – DrLecter
    Jan 15, 2014 at 22:01
  • $\begingroup$ CodesInChaos and DrLecter - there are two choices: (1) NIST/IETF group, and (2) user supplied group. If (2) is chosen but no group provided, it is generated on the fly. $\endgroup$
    – user10496
    Jan 16, 2014 at 4:29

1 Answer 1


I'm not aware of any attack made much easier by using a small generator in EDH, like $g=3$ or $g=5$, even $g=2$ (but I'm not accustomed to GNFS or index calculus), as long as there is a single $g$ used for a given instance of other parameter(s). These generators are common, and (especially $g=2$) allow a modest but sizable performance improvement.

I would give a reference to the desired library, if I knew one. However it is not rocket science to implement for straight EDH, when the desired criteria is known. If we want a random huge $p$ and a generator $g$ among a small list of small $g>1$ such that $g$ is a generator of the group $\mathbb Z_p^*$ where the Discrete Log is hard, one possibility is to generate a random prime $p$ of the desired size until $(p-1)/2$ is also prime, and for one of the desired $g$ we have $g^{(p-1)/2}\bmod p\ne1$ (notice that $g^{p-1}\bmod p=1$ holds since $p$ is prime, and $g^2\bmod p\ne1$ holds since $g\ll\sqrt p$).

There a many other criteria in use, such as those set by RFC 2412, used by IKE as defined by RFC 2409, where in addition to $p$ and $(p-1)/2$ prime, it is wanted:

  • $g=2$ and $g^{(p-1)/2}\bmod p=1$ (rather than $\ne1$), for reasons explained by poncho;
  • a number of top and bottom bits of $p$ are forced to 1, in order to simplify modular reduction both by classical and Montgomery arithmetic;
  • the random-looking center bits of $p$ are traceable to a nothing up my sleeves number.

Another common set of criteria it that for DSA, as specified by FIPS 186-4, appendix A (also good for the Finite Field Cryptography scheme of NIST SP 800-56Ar2 and ancestors, which use DSA public key certificates in order to resist MITM). That requires more complex parameter selection; in particular, a subgroup of prime order $q$ much smaller than $p$. While still not rocket science, that parameters generation process is more involved, and constrained by the standards.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.