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 y2 = x3 + 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
