Elliptic Curve Cryptography

For the last eight years or so, I keep seeing the occasional article or reference to elliptic curve cryptography (ECC). Having only glossed over article headlines and summaries before, I understood it to be some new algorithm for use with public-key cryptography, i.e. an alternative to the RSA algorithm. My only experience with public-key cryptography where I worked directly with the keys and was cognizant of the algorithm being used is with Secure Shell (SSH). Where I work, we have "smart cards" that hold certificates for authentication, message signing and encryption. I know the signing and encryption keys are part of a public-key infrastructure, but I couldn't tell you what algorithm is used or anything else about the keys. It's all encapsulated on the card and the software that reads it.

So what's the difference between RSA and elliptic curves? Is it somehow better, stronger, faster, etc?

The whole idea of public-key cryptography is based on some type of mathematical problem that is easy to solve in one direction, but practically infeasible to reverse engineer and solve in the opposite direction. We're talking about problems whose known solution(s) involve exponential time and would take inordinate amounts of time to solve even if you had inconceivable amounts of computing power at your disposal. In other words, not practical for cracking open single emails and files on a daily basis.

RSA does this by using a pair of large prime numbers. If you know what the two numbers are, it is really simple to crank them through the math and sign/verify or encrypt/decrypt data. But if you only have one of the numbers (i.e. the public key) and some signed or encrypted data, good luck trying to reverse engineer the other number (i.e. the private key) from that. Prime factorization of large numbers has no known polynomial-time solution. However, with advances in computing horsepower, some folks have factored a 768-bit number using a massive, distributed system. So we begin the escalation of attack/counter-measure and start increasing the bit-size of all our keys to stay ahead of the hardware. But that causes some inconvenience like distributing new, larger keys and the extra time required to run the math with them.

Elliptic curves is the same concept, but uses a different type of math problem. The math is hairy and I won't pretend to understand all the details, but the gist is to take the plane curve defined by an equation of the form y^2 = x^3 + ax + b and introduce a set of group operations that take advantage of an interesting property of such a curve. If you draw a line through it, it intersects the curve at exactly three places (yes, there are some boundary cases). These points, boiled through the math, ultimately equate to your key pair. And like RSA, it is infeasible to easily reverse engineer the private key if you only have the public key and some signed/encrypted data.

So is this better than RSA? It depends on what your criteria is. So far the research shows that ECC keys provide the same security as an RSA key of significantly larger size. For example, if you have a 2048-bit RSA key, you only need a 224-bit ECC key. So that will take up less space and computation time.

Should we all jump on the ECC bandwagon then? There are some caveats. There are obviously a lot of different formulas for elliptic curves and the group operations. There are some known sets of parameters for these that are weak in cryptographic terms. So you have to choose wisely. NIST has published a set of recommended parameter sets for use with ECC. Of course, recent revelations about the NSA influencing the choice of certain aspects of these parameters and algorithms to make surveillance easier might give one pause to consider whether these recommendations are really that good.

Another possible issue is patents. Some companies and organizations have patented certain techniques for implementing ECC systems. This might keep someone from implementing or using ECC based on the fear of inadvertently using one of these and getting sued for it.

Then you also have what I think of as the inertia of an entrenched system to overcome. RSA has been around much longer and is in very wide use. To suddenly switch to ECC requires updating software and keys and possibly retraining some people. With no compelling need to do this, many will not bother. This is the same reason IPv6 is not in more use than it is. IPv4 works good enough for 99% of us. Same goes for RSA.

So can I play with ECC keys? It will have to be with SSH. Looks like OpenSSH added support for it in version 5.7 and I have version 6.2 available in Fedora 19. The ssh-keygen man page says they added a new key type of  "ECDSA".

ssh-keygen -b 256 -t ecdsa

That generated a new key pair for me in $HOME/.ssh/ called id_ecdsa and id_ecdsa.pub.

-rw-------. 1 mjones mjones  736 Jul 12 06:01 id_dsa
-rw-------. 1 mjones mjones  605 Jul 12 06:01 id_dsa.pub
-rw-------. 1 mjones mjones  314 Dec  6 16:55 id_ecdsa
-rw-------. 1 mjones mjones  190 Dec  6 16:55 id_ecdsa.pub

They are certainly much smaller than my existing 1024-bit DSA keys. I've been using those for a long time, circa 1998. Can't even remember why I used DSA instead of RSA now. :)

Installing the public key in the authorized_keys2 file on another system, we can test it like this

ssh -v -i ~/.ssh/id_ecdsa user@host
debug1: identity file /home/mjones/.ssh/id_ecdsa type 3

and verify that it did indeed successfully use the new ECC key instead of the default DSA key.

Unfortunately, many of the systems I work with do not have a sufficient version of SSH to support ECDSA keys. So I will maintain both key types for a while and try the ECDSA where possible.




This post maps to CompTIA SY0-301 exam objectives 1.4, 6.1 and 6.2.