When to use safe prime or Schnorr group

Question

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)

Answer 1

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.