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

  • 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?
  • Tom Leek

    Tom Leek Correct answer

    7 years ago

    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 gr = 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 ga mod p and gb 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 22k 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 = st 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".

    If the DDH must hold (for, say, ElGamal) must we find a "big" generator, or, like in regular DH if we're using a safe prime P can we just pick 2 or 5 as `g`?

    _at least 1024 bits_ This may not be true anymore.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM