Public key cryptography systems are usually based on the assumption that a particular mathematical operation is easy to do, but difficult to undo unless you know some particular secret that serves as the secret key. A recent development in this field is the so-called elliptic curve cryptography (ECC).
An elliptic curve with a underlying finite field Fp is a set of points on the curve with equation y^2 = x^3 + ax + b. The set of points on such a curve form an additive group where the basic function is addition. Two points P & Q are added up by drawing a line through both and taking as the outcome where the line intersects the curve. Certicom has a good online tutorial on ECC.
ECC relies upon the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP), the problem of finding k given points kG and G (remember that there is no division is defined on the group).
To use ECC all parties must agree on all the elements (p,a,b,G,n,h) defining the elliptic curve, that is domain parameters of the scheme:
- a & b define the curve (equation);
- p defines the finite field Fp in the prime case -- computations end by taking the remainder on division by p;
- G is the base point and defines the cyclic subgroup;
- order n represents the number of discrete points on the curve -- the smallest non-negative number such that nG=O;
- h is the cofactor and preferably h=1.
-------------------------------
Alice and Bob agree on an elliptic curve (domain parameters) and pick a certain point G on this curve. They can do this with Eve listening in. Alice next picks a random number As (not necessarily a point on the curve) and computes Ap = As*G. This is easy to compute.
Alice's public key is Ap and her secret key is As. Bob does the same thing and ends up with Bp and Bs.
Alice and Bob can now secretly agree on a key with which they can encrypt messages using secret key cryptography. The key simply is the product of Alice's public key and Bob's secret key (which is the same as the product of Alice's secret key and Bob's public key): As*Bp=As*Bs*G=Bs*Ap.
If Eve wanted to crack the key, she would have to reconstruct one of the secret keys. This means having to compute As given Ap and G (ECDLP), which is very difficult. If G is, say, 160 bits long, then Eve needs about 2^80 operations: If she can do a billion operations per second, this takes about 38 million years.
-------------------------------
As for other popular public key cryptosystems, no mathematical proof of difficulty has been published for ECC as of 2006. However, the U.S. National Security Agency has endorsed ECC technology by including it in its Suite B set of recommended algorithms. NIST recommends 15 elliptic curves in FIPS 186-2.
One North Residence
