9
$\begingroup$

Signature algorithms with elliptic curves have smaller output sizes compared to RSA for the same level of security.

What about the processing time to generate a signature ?

I've seen figures giving the advantage to RSA. That seems curious.

Leaving aside the implementation aspects, what could justify (in terms of number of operations) the fact that ECDSA produces signatures faster than RSA (or vice versa) ?

$\endgroup$
1
  • $\begingroup$ "Signature algorithms with elliptic curves have smaller output sizes compared to RSA for the same level of security". That's true for signature with appendix. But if size matters, we can use RSA signature with message recovery and for the same level of security, the size of the overall signed message is slightly smaller with RSA than with most EC signature schemes, except for very small payload. For example, a 350-byte payload becomes a 384-byte signed message when signed per ISO/IEC 9796-2 scheme 3 with RSA-3072 and SHA-256, and a 414-byte signed message when signed per ECDSA P-256. $\endgroup$
    – fgrieu
    Jan 28, 2019 at 12:17

1 Answer 1

18
$\begingroup$

ECDSA should in general create signatures faster than RSA for the same cryptographic strength if you just look at the mathematics. In the end the modular exponentiation is performed for smaller numbers. However, ECDSA depends on a random number generator, so ECDSA speeds may be slower if the random number generator blocks for any reason (and not using a good random number generator may compromise the ECDSA private key). The RSA PSS signature scheme also requires the use of random numbers, negating this performance advantage for RSA for this particular padding scheme.

[EDIT: well, the use of a random salt in RSA / PSS is at least the default option, and many implementations won't allow you to use an empty salt to make the scheme deterministic. RSA / PKCS#1 v1.5 padding for signature generation is fully deterministic and could be used instead; it doesn't come with a security proof like PSS does, but it hasn't been broken either]

RSA is generally much faster for signature verification as verification is performed using the public key. If a small exponents such as F4 (65537 or 10001 in hexadecimals) are used then RSA is generally faster than ECDSA, as only a minimum of modular multiplications is necessary.

The time required for RSA operations with the private key quickly rises for larger security strengths. ECDSA times also rise, but at a much slower rate.

ECC is much much faster than RSA for key generation. Finding large primes for RSA is a tough job even for current CPU's given a high enough key size.


Most RSA libraries have been around for a long time, are used much more often and are therefore more likely to have been optimized. So an RSA implementation may be faster than an equivalent ECDSA implementation (for small key sizes). ECC, in general, is a more complex algorithm to implement - but not necessarily to optimize, as CodesInChaos points out below.

Be aware that real world results will rely heavily on the speed of the implementations used. Note that the security level of such libraries also differs wildly, and selecting a crypto library just based on performance is not a good idea.

$\endgroup$
1
  • 2
    $\begingroup$ Concerning optimized implementations, ECC has one big advantage: A fixed modulus which usually has been chosen to allow efficient reductions. Certain academics like publishing papers about their world record speed ECC implementations, so ECC has seen quite a bit of optimization work targeting modern CPUs. ECC is more complex mathematically, but I think it's actually easier to write a fast ECC implementation compared to a fast RSA implementation. $\endgroup$ May 28, 2014 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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