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 was wondering if the prime numbers defined for use with Diffie-Hellman in RFC 3526 are more trustworthy than generating one's own, especially considering the recent Arjen Lenstra paper (Ron was wrong, Whit is right) which criticized the similarities detected in public keys and prime numbers across the Internet. Am I better off generating my own safe primes, or am I better off using the ones defined in RFC 3526?

share|improve this question

3 Answers 3

For Diffie-Hellman or any variants like Elgamal or DSA, you're better off using the established primes. It doesn't matter what primes you use, really, as long as they're prime.

The standard primes have had someone nod at them. If you generate your own prime and there's a problem (e.g. it's not really prime), then you're on your own and we will all laugh at you. Non-primes for DH are bad news, as you'll end up with subgroups, and other issues that mean you're not secure.

But more to the point, most of the public primes are public, they are not a security parameter (i.e. a secret). That's an even better reason not to use your own primes.

The primality testing we do is probabilistic. There's no actual guarantee that the number is prime. However, if you found a number that the usual gang of primality tests said was prime and it wasn't, that would be worthy of a paper, if not an assistant professorship.

For RSA, however, it matters that the two number you generate are secret more than they're prime. There are even three-prime variants of RSA. The problem in that paper was that they weren't secret, not that they weren't prime.

The real lesson we learned in this paper is to let your RNG warm up before you use it. Ironically, if the people with the badly-seeded RNGs had thrown in something with very low entropy like time(0), we wouldn't have had this problem because there would have been no easy way to find their crap primes through a simple test like a GCD.

share|improve this answer
    
Thank you! I was wondering - are the primes defined in the RFC special in any other way than being derived from Pi? Have they undergone any other testing? If so, what makes them safer or better studied? –  kaepora Mar 6 '12 at 2:16
3  
Actually, it's not actually true that "it doesn't matter what prime you use"; certain primes (say, primes where $p-1$ is smooth) are a really bad idea. In addition, it's a good to generate $p$ so that you know a large prime factor $q$, so that you can generate a generator for a subgroup that size. –  poncho Mar 6 '12 at 2:26
    
Thank you for the clarification, poncho. I was trying not to get into the details, but the gist of it. But you are correct, I should have been more weasely. –  Jon Callas Mar 14 '12 at 3:01
    
@JonCallas: Won't RSA generally fail entirely (i.e. generate public and private "keys" which don't complement each other) if numbers that are supposed to be prime, aren't? Construction of an RSA key pair requires that one knows the prime factorization of the modulus. It need not have exactly two primes, but all primes within it must be known. While one might theoretically find a pair of numbers which aren't prime but yield an encryption/decryption pair, the I think probability of that happening by chance is essentially zero. –  supercat 2 days ago

Generating your own group for Diffie-Hellman is not a tough issue; but it is somewhat expensive (it depends on the context, but a 25 MHz ARM device would not like to do it often) and it is not really needed: a good point of DH (and DSA) is that the group parameters can be shared between many users, with no ill effect on the confidentiality of their respective private keys.

For plain Diffie-Hellman, what you need is $p$, $q$ and $g$, such that:

  • $p$ is a big enough prime (2048 bits are more than enough nowadays);
  • $q$ is smaller, but still big enough (say 256 bits), prime value which divides $p-1$ ;
  • $g$ is a generator of a subgroup modulo $p$ with an order that is a multiple of $q$.

The DSA standard (FIPS 186-3) includes a rather detailed procedure for generating adequate group parameters (see annex A), which would be fine for DH too.

There is another side to the issue. While randomly chosen $p$, $q$ and $g$ are good for DH with overwhelming probability, it is possible to specially craft $p$, $q$ and $g$ values such that breaking discrete logarithm modulo $p$ (with generator $g$) would be easy (or at least easier). This can be a problem if your application entails producing the DH group parameters and having other people use them for their own key pairs. If you generate the group parameters but do not tell how you generated them (in a verifiable way), then other people could suspect you of having purposely made them weak. For completely usable group parameters which are immune to such suspicions, you need "nothing up my sleeve" numbers. Annex A of FIPS 186-3 describes the generation process in full details precisely so that it can be verified to be random. RFC 3526 uses $\pi$ for the same reasons.

Therefore, reusing published group parameters is a good idea, both for performance (no need to do the generation yourself, you can save on CPU and also code size) and for trust that can be put into the results by other people.

share|improve this answer
2  
Can you recommend some material about deliberately weak $p$,$q$,$g$ sets? –  CodesInChaos Dec 22 '12 at 21:08

There's nothing wrong with generating your own primes for DH, as long as you know what you're doing.

On the other hand, if you are a bit weak on number theory (or just glad that someone else has done the work, and had it double-checked), there's also nothing wrong with the modulii and generators in RFC 3526.

As for the paper, well, it chiefly noted that when RSA keys are being generated in practice, a common implementation flaw is a lack of entropy. While bad for RSA (because the entire security of RSA assumes that the keys can't be guessed), that's rather irrelevent for DH, because we're going to tell everyone what DH group we're using.

In fact, the DH groups in RFC 3526 have no entropy at all; they all are of the form:

$p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$

where $n$ is the number of bits within the modulus (1436, 2048, etc), and $i$ is the smallest nonnegative integer that makes both $p$ and $(p-1)/2$ prime.

There was no entropy used to generate these primes, hence the observation that some implementations may not have great entropy is irrelevent when selecting the modulii. Of course, entropy is critical when actually performing the DH operation, but that's true no matter which group you pick.

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.