What is the difference between Diffie Hellman generator 2 and 5?

Question

Generating Diffie Hellman parameters in OpenSSL can be done as follows:

$ openssl dhparam -out dh2048.pem 2048
Generating DH parameters, 2048 bit long safe prime, generator 2
This is going to take a long time 
[...]

The "generator 2" caught my attention there. It appears I can choose between generator 2 and 5 as indicated by the manpage (man dhparam):

-2, -5
   The generator to use, either 2 or 5. 2 is the default. If present then the input file
   is ignored and parameters are generated instead.

• What is generator 2 and 5?
• How does choosing 5 instead of 2 affect the security?
• Is this specific to OpenSSL?

Answer 1

Diffie-Hellman works in a subgroup of integers modulo a prime p. Namely, you have a generator g, which is a conventional integer modulo p. That generator has an order r which is the smallest positive integer such that g^r = 1 mod p. The two systems who engage in DH choose private keys a and b respectively as integers in a given range, and the corresponding DH public keys (which they exchange over the wire) are g^a mod p and g^b mod p.

DH is secure as long as:

• p is "proper": big enough (at least 1024 bits) and not produced with a "special structure" which makes discrete logarithm easy. A randomly generated prime of the right size will be fine.
• The biggest prime divisor of r has size at least 2k bits, when targeting a security level of "k bits". Basically, the biggest prime divisor of r should be a prime integer of size at least 160 bits (200 bits or more would be preferred by today's standards).
• The DH private keys are generated in a range of size at least 2^2k or so. Basically, a and b should also be 2k-bit integers.

The exact value of the generator g does not matter, as long as both parties use the same value. It can be shown that if someone can compute discrete logarithm relatively to a generator g, he can compute it as easily relatively to any generator g' of the same subgroup. Thus, what matters is the subgroup order, not the generator. You can use 2 or 5, it won't change security.

Using a short generator has some (slight) benefits for performance, which is why they are preferred. The performance difference between 2 and 5 will be negligible, though. In some protocols, the generator is agreed upon at the protocol level, i.e. not transmitted over the wire; it is hardcoded in both systems. Some protocols thus mandate the use of 2, others want to use 5, out of historical and traditional reasons. OpenSSL, as a general-purpose library, can generate parameters for both cases.

There are details, though. Making sure that the chosen generator indeed has an order with a big enough prime divisor can be tricky. By default, openssl dhparam will generate a so-called "safe prime", i.e. it generates random primes q until it find one such that p = 2q+1 is also a prime integer. The order of any g modulo q is always a divisor of p-1. Thus, by using a safe prime, OpenSSL is guaranteed that the order r of any generator g in the 2..p-2 range (in particular 2 and 5) will be equal to either q or 2q, thus always a multiple of q, which is a big enough prime.

If OpenSSL generated a random p without making sure that it was a "safe prime", then the actual order of g = 2 or 5 would be hard to compute exactly (it would involve factoring p-1, which is expensive).

In some non-DH contexts, namely the DSA signature algorithm, one must have a DH-like subgroup such that the order of the generator is exactly equal to a given non-too-big prime q, instead of merely being a multiple of q. In that case, OpenSSL (with the -dsaparam command-line switch) will first generate q, then p = qt + 1 for random values of t until a prime is found; and the generator will be obtained by taking a random s modulo p and computing g = s^t modulo p (this necessarily yields either 1 or an integer of order exactly q). When producing DSA parameters, the generator cannot easily (or at all) be forced to be a specific small integer like 2 or 5. For DSA, the generator is "big".

Answer 2

What is generator 2 and 5?

Understanding this requires some amount of mathematical background. Diffie-Hellman operates on cyclic groups. These groups all have in common that there is at least one generator, i.e. an element that can be used to generate all other elements of the group.

Let's look at an example:

Z_11*: Set of integers i = 0,1,...,10 for which gcd(i,11) = 1. This is an abelian group under multiplication modulo 11.

Generator: a = 2

a^1  =           2 mod 11,
a^2  =           4 mod 11,
a^3  =           8 mod 11,
a^4  = (  16 =)  5 mod 11, 
a^5  = (  32 =) 10 mod 11,
a^6  = (  64 =)  9 mod 11,
a^7  = ( 128 =)  7 mod 11,
a^8  = ( 256 =)  3 mod 11,
a^9  = ( 512 =)  6 mod 11,
a^10 = (1024 =)  1 mod 11

As you can see, we generated the whole group, i.e. we've got each element as result. Note however, that this will work on all kind of groups, and is not limited to multiplicative group of integers modulo p.

How does choosing 5 instead of 2 affect the security?

No, the Diffie-Hellman problem is all about the size of the cyclic group, not about the element(s) that generate the group. So when both elements are generators for a group, it doesn't make a difference. Choosing 2 as generator has a couple of advantages, though, because you can implement the underlying algorithms more efficiently.

Personally I wouldn't change the default here, unless there is a very good reason to. This is obviously not the case, otherwise you wouldn't have to ask ;).

Is this specific to OpenSSL?

No, this follows from the mathematics of cyclic groups itself.