What are Elliptic Curve Cryptosystems?

Elliptic curve cryptosystems are analogs of public-key cryptosystems such as RSA (see Question 8) and ElGamal (see Question 29), in which modular multiplication is replaced by the elliptic curve addition operation.

The curves used in elliptic curve analogs of discrete logarithm cryptosystems are normally of the form

y² = x³ + ax + b (mod p),

where p is prime. The problem tapped by the discrete logarithm analogs in elliptic curves is the elliptic curve logarithm problem, defined as follows: given a point G on an elliptic curve with order r (number of points on the curve) and another point Y on the curve, find a unique x (0 x r - 1) such that Y = xG, i.e., Y is the xth multiple of G.

Until recently, the best attacks on elliptic curve logarithm problems were the general methods applicable to any group. The methods have a running time of about a constant times the square root of r on average, which is much slower than specialized attacks on certain types of groups. The lack of specialized attacks means that shorter key sizes for elliptic cryptosystems give the same security as larger keys in cryptosystems that are based on discrete logarithm problem . However, for certain elliptic curves, Menezes, Okamoto, and Vanstone [MOV90] have been able to reduce the elliptic logarithm problem to a discrete logarithm problem. It is possible that algorithm development in this area will change the security of elliptic curve discrete logarithm cryptosystems to be equivalent to that of general discrete logarithm cryptosystems; this is an open research problem.

Elliptic curve analogs of RSA have been proposed, and they are based on the difficulty of factoring, just as RSA is. The elliptic curve analogs do not seem to offer any significant advantage over RSA, as the underlying problem is the same and the key sizes are similar for equivalent levels of security. Two of their purported advantages resistance to "low-exponent" attacks and to signature forgery against a chosen message attack have recently been shown not to hold.