Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
2  
Why don't you simply hardcode a default group? –  CodesInChaos Jan 15 at 20:18
1  
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. –  DrLecter Jan 15 at 22:01
    
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. –  noloader Jan 16 at 4:29

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.