0
$\begingroup$

In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime.

  • so my question is what extra benefit of using such a prime, what's new does it bring to the table.

  • and does using a regular prime make the problem much easier to solve(make an attack practical).

g^ab mod safe-prime is more secure than g^ab mod prime ?

$\endgroup$
5
$\begingroup$

In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime.

We don't have to; there are other options which achieve the same effect. However, it works.

so my question is what extra benefit of using such a prime, what's new does it bring to the table.

Well, a lot of the security of DH depends on the subgroup structure of $\mathbb{Z}_p^*$, and that depends on the factorization of $p-1$.

For any generator $g$ we use, the order of the subgroup $q$ (the smallest positivie value $q$ such that $g^q = 1 \bmod p$) satisfies $p-1 = h \cdot q$, for some integer $h$.

In addition, we generally prefer working with a prime subgroup, that is, where $q$ is a prime value. That's because if $q$ is composite, that is, $q = r \cdot s$, then given $g^x \bmod n$, we can recover the value $x \bmod r$ in $O( \sqrt{r} )$ time; if $r$ is not large, this leaks more information that we'd care for.

Thirdly, there is a invalid key share attack possible if you reuse DH public keys (which sometimes we do). That is, if $h$ has a moderate factor $t$, then by issuing an invalid key share, the attacker can rederive $x \bmod t$ (where $x$ is your private value). This attack can be detected, but the detection is expensive, and so it is often not done (even when you do reuse key shares).

So, with all that:

and does using a regular prime make the problem much easier to solve(make an attack practical).

What do you mean by a "regular prime"? Do you mean just picking a random prime $p$ and random generator $g$? Well, while the order of $g$ is probably large, it is likely to be composite, and will often have moderate factors; these factors (if present) would allow someone listening in to recover some information about your private value (and if you use one that's not full length, it may be enough to recover the entire value). However, possibly this is not the case; however you're taking a gamble here.

In contrast, if we have a safe prime, well, we're safe. We generally use a prime that's in the "quadratic residue" subgroup, that is, the one where every member (other than 1) has order $(p-1)/2$, which is prime. And, if we happen to pick another generator (other than 1 or $p-1$), the only other subgroup is the one of size $p-1$, which means that the attacker can find $x \bmod 2$, but nothing else about $x$.

In addition, the invalid key share attack can only recover $x \bmod 2$ (because $h=2$), and so even if we reuse key shares, that's not a concern.

Now, there are other ways to make sure that we work within a prime-sized subgroup. On the other hand, safe primes have the property that we can have $g=2$; these other methods generally require larger $g$ values (which makes part of the computation more expensive).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Since the question seems to be quite basic, I think it would be beneficial to explicitly link to the Pohlig Hellman algorithm, $\endgroup$ – tylo Aug 28 at 23:08
  • $\begingroup$ I also see use for a link about that invalid key share attack on Diffie-Hellman key exchange, which rings no bell in my mind. $\endgroup$ – fgrieu Aug 29 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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