2
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ Why don't you simply hardcode a default group? $\endgroup$ – CodesInChaos Jan 15 '14 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 '14 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 '14 at 4:29
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy