# Why digital signatures needs different algorithm

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?

• I'm sure this has been asked before (but still searching). Anyways, one reason of many: In RSA it is methematically possible to use either key to encrypt. But that doesn't mean all asymmetric encryption algos are like that. ... Don't be confused by the similarity of encrypting and signing in RSA - in general they are completely different things. – deviantfan Oct 21 '18 at 9:32

## 2 Answers

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.

As Kyoto said, most of it comes down to preference with some algorithms being faster than others.

On top of that, you should know that the most commonly used one (RSA) is vulnerable to Quantum Computing. This means that other algorithms to replace are being looked at but so far, there doesn't seem to be one that we have found/created that can replace RSA while still retaining the speed of decryption/encryption/keygeneration and while keeping the size of the output low. This is not as bad of a problem for digital signatures as it is for the implementation of TLS, where every byte sent counts and increases the amount of work the server has to do.

• RSA vs RSA-PSS is not a matter of performance, it's a matter of security. As for the rest of your answer, elliptic curves are just as likely to be vulnerable to quantum computing as RSA. But it's still science fiction. – Gilles Oct 22 '18 at 7:12
• @Gilles You are misreading the question. The question says 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? He is asking why other people use different algorithms than RSA, not why people use RSA. You even contradict this with "there is no particular security reason to choose one over the other. It mostly comes down to performance and ease of implementation." And Quantum Computing is not science fiction. Last week IBM released their study demonstrating its advantage over current tech. – hemlck Oct 22 '18 at 18:25
• The question asks, in the very part you quoted, “Why digital signatures uses algorithms such as (…) RSA-PSS, and not just the RSA algorithm”. Quantum computing isn't science fiction, but using it to break crypto still is. It's plausible science fiction, to be sure, but it isn't current technology, and post-quantum algorithms aren't ready for use yet. – Gilles Oct 22 '18 at 18:33