0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you so much, if only I knew this yesterday! $\endgroup$
    – Jonas Grønbek
    Commented May 24, 2020 at 13:05
  • $\begingroup$ 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? $\endgroup$
    – Jonas Grønbek
    Commented May 30, 2020 at 16:51
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Commented May 30, 2020 at 17:52
  • $\begingroup$ I don’t have the abstraction required to understand why “leakage” leakage is a problem. I really samt a concrete example where a leak can be used to compromising something $\endgroup$
    – Jonas Grønbek
    Commented May 30, 2020 at 17:54

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.