# Difference between DSA and RSA in terms of signature generation

For DSA, if the same message is signed multiple times on different occasions, the signatures will differ because the random value k is generated for each signature. This is not true of RSA signatures. What is the practical implication of this difference?

• "This is not true of RSA signatures."; depends on the RSA padding method; for PSS signatures, they would be different Commented Aug 17, 2022 at 2:41
• This RSA is basic RSA without any padding Commented Aug 17, 2022 at 2:48
• RSA without padding is insecure, so 'practically' that signature is useless. Deterministic padding as in PKCS1-v1_5 can be secure, although it does not have as good a proof as PSS. Conversely DSA (both classic/FF if anyone still uses it and ECDSA) can use a deterministic but unpredictable and unique nonce, see RFC6979 crypto.stackexchange.com/questions/66190 crypto.stackexchange.com/questions/59876 crypto.stackexchange.com/questions/851 crypto.stackexchange.com/questions/20538 Commented Aug 18, 2022 at 0:07

The question asks practical implication of DSA producing (most probably) different signatures if signing the same message with a given private key, compared to some variants of RSA (textbook, common RSASSA-PKCS1-v1_5, RSA-FDH) which signature is a mathematical function of message, private key, and other fixed parameters.

I can think of:

• It's not possible to devise a Known Answer Test of a signature device.
• Implementation of the signature algorithm can leak information thru the value of a valid signature, by accident or deliberately. For example, with DSA, the signer could compute two signatures, release the first when the low bit of it's $$r$$ matches the bit at index $$s\bmod N$$ in the private key, and otherwise release the second signature. In the long run this allows to find the private key. Something similar is impossible with RSASSA-PKCS1-v1_5.

Notes:

1. Not all RSA-based signature schemes have a signature that's a function of the message and private key. A counterexample is RSASSA-PSS. The randomness was introduced to ease a strong security reduction to the RSA problem.
2. Having a signature that's a function of the message and private key is not equivalent to having a deterministic signing algorithm:
• Often, in order to resist side-channel attacks, the implementation of a function internally uses randomness. E.g. in in order to compute an RSA signature $$s:=m^d\bmod n$$ where $$m$$ is the message representative, $$(n,d)$$ the private key, and $$(n,e)$$ the public key, an implementation could draw random $$u$$, $$v$$, $$w$$ then compute $$s:=((m\,u)^{d-v}\bmod(n\,w))\,(u^e\bmod n)\,((m\,u)^v\bmod n)\bmod n$$
• In the other direction: Merkle signature has a deterministic signing algorithm but has an internal state, so that signing the same message twice (most probably) produces different signatures.
3. It's easy to modify DSA, or any other stateless signature scheme, so that it's signature is a function of the message and private key: replace any internal source of randomness by a PRNG seeded with (a hash of) the message and private key. EdDSA uses that principle.