5
$\begingroup$

I am having trouble coming up with a use case for RSA or DSA. It appears that ECC is better in every way.

Is this true?

I am looking for cases where RSA/DSA is superior to ECC, not where it is used for historical reasons.

$\endgroup$
2
  • 3
    $\begingroup$ Tempted to close as dupe of this question. Is there anything that is not answered in the answers there? If so, you should edit to clarify. $\endgroup$
    – otus
    Feb 24 '16 at 8:10
  • $\begingroup$ By themselves, elliptic curves are useless. It is when certain algorithms are done over elliptic curves that they become useful. ECC is not a replacement for DSA, but ECDSA is. $\endgroup$
    – Melab
    Feb 26 '16 at 6:53
13
$\begingroup$

There are three use cases where RSA beats common ECC algorithms, such as ECDSA:

  1. Signature with verification frequent or/and by low-power devices or/and where the verification code needs to be small. The verification cost of $n$-bit RSA with usual public exponents is $O(n^2)$, but the verification cost of ECC-based signatures is $O(n^3)$ (using usual algorithms). Together with simpler math, that's why RSA can be way over 10 times faster for signature verification at usual security levels, even though it must use a larger $n$ for equivalent security level. RSA verification also requires significantly less code than ECC computations, which makes it attractive, for example, in ROM code where space is expensive and a bug can't be patched.

  2. Similarly, encryption by low-power devices or/and with decryption comparatively rare.

  3. Need to minimize the size overhead of adding a signature; using signature with message recovery, that can be 34 bytes for RSA (using SHA-256 hash, ISO 9796-2 mode 3 or the deprecated mode 1, for messages at least 222 bytes before signature at the 2048-bit security level), versus 64 bytes for ECDSA for comparable security.

RSA is thus a good choice (and indeed still the dominant one, I believe) for signing public-key certificates; beside inertia, in the internet domain that's mostly for reason 1 (certificates are verified often), but in the Smart Card and payment industry reason 3 adds up.

Additional arguments for RSA (vs ECC) are

  • RSA was first there / is the most time-proven, and became an industry standard.
  • Simplicity. RSA signature verification is much easier to code, and get right, than ECDSA signature verification.
  • RSA has long been clearly patent-free. But that now applies to ECDSA as well, and arguably applied all along and indisputably since August 2014, at least for curves in a prime field; e.g. ECDSA on secp256r1 and EdDSA on Curve25519 are patent unencumbered.
  • Perhaps (but see these comments) slightly more quantum resilience; that is, at comparable level of resistance versus non-quantum attacks, RSA arguably would fall after ECC if it ever emerged quantum computers usable for cryptanalysis; see this other answer and section 5.4 of its source; note that Koblitz and Menezes are not making any strong statement, rather, their intro is (emphasis mine):

We next examine some conjectures about the NSA’s motives in its PQC announcement (..)
The NSA believes that RSA-3072 is much more quantum-resistant than ECC-256 and even ECC-384. (..)

Note: this answer does not touch use cases where ECC is preferable, or its virtues.

$\endgroup$
5
  • 3
    $\begingroup$ Case 2 could occur in a sensor grid scenario where the encryption is on embedded systems but decryption is on a much more powerful server. $\endgroup$
    – Demi
    Feb 24 '16 at 18:26
  • $\begingroup$ OTOH, using RSA signature and key generation on smart card devices really can bog things down, and using the more accpted / proliferate RSA PKCS#1 extends the signature size to less acceptable levels. $\endgroup$
    – Maarten Bodewes
    Feb 28 '16 at 20:02
  • 2
    $\begingroup$ I think citing improved "quantum resilience" is a bit irresponsible, since both algorithms should be considered utterly broken in the presence of scalable quantum computing. While there may be a gap, the authors themselves suggest "It is not likely that the gap between quantum cryptanalysis of a 384-bit key and a 3072-bit key will be great enough to serve as a basis for a cryptographic strategy." This should be interpreted as quantum resilience NOT being a reason to use RSA over ECC algorithms. $\endgroup$
    – bkjvbx
    Oct 18 '16 at 9:40
  • 1
    $\begingroup$ @bkjvbx I interpret this as “yes, both will fall to a quantum computer, but ECDSA will fall first, which might give a bit more warning to switch.” Of course, one should be switching to post-quantum schemes ASAP, but in some cases (such as code signing), all that matters is that I have switched to a post-quantum scheme before the original scheme is broken. As long as RSA holds out long enough for a successor to be deployed, software signatures based on it are safe. $\endgroup$
    – Demi
    Dec 11 '21 at 6:46
  • $\begingroup$ Note that an EC Schnorr signature only requires 48 bytes, since it is unnecessary for the hash to produce a challenge greater than 128 bits. Signing keypair is (x, xG). Signature is (c,r), VER is c =?= hash_to_128_bits(rG + cX || m), SIG is choose random k, r = c - kx. c = hash_to_128_bits(kG || m). $\endgroup$
    – knaccc
    Dec 11 '21 at 11:24
2
$\begingroup$

If practical quantum computers become a reality, the larger bitlengths of RSA keys would make them more quantum-resistant than their ECC counterparts. See section 5.4 of this Koblitz & Menezes paper

$\endgroup$
1
  • $\begingroup$ What about Ed448? $\endgroup$
    – Zimba
    Sep 21 '20 at 16:57

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.