Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.
share|improve this question

migrated from security.stackexchange.com Nov 15 '11 at 8:01

This question came from our site for Information security professionals.

    
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. –  Raghavendra Jul 9 '12 at 18:03
    
Another advantage of RSA: public key operations (encryption/sig verification) are still faster than for ECC with same strength. –  Smit Johnth May 4 '13 at 21:22
2  
@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? –  Vineet Menon May 5 '13 at 13:04
    
@VineetMenon crypto.stackexchange.com/questions/1190/… RSA can use very short public key. This wouldn't word with DH-based ciphers, used with ECC. –  Smit Johnth May 5 '13 at 13:32
    
Is it possible that better algorithms for integer factorisation were found first after RSA become widely used? –  Smit Johnth May 5 '13 at 13:44

3 Answers 3

up vote 56 down vote accepted

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.)

share|improve this answer
5  
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. –  CodesInChaos Apr 18 '12 at 12:33
2  
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! –  Simon Johnson Jul 10 '12 at 11:04
    
@ThomasPornin Do you have a citation for the outperfomance of RSA on signatures verification ? –  curious Mar 3 '13 at 11:12
1  
@curious: I can quote myself. But you can also make benchmarks (with OpenSSL, try openssl speed rsa2048 ecdsap224). –  Thomas Pornin Mar 3 '13 at 13:34
1  
I have a question. I heard that cipher texts encrypted with RSA can possible give hints about the public key used (identify who did or did not encrypt that message) while elliptic curves do not have this weakness. Is this true? –  Xeoncross Jul 9 '13 at 16:25

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.

share|improve this answer
3  
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!! –  Vineet Menon Nov 15 '11 at 18:42
    
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. –  MrEvil Jun 10 '13 at 15:58

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.

share|improve this answer
    
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. –  jww Dec 26 '13 at 4:44

protected by Community Jun 11 '13 at 18:55

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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