March 8, 2006
This article was contributed by Jake Edge.
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:
In all of these cases, it is the implementation technique that is patented,
not the prime or representation, and there are alternative, compatible
implementation techniques that are not covered by the patents.
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.]
Comments (7 posted)
