Is there a situation where RSA cannot be replaced with ECC + symmetric algorithms? If no, why do we still use it?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.