What problem does ECC seek to fix compared to RSA?

Question

Elliptical Curve Cryptography (ECC) is one of the newest encryption schemes to challenge RSA cryptography. What problem does ECC seek to fix compared to RSA? Would you have any qualms with using ECC to encrypt sensitive material?

Answer 1

Tom gave a good answer for your other question, so I will address the last one.

Would you have any qualms with using ECC to encrypt sensitive material?

Yes, I would have qualms about using RSA or even ECC to encrypt sensitive material in today's world. RSA relies on the integer factorization problem and ECC relies on the discrete logarithm problem. Both of which are quickly solvable by a quantum computer. We know some organisations are making progress in the area and certain government agencies are spending $79.7 million a year on researching and developing a quantum computer capable of cracking encryption.

It is not a matter of if, but a matter of when a quantum computer becomes available. If one was secretly available to intelligence agencies in the past decade, then anything you encrypted with RSA or ECC has already been readable by them. If they have not managed to build one yet, then the same applies for anything encrypted with RSA or ECC between now and when they get a working one. They are storing vast amounts of internet traffic in their datacenters indefinitely, especially if they can't crack the encryption on them right now, they will try again when they can.

Fortunately there is a whole field of cryptography called Post-quantum cryptography. Aim to only develop and use open source software using these algorithms.

Answer 2

The main "problem" that ECC tries to fix is that RSA is RSA. Namely, people want to have a backup kind of algorithms, in case RSA gets brutally broken through a stupendous (and unpredictable) advance in integer factorization techniques. Integer factorization has been heavily studied for more than 2500 years (it was already all the rage in the Neo-Babylonian empire), and we can therefore say that ground-breaking advances in that field are not obvious, and don't happen often. However, this is mathematics: progress comes from ideas, which may occur without warning in the brain of people living in remote places that you have never heard of. Though such a break is improbable, there will be no prior warning. Hence ECC.

For the "backup algorithm" strategy to work, the ECC-based algorithm must be deployed wherever RSA is used. It takes a lot of time from the scientific article to code which runs and interoperates; if ECC is supposed to be able to replace RSA at a moment's notice, then it must be already there.

Apart from that point (often described as "a need for algorithm biodiversity"), ECC offers interesting performance-related advantages: smaller messages (an RSA-based key exchange with a 2048-bit RSA key requires 256 bytes, while the ECDH key exchange of similar strength may fit in 28 bytes), faster private key operations (by a factor of 10 or more)... Smart card vendors are much interested.

Furthermore, some very specific types of elliptic curves allow for efficient pairing computations, which open up the practical possibility of three-actor protocols. This is used, for instance, to implement identity-based encryption: you cannot do that with RSA.