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".
Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.Sign up to join this community
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".