3
$\begingroup$

The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key. This multiple encryptions is a pretty expensive process since public key encryption is so resource intensive.

On the other hand, the RSA-based digital signature algorithm encrypts the hash using only the senders private key, which is a much cheaper operation.

Under what circumstances would I need to use the expensive DSA as opposed to using the much faster RSA?

$\endgroup$
  • 2
    $\begingroup$ (EC)DSA doesn't use the receivers public key, in fact the receiver need not even have a key pair, all they need are the senders public key to verify the signature. $\endgroup$ – puzzlepalace Jul 14 '16 at 19:19
  • 3
    $\begingroup$ ECDSA (DSA over elliptic curves) actually is faster than RSA. $\endgroup$ – SEJPM Jul 14 '16 at 19:19
  • $\begingroup$ Isnt (EC)DSA different in operation from the more traditional DSA? $\endgroup$ – Minaj Jul 14 '16 at 19:20
  • 1
    $\begingroup$ No, the basic signature / verification algorithms for both are the same, the differences are in what the group operations are (e.g. modular exponentiation vs. point multiplication) since DSA is over a finite field and ECDSA is over an elliptic curve. $\endgroup$ – puzzlepalace Jul 14 '16 at 19:24
  • 4
    $\begingroup$ DSA signatures are shorter, at a 128 bit security level you have 512 bit signatures, instead of about 3000 bits with RSA. $\endgroup$ – CodesInChaos Jul 14 '16 at 19:28
13
$\begingroup$

The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key.

Huh? I see two problems with the above statement;

  • "Encryption"; using the word encryption implies that there's a way somehow to decrypt it. However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the hash.

  • "using ... the receiver's public key"; the signature operation most certainly does use the signer's private key, but it doesn't use any key (public or private) from the receiver.

On the other hand the RSA-based digital signature algorithm encrypts the hash using only the senders private key, which is a much cheaper operation.

Not necessarily; if we're talking about the standard DSA operation, the expensive operation is a modular exponentiation of the generator over a (perhaps) 256 bit random exponent modulo the prime; for RSA, the expensive operation (I'm assuming CRT) is two modular exponentiations of arbitrary values modulo primes half in length of the key size. I believe that you can implement the DSA operation (which, using precomputed tables, would take perhaps 50 multiplications modulo a 2048 bit prime) considerably faster than you can the RSA operation (which might take perhaps 2000+ multiplications modulo 1024 bit primes)

In addition, with DSA, you can potentially perform this computation before you learn the value you're signing; if you can do this in time where you would otherwise be idle, you can make the signing operation very cheap indeed.

And, if we're talking about DSA over Elliptic Curves, that is, ECDSA, the balance tilts even more radically towards ECDSA.

Where RSA shines is the signature verification operation; there's, it's considerably faster than (EC)DSA.

Under what circumstances would I need to use the expensive DSA as opposed to using the much faster RSA?

Quite apart from your mischaracterization of DSA as expensive and RSA as cheap, actually, straight DSA is fairly rarely used in practice. ECDSA (and relatives, such as EdDSA) are becoming more popular, in part because it is cheaper...

$\endgroup$
  • 2
    $\begingroup$ "However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the hash...." Did you use this statement strictly in reference to DSA? $\endgroup$ – Minaj Jul 14 '16 at 19:57
  • $\begingroup$ "Where RSA shines is the signature verification operation; there's, it's considerably faster than (EC)DSA." Why exactly is signature verification fast? small exponent? $\endgroup$ – Minaj Jul 14 '16 at 19:58
  • 1
    $\begingroup$ @Minaj: "However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the hash...."; because a DSA signature consists of $g^k$ and $k^{-1} (H + xg^k)$; without $k$, you can't derive $H$ from the latter, and deriving $k$ from the former is a Hard Problem. $\endgroup$ – poncho Jul 14 '16 at 20:07
  • 1
    $\begingroup$ @poncho That's in DSA though. I believe what Minaj was asking was whether that statement is true for RSA. I was under the impressing it is not, signatures in RSA are "decrypted" to form the original hash as part of the signature verification process. $\endgroup$ – Ajedi32 Jul 14 '16 at 21:21
  • 3
    $\begingroup$ @Ajedi32: with RSA, one could recover the hash (assuming that the padding operation allows it; I believe all the commons ones will). On the other hand, I still don't like calling it "encryption", but for subtler reasons; the security policies we need during a signature operation really aren't the same as we need during a true encryption operation. $\endgroup$ – poncho Jul 14 '16 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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