Elliptic curve cryptography

Elliptic curve cryptography or ECC is a class of cryptographic algorithms capable of doing asymmetric encryption. That is, two different keys are used: one for encryption, and one for decryption. Possession of one key does not give sufficient information to determine the other key.

There are several slightly different versions of elliptic curve cryptography, all of which rely on the widely believed difficulty of solving the discrete logarithm problem for the group of an elliptic curve over some finite field. The most popular finite fields for this are the integers modulo a prime number (see modular arithmetic), or a Galois field of size a power of two. (Galois fields of size of power of some other prime have also been proposed, but are considered a bit dubious among cryptanalysts.)

Given an elliptic curve E, and a field GF(q), we consider the abelian group of rational points E(q) of the form (x, y), where both x and y are in GF(q), and where the group operation "+" is defined on this curve as described in the article elliptic curve. We then define a second operation "*" | Z×E(q) → E(q): if P is some point in E(q), then we define 2*P = P + P, 3*P = 2*P + P = P + P + P, and so on. Note that given integers j and k, j*(k*P) = (j*k)*P = k*(j*P). The elliptic curve discrete logarithm problem (ECDLP) is then to determine the integer k, given points P and Q, and given that k*P = Q.

It is believed that the usual discrete logarithm problem over the multiplicative group of a finite field (DLP) and ECDLP are not equivalent problems; and that ECDLP is significantly more difficult than DLP.

In cryptographic use, a specific base point G is selected and published for use with the curve E(q). A private key k is selected as a random integer; and then the value P = k*G is published as the public key (note that the purported difficulty of ECDLP implies that k is hard to determine from P). If Alice and Bob have private keys k_A and k_B, and public keys P_A and P_B, then Alice can calculate k_A*P_B = (k_A*k_B)*G; and Bob can compute the same value as k_B*P_A = (k_B*k_A)*G.

This allows the establishment of a "secret" value that both Alice and Bob can easily compute, but which is difficult for any third party to derive. In addition, Bob does not gain any new knowledge about k_A during this transaction, so that Alice's private key remains private.

The actual methods used to then encrypt messages between Alice and Bob based on this secret value are adaptations of older discrete logarithm cryptosystems originally described for use on other groups. These include Diffie-Hellman, ElGamal discrete log cryptosystem and DSA.

Doing the group operations needed to run the system is slower for an ECC system than for a factorisation system or modulo integer discrete log system of the same size. However, proponents of ECC systems believe that the ECDLP problem is signficantly harder than the DLP or factorisation problems, and so equal security can be provided by much smaller key lengths using ECC, to the extent that it can actually be faster than, for instance, RSA. Published results to date tend to support this belief, but some experts are skeptical.

ECC is widely regarded as the strongest asymmetric algorithm at a given key length, so may become useful over links that have very tight bandwidth requirements.

NIST and ANSI X9 have set minimum keysize requirements of 1024 bits for RSA and DSA and 160 bits for ECC, corresponding to a symmetric block cipher key size of 80 bits. NIST has published a list of recommended elliptic curves for protection of 5 different symmetric keysizes (80, 112, 128, 192, 256). In general, ECC over a binary field requires an asymmetric key size of twice that of the corresponding symmetric key.

Certicom[?], a major commercial proponent of ECC, has sponsored several challenges to the ECC algorithm. The most complex to have been solved was a 109 bit key, which was broken by a team of researchers near the beginning of 2003. The team which broke the key used a massive parallel attack based on the birthday attack, using over 10,000 Pentium class PCs running continuously for over 540 days. The minimum recommended key size for ECC, 163 bits, is currently estimated to require 10⁸ times the computing resources as that required for the 109 bit problem.

External links

• Recommended Elliptic Curves for Government Use, NIST document (PDF file) (http://csrc.nist.gov/CryptoToolkit/dss/ecdsa/NISTReCur.pdf)
• Certicom press release regarding 109 bit ECC challenge (http://www.certicom.com/about/pr/02/021106_ecc_winner)
• Certicom Online ECC Tutorial (http://www.certicom.com/resources/ecc_tutorial/ecc_tutorial)
• Digital Signature Standard; includes info on ECDSA (http://csrc.nist.gov/cryptval/dss.htm)