An introduction to Elliptic Curve Cryptography

Elliptic Curve Cryptography (ECC) has been gaining momentum as a replacement for RSA public key cryptography largely based on its efficiency, but also because the US National Security Agency (NSA) included it, while excluding RSA, from its Suite B cryptography recommendations. Suite B is a set of algorithms that the NSA recommends for use in protecting both classified and unclassified US government information and systems.

Public key cryptography is the basis for tools like ssh as well as Secure Sockets Layer (SSL) for encrypting web traffic. For readers who would like more information, a nice introduction to public key cryptography and the RSA algorithm can be found on Wikipedia.

ECC is based on some very deep math involving elliptic curves in a finite field. It relies on the difficulty of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) in much the same way that RSA depends on the difficulty of factoring the product of two large primes. The best known method for solving ECDLP is fully exponential, whereas the number field sieve (for factoring) is sub-exponential. This allows ECC to use drastically smaller keys to provide the equivalent security; a 160-bit ECC key is equivalent to a 1024-bit RSA key.

Smaller key sizes lead to faster processing, which is very interesting to folks that are implementing encryption on small, mobile devices with limited resources in terms of power, CPU and memory. It is also very desirable for large web servers that will be handling many encrypted sessions. These are the technical considerations driving adoption. The NSA's recommendation makes it very attractive to companies that sell encryption products to the government and many non-governmental entities will also want products that implement ECC.

In order to use elliptic curves as part of a public key cryptosystem, both parties must agree on a set of domain parameters that fully specify the curve that is being used. Various groups, notably the US National Institute for Standards and Technology (NIST) and the Standards for Efficient Cryptography Group (SECG) have recommendations for the domain parameters to be used for various key sizes. The Internet Engineering Task Force (IETF) also has a draft specification for adding ECC to SSL/TLS.

Sun Microsystems has donated ECC code to OpenSSL and the Network Security Services (NSS) library; this allows the Apache web server and Mozilla browsers (and many other programs) to use ECC.

Unfortunately, as with RSA before its patent expired, the ECC landscape is littered with patent claims; some of dubious enforceability due to prior art. Sun claims patents on ECC technology, but has provided a "patent peace" provision in its license that states that it will not enforce its patent claims and asks that anyone holding patents associated with the code not enforce them against Sun.

The wild card in the ECC patent arena seems to be Certicom which claims a large number of ECC patents and has not made a clear statement of its intentions with regard to open source implementations. The NSA licensed Certicom's patents for $25 million to allow them and their suppliers to use ECC, lending some credence to at least some of the Certicom patents. Other companies also have patents on various pieces of ECC technology.

As is often the case with patents, it is well nigh impossible to determine what the patents cover and if an implementation infringes without going to court. Ironically, the clearest description of what is and is not patented is an RSA Laboratories FAQ entry:

Of course, this is not legal advice from RSA and may or may not be how it is interpreted by the courts. We will all have to wait and see how it plays out if one or more of the patent holders decides to sue.

[The author wishes to thank his employer, Privacy Networks, for sending him to the RSA 2006 conference which inspired this article.]