29

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

AviD
  • 72,138
  • 22
  • 136
  • 218
Stefano Palazzo
  • 971
  • 2
  • 11
  • 18
  • 1
    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: http://www.ietf.org/rfc/rfc3526.txt – Stefano Palazzo Jul 13 '11 at 18:03

1 Answers1

24

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

Community
  • 1
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 1
    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
  • 7
    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 02 '13 at 08:52
  • 2
    @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 02 '13 at 11:36
  • 1
    I'm not agreeing with lily wilson here. I think that using standardized parameters is not a problem per se *as long as they are strong enough*. So the primes should be 2048 bit or over; using [the values defined here](https://tools.ietf.org/html/rfc3526) is probably enough to take away these worries. lily, you really should not make significant changes to an answer like that. – Maarten Bodewes May 23 '15 at 12:05
  • That said, many implementations may only offer DH using small primes. In that case the parameters should be recomputed - but it stays an implementation issue. – Maarten Bodewes May 23 '15 at 12:18
  • @MaartenBodewes: I also disagree with the text that lili added, so I reverted the edit. – Thomas Pornin May 23 '15 at 15:57
  • 3
    what about "logjam", doesn't that imply that we should use random primes, not standard ones? – Jasen Jul 14 '15 at 00:16