Elliptic curve cryptography
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. This particular secret that serves as the secret key. A recent development in this field is the so-called elliptic curve cryptography.
Elliptic curve cryptography works with points on a curve. The security of this type of public key cryptography depends on the elliptic curve discrete logarithm problem.
Introduction
Elliptic curve cryptography was invented by Neil Koblitz in 1987 and by Victor Miller in 1986. The principles of elliptic curve cryptography can be used to adapt many cryptographic algorithms, such as Diffie-Hellman or ElGamal. Although no general patent on elliptic curve cryptography appears to exist, there are several patents that may be relevant depending on the implementation (US 5,159,632, US 5,271,061, US 5,463,690 and US 6,141,420).
The main advantage of elliptic curve cryptography is that the keys can be much smaller. Recommended key sizes are in the order of 160 bits rather than 1024 bits for RSA.
Elliptic curves
An elliptic curve is a set of points (x, y), for which it is true that
given certain chosen numbers a and b. Typically the numbers are integers (whole numbers), although in principle the system also works with real (fractional) numbers. Despite what the name suggests, the curves do not have an elliptic shape. For example, a = -4 and b = 0.67 gives the elliptic curve with equation y2 = x3 - 4x + 0.67. This curve is illustrated in the following figure.
If x3 + ax + b contains no repeated factors, or equivalently if 4a3 + 27b2 is not 0, then the elliptic curve can be used to form a group. A group is simply a set of points on the curve. Because it is a group, it is possible to "add up" points which gives another point on the curve. On the graph, two points are added up by drawing a line through both and taking as the outcome where the line intersects the curve.
For cryptographic purposes, an elliptic curve must have only points with all coordinates whole numbers (integers) in the group.
The trick with elliptic curve cryptography is that if you have a point F on the curve, all multiples of this point are also on the curve.
Generating an elliptic curve public key
Alice and Bob agree on an elliptic curve and pick a certain point F on this curve. They can do this with Eve listening in. Alice next picks a random number AS (which does not have to be a point on on the curve) and computes AP = AS*F. The point AP is on the curve, because it is a multiple of F. 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.
Encrypting and decrypting messages
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). It will be clear that Alice and Bob can compute this product after they have exchanged their public keys, but Eve cannot since she has none of the secret keys.
Cracking the elliptic curve key
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 F (because AP = AS * F). And that is very difficult.
The number of discrete points on the curve (points with both X and Y coordinates being integers) is called the order of the curve. If the order of the point F is a prime number of n bits, then computing AS from AS*F and F takes roughly 2n/2 operations. If F is, say, 160 bits long, then Eve needs about 280 operations. If she can do a billion operations per second, this takes about 38 million years.
This problem is commonly referred to as the elliptic curve discrete logarithm problem.