181
$\begingroup$

I recently ran across elliptic curve crypto-systems:

It seemed to me to be great alternative to RSA as the de-facto cryptosystems to be used in banking and financial systems and in the public key infrastructure for certificates, but is not used! If someone can explain why this is not done, it would be very helpful. A comparison between traditional RSA and an elliptic curve cryptology would be helpful.

To begin with:

Advantage of RSA:

  1. Well established.

Advantages of elliptic curve:

  1. Shorter keys are as strong as long key for RSA (see the IEEE paper)
  2. Low on CPU consumption.
  3. Low on memory usage.
$\endgroup$
9
  • $\begingroup$ Excellent answers. Regarding adoption of EC, implementation has always been an issue. However, openssl (from 0.9.8) and lately openssh (from openssh 5.7) have elliptic curve built into them, so we should see greater adoption in future. $\endgroup$ Commented Jul 9, 2012 at 18:03
  • 3
    $\begingroup$ @SmitJohnth: 'RSA' faster than 'ECC'? How's that? The lower CPU consumption and lower memory consumption of ECC doesn't automatically translate to a faster algorithm? $\endgroup$ Commented May 5, 2013 at 13:04
  • 1
    $\begingroup$ @VineetMenon crypto.stackexchange.com/questions/1190/… RSA can use very short public key. This wouldn't word with DH-based ciphers, used with ECC. $\endgroup$ Commented May 5, 2013 at 13:32
  • 2
    $\begingroup$ One additional minor advantage for RSA is that it is believed it will hold up better against a quantum computer compared to ECC. I don't think that ever causes anyone to choose RSA over ECC though. $\endgroup$
    – Lie Ryan
    Commented Jun 10, 2017 at 14:34
  • 1
    $\begingroup$ @LieRyan, interesting.. more at Why is ECC more vulnerable than RSA in a post-quantum world? $\endgroup$ Commented Jun 12, 2017 at 4:43

4 Answers 4

164
$\begingroup$

RSA was there first. That's actually enough for explaining its preeminence. RSA was first published in 1978 and the PKCS#1 standard (which explains exactly how RSA should be used, with unambiguous specification of which byte goes where) has been publicly and freely available since 1993. The idea of using elliptic curves for cryptography came to be in 1985, and relevant standards have existed since the late 1990s. Also, both RSA and elliptic curves have been covered by patents, but the RSA patents have expired in 2000, while some elliptic curve patents are still alive.

One perceived, historical advantage of RSA is that RSA is two algorithms, one for encryption and one for signatures, that could both use the same key and the same core implementation. But this is not a real advantage because it is usually a bad idea to use the same key for both encryption and signatures. Also, you can mathematically use the same private key for ECDH (key exchange) and for ECDSA (signatures), so that's really not an "advantage" of RSA over EC at all.

Another advantage of RSA is that its mathematics are somewhat simpler than those involved for elliptic curves, so many engineers feel that they "understand" RSA more than elliptic curves; again, a fallacious argument, since implementation of cryptographic algorithms is fraught with subtle details and best left to professionals -- and there is no need to understand the internal mathematics of a library to simply use it (we could make this argument semi-valid by pointing out that RSA relies on the hardness of factorization, which has been studied for 2500 years, whereas discrete logarithm on elliptic curves can only sport about 25 years of research).

The only scientifically established advantaged of RSA over elliptic curves cryptography is that public key operations (e.g. signature verification, as opposed to signature generation) are faster with RSA. But public-key operations are rarely a bottleneck, and we are talking about 8000 ECDSA verifications per second, vs 20000 RSA verifications per second.

An additional interoperability issue is that elliptic-curve operations can be made over curves of distinct types, and can be widely optimized if you stick to a specific curve known when the code was written. There is no security issue in using the same curve for many distinct people with distinct key pairs. But it means that most implementations will only support two or three specific curves. NIST has defined 15 standard curves. However, in practice, many implementations only support two of them, P-256 and P-384, because that's what is recommended by NSA (under the name "suite B")(a notorious example is NSS, the cryptography library used by the Firefox Web browser for SSL).

There are two ANSI standards for elliptic curves, X9.62 for signatures (partially redundant with FIPS 186-3, but much more detailed), and X9.63 for asymmetric encryption.

So there is a lot of political push for the adoption of elliptic curves in cryptography, by both academic researchers and institutional organizations. But inertia of the firmly entrenched RSA will take time to defeat. Also, the perceived mathematical complexity, and the potential legal risks related to patents, still hinder wide acceptance of elliptic curves.

(To your list, you can add "key generation time": generating a new key pair for ECDH or ECDSA is widely faster than generating a new RSA key pair.)

$\endgroup$
12
  • 11
    $\begingroup$ For me the primary selling point of RSA is that it doesn't leak the private key if your PRNG happens to be badly seeded while signing. While it's possible to avoid this issue, most implementations don't. $\endgroup$ Commented Apr 18, 2012 at 12:33
  • 15
    $\begingroup$ You can implement RSA from scratch in about 50 lines of python. Try doing that with elliptic curves. Laziness was certainly part of the reason RC4 became so widespread. I think it's true of RSA too! $\endgroup$ Commented Jul 10, 2012 at 11:04
  • 4
    $\begingroup$ @curious: I can quote myself. But you can also make benchmarks (with OpenSSL, try openssl speed rsa2048 ecdsap224). $\endgroup$ Commented Mar 3, 2013 at 13:34
  • 4
    $\begingroup$ That's because the operation is not exactly the same. With RSA, signature verification uses the public exponent, which can be very short (with RSA, the public exponent typical length is 16 bits, while the privat exponent is as large as the modulus). This gives a huge boost to public key operations in RSA. There's no analog with elliptic curves. $\endgroup$ Commented Mar 3, 2013 at 16:53
  • 2
    $\begingroup$ I think there're also some inherent (mis)trust issues w.r.t the fact that the NSA itself is making the recommendations and, IIRC, there were some important numbers that are necessary for ECC that, at least at the time I read about it, it wasn't clear where/how those numbers had come from. I think the trust part is an important factor that has not been explicitly mentioned. $\endgroup$
    – code_dredd
    Commented Jun 12, 2018 at 19:44
40
$\begingroup$

This is mostly a supplement to @ThomasPornin's answer, not a complete answer on its own (but too long to fit in a comment).

ECC uses a finite field, so even though elliptical curves themselves are relatively new, most of the math involved in taking a discrete logarithm over the field is much older. In fact, most of the algorithms used are relatively minor variants of factoring algorithms.

The real question (and one that's still open, AFAIK) is whether discrete logarithms over an elliptical curve have the same "smoothness" property as you use in the sieve-based algorithms for factoring the product of large primes. If elliptical curves aren't "smooth" (and quite a few mathematicians seem convinced they're not) then the sieve-style factoring algorithms can't be adapted to taking discrete logarithms over elliptical curves. If they are smooth (and a fair number of other mathematicians seem convinced this is likely to be true), however, the sieve-style algorithms could be adapted. This would be a significant "break" against ECC -- you'd need to increase key sizes substantially to maintain security (probably not to quite as large as RSA for equivalent security, but fairly close).

What this all comes down to is one thing: it's not nearly so clear-cut a difference as 2500 years vs. a few decades. If anything, almost the opposite is actually true: variants of most of the older factoring algorithms can be used to find discrete logarithms over elliptical curves. What does not apply (at least based on present knowledge) to elliptical curves is the research of the last few decades or so into sieve-based algorithms.

As far as the patent situation goes, I think the situation is much more clear than @poncho implies. Yes, Certicom holds some patents (120 currently, though not all of them are on ECC), but what is or isn't covered by those patents has been quite clear for years. Their patents cover some specific ways to optimize ECC, but definitely do not cover ECC itself. In fact, the patents themselves have a "Field of the Invention" (or, in some, "Background of the invention") section that tells you about what was known before the patent, and these have a fairly complete explanation of how to use ECC for both encryption and signatures. For example, see US Patent Number 6,141,420, which has quite a decent explanation of the math involved in elliptical curves, and how to implement ElGamal with elliptical curves -- all in the description of what was known prior to the patent.

$\endgroup$
1
  • 1
    $\begingroup$ Blackberry and Certicom claim over 300 patents in the arena, IIRC. See, for example, the NSA Sublicense FAQ at The National Security Agency’s ECC License Agreement with Certicom Corp. Certicom and Blackberry also claim to have patents that cover what CAs need to issue certificates with elliptic curves (perhaps implementation related?). See, for example, Certicom's IPR Licensing Contributions to the IETF's IKE, SSL, TLS, CMS, and S/MIME. $\endgroup$
    – user10496
    Commented Dec 26, 2013 at 4:44
26
$\begingroup$

Part of the reason is trust; RSA has been around longer than EC, and people feel they understand it, and they trust it more (and in security, this is important). It's also easier to implement.

However, I believe that a bigger concern (at least for major companies) is the fear of being sued; there's a small company called Certicom that holds a number of EC-related patents, and has threatened to sue anyone who might infringe on their patents (and, of course, without there being any clear definition of what those patents actually cover). They have sued Sony (and eventually settled out of court).

The bottom line: for quite a while, it was just easier for companies to stick with RSA/DH, rather then either pay Certicom or take the legal risk.

Lately, things have shifted; people have figured out they can implement EC using things that can be documented to predate the Certicom patents (and hence are immune to lawsuit); it appears that more common use of Elliptic Curves is not that far away.

$\endgroup$
2
  • 3
    $\begingroup$ since you are talking about implementations, wiki says there are open source implementation available in openSSH and others. So, as a programmer if I'm prompted to use that; will it do harm to me or my firm? I guess not!! $\endgroup$ Commented Nov 15, 2011 at 18:42
  • $\begingroup$ At PGP we had implementations of EC in the SDK, but they were stripped on compile specifically due to the patent issue. It's not the core implementations that you have to worry about, it's all of the performance aspects and implementation details that are encumbered. $\endgroup$
    – MrEvil
    Commented Jun 10, 2013 at 15:58
11
$\begingroup$

You forgot to mention one additional advantage of elliptic curves: the generation of keys is much faster than with RSA.

In europe, many government smart card solutions are now based on ECC:

  1. The european electronic pass ports
  2. The Austrian card
  3. The German ID card
  4. The new German health insurance card
$\endgroup$
2
  • 2
    $\begingroup$ To whom It may concern, the german ID card does use Brainpool P256r. $\endgroup$
    – hdev
    Commented Dec 7, 2016 at 9:18
  • 2
    $\begingroup$ didn't someone prove that the brainpool "r" curves were not, in fact, random... except maybe the 512r? $\endgroup$ Commented Sep 11, 2018 at 21:10

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