Why digital signatures needs different algorithm

Question

Why digital signatures uses algorithms such as DSA, ECDSA or RSA-PSS, and not just the RSA algorithm to encrypt the message hash with the private key? Is the choice more security or performance related and how?

Answer 1

When you use a mathematical primitive directly, it's often vulnerable to mathematical relationships. The raise-to-the-power-of-$d$-or-$e$-modulo-$n$ operation (sometimes called “textbook RSA” or “plain RSA”) has a simple mathematical structure so it's easy to find some of the transformations it allows. For example, suppose that you know that the signature of message $M_1$ is $S_1$ and the signature of $M_2$ is $S_2$. Then the signature of $M_1 \cdot M_2$ is $S_1 \cdot S_2$, because $S_1 S_2 = M_1^d M_2^d = (M_1 M_2)^d$ (all equalities are $\mod n$). You can forge a signature without knowing the private key. That's bad. And this is just one example.

Constructions such as PSS, and PKCS#1 v1.5 padding before it, avoid this kind of mathematical relationships. They encoded each message in such a way that there is no simple arithmetic transformation between valid encoded messages. PKCS#1 v1.5 does it by padding the message. For example, it avoids the attack above because $\mathrm{pad}(M_1) \cdot \mathrm{pad}(M_2)$ is not a valid padded message, so $S_1 \cdot S_2$ is not the signature of anything. PSS does it in a more complex way by masking the message and then padding the result.

So between plain RSA and the signature schemes RSASSA-PKCS1-v1_5 and RSASSA-PSS, the difference is security. Plain RSA as a signature schemes has many security holes, whereas RSASSA-PKCS1-v1_5 and RSASSA-PSS are both considered secure today. There are reasons to prefer PSS: v1.5 padding has known problems for encryption and there is a risk that someone will find a way to adapt the attack to signatures. Also v1.5 signature is tricky to implement correctly and even after two decades, some implementations don't get it right; PSS has fewer subtleties.

Between RSA-PSS, DSA and ECDSA, there is no particular security reason to choose one over the other. It mostly comes down to performance and ease of implementation. DSA is slower; it emerged when there were concerns about patents that might apply to RSA, but those patents have expired and DSA is dying out. Most new protocols favor ECDSA (or the newer variant EdDSA). ECDSA keys and signatures are smaller than RSA, which matters on embedded devices and ultra-low-bandwidth communication protocols. ECDSA signature is also significantly faster than RSA signature, but verification is slightly faster with RSA.