# Diffie-Hellman what is the subgroup

I am trying to understand the safety precautions regarding the variables used in Diffie-Hellman and I was refered to this post answer Does the generator size matter in Diffie-Hellman?.

In more details: for DH, we use a subgroup of size q of the integers modulo p (a big prime) with the multiplication as group operation. q should be a prime of length at least 2n bits for a 2n security level (or, at least, q should have a prime divisor of at least 2n bits). Typical parameter sizes are 160 bits for q and 1024 bits for p, or 256 bits for q and 2048 bits for p. The generator g is an element of order q.

What is meant by for DH, we use a subgroup of size q of the integers modulo p I assume the group is the potential congruences of $$\mod p$$, but what is the subgroup. Since the generator should be a primitive root of p doesn't that mean that the group is $$[1,p-1]$$? This leads me to believe that $$q = p-1$$. However this makes no sense when considering the following sentence q should be a prime of length at least 2n bits for a 2n security level (or, at least, q should have a prime divisor of at least 2n bits). I am not sure what the n variable symbolizes?

Since the generator should be a primitive root of p
Well, here's your misunderstanding; the generator $$g$$ needn't generate the entire group $$\mathbb{Z}^*_p$$; instead, it can generate a proper subgroup (and in most cases, we select such a subgroup).
Here's the issue, if $$h$$ is a factor of the size of the group generated by $$g$$, then given $$g^x \bmod p$$, we can compute $$h \bmod n$$ in $$O(\sqrt h)$$ time. If $$g$$ generates the entire group, well, its size will be $$p-1$$, which always has a factor of 2 (assuming $$p>2$$), and so we'd be giving away $$x \bmod 2$$ for free.
In contrast, if the size of the subgroup is a large prime (which implies that it is not the entire group), then the above observation doesn't give the attacker any advantage; the only factors of the subgroup size are 1 (which doesn't tell the attacker anything) and the large subgroup size itself (which is too large to make $$O(\sqrt{h})$$ time feasible.
• How could $$x \mod 2$$ be used to compromise a secret value? If we have prime 761, and the generator as 6. Then our subgroup is of order 760. If we use $$6^5 \mod 761$$ how is $$5 \mod 2$$ going to give us any information about 5 being the secret value? – Jonas Grønbek May 30 '20 at 16:51
• @JonasGrønbek: from just $x \bmod 2$ against the size of modulii we use in practice, not much. However, a) we generally prefer not leaking anything, and b) of $p-1$ has other small factors, that increases the leakage. – poncho May 30 '20 at 17:52