Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I realise it's very hard to generate suitable prime numbers and generators for the Diffie-Hellman key exchange.

What is the best way to generate them? And if I have one, can I use it twice? According to Wikipedia, they are considered "public".

share|improve this question
    
Mh, I was going to answer this myself, but I can't due to my rep. If you want to answer, maybe this'll save you a few seconds on google: ietf.org/rfc/rfc3526.txt –  Stefano Palazzo Jul 13 '11 at 18:03
add comment

1 Answer

up vote 9 down vote accepted

Actually it is not that hard. It may be slightly expensive, computationally speaking.

A good DH modulus and generator is what you get when generating DSA key parameters; see the DSA specification. You get to choose the subgroup order (q, a prime number), the modulus (p, such that p-1 is a multiple of q), and a generator for the subgroup of size q. OpenSSL can do that for you. It is not very hard to implement yourself, provided that your programming language and environment provides some support for arbitrary-length integers (Python and Java do, C does not, unless you use an extra library such as GMP).

Alternatively, some effort has been invested into generating so called "safe primes": prime integers p such that (p-1)/2 is also a prime. A safe prime is called such because it does not suffer from some attacks which may make discrete logarithm easy (or at least easier) on some "weak" modulus -- but a randomly generated modulus will not be weak, with an overwhelming probability, so there is no real worry here. Also, "safe primes" have the advantage of allowing g=2 as generator, which promotes computational efficiency (not by much, but still). Generating a safe prime entails trying random odd integers of the right size until you hit a safe prime: nothing complex or even hard to implement, but it can take a few minutes to complete (about one odd 1024-bit integer in 400000 is a safe prime). Or you can use one of those from RFC 3526.

There is no problem in using the same group parameters (modulus, generator) for millions of distinct key pairs. They are indeed "public data".

share|improve this answer
    
In that case, why does—for instance—OpenVPN require the user to provide DH parameters? Why not just choose some automatically? Surely it knows better than I, and since it's public information, it can't be compromised. –  Peeja Dec 26 '12 at 16:38
2  
Some organizations (especially big administrations) tend to have ritualistic requirements on cryptographic objects, often expressed as "ye shall use only Approved DH parameters", for some notion of "approval". Asking the sysadmin to provide such objects is the bureaucratically safe way to do, from the point of view of the OpenVPN developers. –  Thomas Pornin Dec 27 '12 at 15:33
    
@ThomasPornin Can you just mention some attacks that make it "easy" to break DL in primes that are not safe? –  curious May 2 '13 at 8:52
1  
@curious: deliberately weak DH parameters may use a non-prime subgroup order q, which would factor as a bunch of small primes, allowing DL modulo each of these small primes. Other weak DH parameters would use a modulus of a special form, so that SNFS can be applied (instead of the generic NFS). However, a randomly generated prime will be "safe enough" by a very large margin, with overwhelming probability -- to get weak parameters, you really have to do it on purpose (and with much maths). –  Thomas Pornin May 2 '13 at 11:36
add comment

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.