### 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^{2} = x^{3} + 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.