10
$\begingroup$

Protocols that use $\mathbb{Z}_{p}^*$ arithmetic often choose $p$ to be a safe prime ($p = 2q + 1$, for prime $q$) or to have the Schnorr group form ($p = rq + 1$, for prime $q$). I understand that the reason for this is to prevent the Pohlig–Hellman algorithm.

It appears that both are safe as long as $q$ is big enough. However, from what I've seen, safe primes are commonly used for Diffie-Hellman, while Schnorr group primes are used for DSA. (For example, the dhparam and dsaparam OpenSSL commands).

My question is: what is the reason for that? I see that Schnorr group primes are more efficient, since $q$ is smaller, making exponentiations faster. But if that is the case, why it seems to be avoided in Diffie-Hellman? Is it safe to use Diffie-Hellman with Schnorr group primes, or DSA with safe primes?

(This question is partially included in ElGamal and Schnorr groups, but was not answered there)

$\endgroup$
1

1 Answer 1

6
$\begingroup$

Is it safe to use Diffie-Hellman with Schnorr group primes, or DSA with safe primes?

Safe, yes; efficient, no.

For DSA, that signature algorithm includes a clever trick that reduces the size of the signature to twice the size of the subgroup (the size of $q$). Because of this, we want to reduce the size of the subgroup as much as possible (without cutting into security). You could use a safe prime, but that means that the signature would end up being much larger than required.

For DH, there is no corresponding clever trick; the key share is the size of $p$. However, there are two things which allow a performance difference:

  • We use use a small $g$ (often $g=2$); such a $g$ has order $q$, and so works perfectly well. Such a small $g$ makes the initial modular exponentiation cheaper. In contrast, with a Schnorr group, you have to use the $g$ which came with the group (which will be larger)

  • We can safely reuse private exponents. With a safe-prime, if someone gave us a bogus key share, they could deduce the lsbit of our private exponent, but nothing else; hence, the leakage is minimal. In contrast, with a Schnorr group, they can deduce our private exponent modulo $s$ for every small $s$ which is a factor of $r$ (where $p = rq+1$ is the Schnorr group); you could defend against this by either selecting $r$ is 2 times a prime (I haven't heard of someone doing that, but they could), or by raising the key share to the power of $q$ (which would eliminate any potential performance gain by reusing the private exponent).

You state that Schnorr groups are more efficient because $q$ is smaller; that is not true, because with a safe prime, there is no reason to select your private exponent randomly from the entire range $[1, q-1]$; you can select from a smaller range (for example, the range you would use if you used a Schnorr group); there's no known discrete log method that could use the additional information.

$\endgroup$
1
  • $\begingroup$ Great answer, very clear explanation of complicated concepts. $\endgroup$
    – JFreeman
    Oct 24, 2022 at 0:18

Your Answer

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

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