# Could someone explain to me, in simple terms, why we need a large order of group G for Diffie-Hellman and what does that mean?

For ElGamal encryption, safe prime $$p$$ is used such that $$p = 2q+1$$. However, can someone explain to me, in simple terms, why we would need, in this context, a large order of $$G$$ and how it will contribute in making $$g^{ab}$$ more secure such that $$a$$ and $$b$$ could be obtained via solving for discrete logarithm problem.

Based on Wikipedia, using $$p = 2q+1$$ implies $$G$$ has subgroups either of order $$2$$ or of order $$q$$ and that "$$g$$ is then sometimes chosen to generate the order-$$q$$ subgroup of $$G$$, rather than $$G$$ itself, so that the Legendre symbol of $$g^a$$ never reveals the low order bit of $$a$$. A protocol using such a choice is for example IKEv2" Also, wanted some further clarity on what this meant.

However, can someone explain to me in simple terms why we would need in this context a large order of G and how it will contribute in making g^ab more secure

Background (which you likely already know), with El Gamal, the ciphertext is the pair $$g^r, h^r \cdot m$$ (where $$h$$ is the public key and $$r$$ is a random value); if we could figure out what the value $$r$$ is, we could recover $$m$$ (because we assume we know the value $$h$$).

So, one of the things that we need to make sure is that, given the value $$g^r$$, we can't deduce what $$r$$ is; this is known as the "discrete logarithm problem".

With that in mind, here are some of the math behind the scene:

We define the "order of G" to be the smallest value $$k > 0$$ for which $$G^k = 1$$. This is interesting because $$G^r$$ can take on only $$k$$ different values, $$G^1, G^2, ..., G^{k-1}, G^k = 1$$. If we keep on going, we'll end up repeating, starting back at $$G^1$$, and so that doesn't help us any.

If there are only $$k$$ different values of $$r$$ that give us different values of $$G^r$$, then if $$k$$ is small, what the attacker could do is just try all $$k$$ different values of $$r$$ and see if one works; if he can do that, he can recover the correct value of $$r$$ [1]. Actually, it turns out that if the attacker uses just a give of cleverness, he can perform this search with about $$\sqrt{k}$$ multiplications; hence if we want to ensure that the attacker must perform $$2^{128}$$ operations to attack the system (which is the current standard for "that is beyond anyone's capability"), then we need a $$k$$ at least $$2^{256}$$.

And, it turns out that there's another observation to be made: if $$k$$ is composite and has a prime factor $$s$$, the attacker can compute $$r \bmod s$$ with $$\sqrt{s}$$ operations (by using the same sort of cleverness); this reduces the strength of such a $$G$$.

using p = 2q+1 denotes that order of G is is 2 and q and that "g is then sometimes chosen to generate the order q subgroup of G, rather than G, so that the Legendre symbol of g^a never reveals the low order bit of a.

This talks about a common method of dealing with the above attacks (not the only method, mind).

It turns out that if $$p = 2q+1$$ prime, where $$q$$ is prime as well, and if $$p \mod 8 = 7$$ (something that Wikipedia forgot to mention), then the value $$g=2$$ always has order $$q$$; that is a large prime. What's so special about 2? Well, it makes computing the exponentiation a bit easier (as multiplying by 2 modulo p is quite cheap).

And, when it talks about the Legendre symbol revealing something about $$g^a$$, well, that is a special purpose method of finding $$a \bmod 2$$; in essence, it is the same approach as I referenced above to recover $$a \bmod s$$ for $$s=2$$; it works only if the order of $$g$$ has 2 as a factor. Because we picked a $$g$$ that has an odd order $$q$$, it doesn't work.

[1]: You might ask: even if $$G^r$$ is the same, wouldn't it be possible that $$H^r$$ take on different values? It turns out that no, that can't happen - if we finds any value $$r$$ that gives him the observed value of $$G^r$$, he can use that to decrypt.

• Nit: you define order of an element such as the chosen generator $g$; order of the group $G$ is the number of elements, and for $Z_p^*$ this is $p-1$, so with $p=2q+1$ the order of any element (and equivalently the subgroup it generates) divides $2q$, and as you describe we prefer $q$. Even if $p \bmod 8 \neq 7$ there are order-q elements, just not 2. Feb 14, 2022 at 4:19
• @dave_thompson_085: actually, in the notation I used above, $G$ is a group element, not the group taken as a whole. Feb 14, 2022 at 5:19