Elliptic curves are mathematical constructions from number theory and algebraic geometry, which in recent years have found numerous applications in cryptography.

An elliptic curve can be defined over any field (for example, real, rational, complex), though elliptic curves used in cryptography are mainly defined over finite fields. An elliptic curve consists of elements (x, y) satisfying the equation

y2 = x3 + ax + b

together with a single element denoted O called the "point at infinity", which can be visualized as the point at the top and bottom of every vertical line. The elliptic curve formula is slightly different for some fields.

The addition operation in an elliptic curve is the counterpart to modular multiplication in common public-key cryptosystems, and multiple addition is the counterpart to modular exponentiation. Elliptic curves are covered in more recent texts on cryptography, including an informative text by Koblitz.

Elliptic curve cryptosystems were first proposed independently by Victor Miller and Neal Koblitz  in the mid-1980s. At a high level, they are analogs of existing public-key cryptosystems in which modular arithmetic is replaced by operations defined over elliptic curves. The elliptic curve cryptosystems that have appeared in the literature can be classified into two categories according to whether they are analogs to the RSA system or to discrete logarithm based systems.

Just as in all public-key cryptosystems, the security of elliptic curve cryptosystems relies on the underlying hard mathematical problems. It turns out that elliptic curve analogs of the RSA system are mainly of academic interest and offer no practical advantage over the RSA system, since their security is based on the same underlying problem, namely integer factorization. The situation is quite different with elliptic curve variants of discrete logarithm based systems. The security of such systems depends on the elliptic curve discrete logarithm problem.

Nowadays, the methods for computing general elliptic curve discrete logarithms are much less efficient than those for factoring or computing conventional discrete logarithms. As a result, shorter key sizes can be used to achieve the same security of conventional public-key cryptosystems, which might lead to better memory requirements and improved performance.

In general, the best attacks on the elliptic curve discrete logarithm problems have been general brute-force methods. The current lack of more specific attacks means that shorter key sizes for elliptic cryptosystems appear to give similar security as much larger keys that might be used in cryptosystems based on the discrete logarithm problem and integer factorization. For certain choices of elliptic curves there do exist more efficient attacks. Menezes, Okamoto, and Vanstone have been able to reduce the elliptic curve discrete logarithm problem to the traditional discrete logarithm problem for certain curves, thereby necessitating the same size keys as is used in more traditional public-key systems. However these cases are readily classified and easily avoided.

The comparison between elliptic curve cryptosystems  and other cryptosystems

The main attraction of elliptic curve cryptosystems over other public-key cryptosystems is the fact that they are based on a different, hard problem. This may lead to smaller key sizes and better performance in certain public key operations for the same level of security.

Very roughly speaking, elliptic curve cryptosystems with a 160-bit key offer the same security of the RSA system and discrete logarithm based systems with a 1024-bit key. As a result, the length of the public key and private key is much shorter in elliptic curve cryptosystems. In terms of speed, it is perhaps fair to say the following: Elliptic curve cryptosystems are faster than the corresponding discrete logarithm based systems. Elliptic curve cryptosystems are faster than the RSA system in signing and decryption, but slower in signature verification and encryption.