18
$\begingroup$

RSA is both an asymmetric encryption algorithm and a digital signature algorithm. However, in recent years, many cryptographic protocols (TLS, for example) have moved away from the use of RSA to instead prefer ECC because of forward secrecy.

So, my question is, do we still need RSA? Is there any situation where it cannot be replaced by an ECC scheme instead?

More specifically, if the answer to the above is no, are there any circumstances in which RSA is better suited than the ECC counterpart? Why is it still in use from a practical point of view?

$\endgroup$
22
$\begingroup$

Summary: ECC+symmetric algorithms can do almost anything RSA+symmetric algorithms commonly do (plus forward secrecy where RSA struggles). But RSA is often preferred, sometime rightly so, in particular due to it's superior performance for the public-key side.


At common security levels, the public-key RSA operation (used for signature verification, and on the encryption side of public-key encryption) remains significantly more compute-efficient than anything ECC-based has to offer. That's an advantage in some applications, including:

  • For the signature of a digital certificate: it can be verified many millions times in its active lifetime, when it is generated only once; the cost of its signature can be neglected entirely, while the power or/and time saving by the users of the certificate becomes sizable. That is part of why CAs typically use RSA public/private key pairs.
  • For data (including code) signature verification by underpowered devices (IoT).
  • For asymmetric encryption by underpowered devices (IoT), complemented by symmetric crypto for large ciphertext.

To illustrate: with $e=3$, on a CPU with 32×32→64-bit multiplication, a straightforward RSA signature verification with $n$-bit public modulus uses about $4(n/32)^2$ multiplications (e.g. <17k multiplications for $n=2048$), while ECC-based crypto in field $\Bbb Z_p$ with $n$-bit $p$ requires about $k\,n(n/32)^2$ multiplications for some integer $k$ typically 12 or more (e.g. 200k multiplications for $n=256$). In practice, even when using RSA with $e=65537$ (like 8 times slower than $e=3$) perhaps due to diktat by authorities, RSA typically keeps a sizable advantage because it is easier to optimize.


Also, RSA signature with message recovery is sometime what minimizes the size overhead of signing. E.g. for a 350-octet payload to be conveyed signed, the signed message is

  • 384-octet with RSA-3072 per ISO/IEC 9796-2 scheme 3 and SHA-256
  • 398-octet with ECPVS (ANS X9.92-1) and SHA-256
  • 414-octet with ECDSA/EdDSA and SHA-256

Thus when size is a hard limit, RSA signature with message recovery might be the only option. Admittedly, that applies only for a narrow interval of size: the gain is a fraction of the hash size thus becomes proportionally negligible with larger payloads, and ECC wins for smaller ones (because RSA cryptograms have the size of the public modulus). It happens that the interval where RSA wins is close to the maximum practical capacity of a 2D-code (e.g. QR-code).


That answer points another rather specialized use case of RSA where it shines: deterministic, size-preserving public-key encryption.

That answer points yet other practical reasons why RSA remains widely used.

$\endgroup$
  • 2
    $\begingroup$ RSA also has a longer history of attack analysis behind it. Currently, elliptic curves seem stronger / better in a number of quantifiable ways, but they haven't had as many decades of researchers pounding on them. $\endgroup$ – JesseM May 29 '18 at 18:30
  • 5
    $\begingroup$ @JesseM ECC is only 8 years younger than RSA. $\endgroup$ – yyyyyyy May 29 '18 at 23:28
  • 2
    $\begingroup$ @yyyyyyy: But RSA was the go-to mainstream algo for longer, so perhaps it's had more attention during many of the years when they both existed. (I don't know whether this is true or not; I don't follow cryptanalysis research.) $\endgroup$ – Peter Cordes May 30 '18 at 11:32
12
$\begingroup$

So, my question is, do we still need RSA? Is there any situation where it cannot be replaced by an ECC scheme instead?

RSA is used for signature generation. ECDSA covers signature generation. RSA also allows for signature's with (partial) message recovery. That's nice, but again the small signature / key size of ECC makes up for most if not all of the difference.

RSA can also be used for direct and hybrid encryption. ECC cannot directly be used for encryption of any message with a comparable size. The hybrid ECIES scheme to overcome that; the smaller key size will generally still result in comparable ciphertext size.

RSA can actually be used for forward secrecy as well, but the enormously time consuming (and hard to protect) key pair generation would make it a horrible choice.

So anything that RSA can do can be done using ECC in one form or other.


More specifically, if the answer to the above is no, are there any circumstances in which RSA is better suited than the ECC counterpart? Why is it still in use from a practical point of view?

There are many reasons to choose RSA:

  • faster for public key operations (repeat from fgrieu's answer);
  • prolific in many PKI(X) infrastructures, including long term certificates;
  • better backward compatibility;
  • more implementations available;
  • operations that use the keys easier to understand / implement;
  • slightly less vulnerable against quantum computers at the same bit strength;
  • operations using the keys do not depend (as much) on security of random number generator;
  • no domain parameters to agree on or store (there are 3 ways of encoding the parameters using ASN.1 alone);
  • fewer pitfalls (such as verifying that the public key is on the curve);
  • fewer options such as types of domain parameters, signature formats (flat or ASN.1 encoded) or key formats (compressed or uncompressed);
  • fewer IP rights to mull over (I guess most - if not all - patents are expired or not-applicable, but...);
  • still efficient enough for most purposes.

Obviously the smaller key sizes, the possibility to offer 256 bit security without requiring obnoxious key sizes, the efficiency & simplicity of key pair generation and private key operations still offer plenty of incentives to use ECC - but there are still many things that favor RSA.


These are just the practical / logical reasons that you asked for. There is a lot of mental insecurity around ECC while RSA is generally trusted pretty well. Management will keep going to RSA because it is considered the known, safe option.

$\endgroup$
  • $\begingroup$ I also found a homomorphic encryption scheme for ECC, so I guess that's covered as well. Homomorphic encryption is however not used that much afaik, so I'll leave it out. $\endgroup$ – Maarten Bodewes May 29 '18 at 13:34
7
$\begingroup$

One uncommon case, but one that I don't know of an elliptic curve variant of, is format-preserving encryption.

RSA-DOAEP can be used in a format-reserving encryption scheme (possibly in conjunction with cycle walking), so long as the space of possible formatted values is larger than the keyspace.

Since RSA keys need to be quite large for security, this limits the usefulness of asymmetric format-preserving encryption, but I don't know of a published elliptic curve alternative.

$\endgroup$
3
$\begingroup$

You can do forward secrecy with classicial RSA and DH. No need for ECC there.

The main reason for prefering ECC is that it can deliver the same level of assumed-security with smaller keys, smaller signatures etc. That means that the cost per session is lower than with classical RSA/DH

As for reasons poeple may prefer RSA.

  1. The admin can choose the keysize arbiterally. With ECDSA the admin is forced to choose from one of a handful of standard curves.
  2. Speaking of standard curves some of the most widely supported curves came from the US government and there are suspiscions that the US government may have generated them in a way that opens up backdoors.
  3. ECDSA has a design flaw where a bad random number generator during signing can compromise the long term private key. There is a fix for said design flaw but figuring out whether all the involved implementations have the fix may be difficult.
  4. Everyone supports RSA. Not everyone supports ECDSA. Is the overhead of maintaining two seperate public keys worth the savings?
  5. There are patent concerns surrounding ECC. RSA was also Patented but the patent expired in 2000.
$\endgroup$
  • $\begingroup$ The question was about elliptic curve cryptography in general, not about ECDSA; one might presume that the questioner admits the possibility of making modern sensible choices like Ed25519 instead of archaic garbage like ECDSA-nistp256. None of these really distinguish RSA from elliptic curve cryptography. $\endgroup$ – Squeamish Ossifrage May 29 '18 at 15:24
  • 2
    $\begingroup$ They distinguish "RSA as practically implemented" from "ECC as practically implemented". And thus answer the OPs final questino of "why is it still in use from a practical point of view". It would be nice if we had a widely supported, 512 bit, nothing up my sleeve deterministic ECC digital signature scheme but afaict we don't. $\endgroup$ – Peter Green May 29 '18 at 15:39
  • 1
    $\begingroup$ X25519 and Ed25519 are widely supported and well-understood and after a decade of deployment have no obvious relevant patents and provide ample security with high performance for everything except signature verification as fgrieu noted. There's no need for a ‘512-bit signature scheme’: as a hedge against minor cryptanalytic advances Ed448 is plenty; if you really wanted something closer to the number 512, EdDSA over E-521 is the obvious choice. If the only answer is (4) ‘because the library you're using supports RSA but not Ed25519’, that's hardly more than begging the question. $\endgroup$ – Squeamish Ossifrage May 29 '18 at 18:35
2
$\begingroup$

There's an extremely common situation where RSA can't be replaced with ECC. It's the situation where the person at the other end of the transaction has software that only supports RSA. Lack of compatibility has doomed many technologies that are technically the better solution.

$\endgroup$

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.