In traditional DH one chooses two shared parameters: a large prime $p$ and base $g$, which is primitive root $\bmod p$. Suppose that the generation algorithm is broken and $g$ generates only a subgroup (the group with fewer elements than the number of coprimes to $p$), what could be the possible attack? what's the complexity ? are there any real-world examples of attacking wrong DH parameters (implementation)?

  • $\begingroup$ if $g$ generates only a subgroup, then it can be attacked by using small subgroup, only given that the protocol doesn't verify the validation of elements. you can refer to this link. In this page, i give a example of small subgroup attack. $\endgroup$
    – T.B
    Sep 1, 2013 at 14:20

1 Answer 1


As far as we know, Diffie-Hellman is secure as long as the subgroup generated by g is impervious to discrete logarithm. When working modulo a prime p, this is achieved when the following are met:

  • p is large enough (at least 1024 bits, go to 2048 bits for a bigger safety margin) and is not a "special form" prime (a randomly generated prime will be fine with overwhelming probability).

  • the subgroup generated by g has an order t which is such that there is at least one prime factor q of t which is "big enough", i.e. more than 2k bits, when k is the "security level" (e.g. to have at least 80-bit security, q should be at least 160 bits).

Note that it is in no way necessary that g generates all non-zero integers modulo p. It is fine if it generates a strict subgroup, as long as that subgroup cannot be split into several subgroups, each being very small. This is the essence of the necessity of at least one medium-sized prime q in the factorization of the subgroup order t.

The order of g, called t above, is a divisor of p-1. With overwhelming probability, a randomly generated g will imply an order which will not be much smaller than p. Indeed, there is only one chance in a billion to hit a g which implies an order t smaller than p by more than 30 bits (because 230 is about one billion). It is preposterous to imagine that a random g, modulo a 1024-bit prime p, will imply a subgroup order smaller than 900 bits.

The biggest prime factor of a random integer of n bits will have length, on average, about 0.3*n. It is extremely improbable that the biggest prime factor will be much shorter than that.

Bottom-line is that a purely random prime p (of at least 1024 bits) and a purely random g modulo p will be fine. To get bad DH parameters, you have to do it on purpose.

However, some people are arguing for ensuring that p and g are fine with "stronger" arguments than the probabilistic properties explained above (mathematically, these probabilities are extremely strong, but convincing people is not only about mathematics, but also about psychology). First, p will be generated as a "nothing up my sleeve" number with a completely open and fully described pseudo-random generator. See appendix A of FIPS 186-4 for an illustration (this is for DSA, but it may apply to DH as well). Then there are two ways for g:

  • The smaller prime q could be generated first; then p is produced randomly as p = qr + 1 for random r of the right size, until a prime p is reached. Then a random h modulo p is produced, and g is set to g = h(p-1)/q mod p. This yields either g = 1 (with extremely small probability) or a g with an order exactly equal to q, which is fine.

  • p could be generated as a so-called "safe prime". I.e. random odd integers u are generated until both u and p = 2u + 1 are both prime. Then set g = 2: the order of g is then necessarily equal to u or 2u, and both are fine. Generating a safe prime is computationally expensive, but having g = 2 yields a slight performance boost when doing the actual Diffie-Hellman.

When the whole process is fully described, as in Appendix A of FIPS 186-4, it can be verified, which guarantees against DH parameters which have been made weak on purpose.

  • $\begingroup$ Actually, I would have to disagree that, as long as you pick your DH values randomly, you're probably safe. If your value $g$ has an order $n$ with a small factor $q$, then the attacker can compute the secret exponents modulo $q$. If you pick $g$ and $p$ totally at random, there's a nonnegliable probability that $n$ will have a number of small factors; and hence you'll leak a nontrivial part of the secret. Yes, if you make the secret exponents larger to compensate -- you have to know to do so. $\endgroup$
    – poncho
    Apr 16, 2015 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.