Basic explanation of Elliptic Curve Cryptography? I have been studying Elliptic Curve Cryptography as part of a course based on the book Cryptography and Network Security. The text for provides an excellent theoretical definition of the algorithm but I'm having a hard time understanding all of the theory involved in ECC.

I'm looking for an explanation suitable for someone who has studied at undergraduate level in computer science. Can anyone explain how elliptic curve cryptography works in a simple, straightforward manner?
There are some widely used cryptographic algorithms which need a finite, cyclic group (a finite set of element with a composition law which fulfils a few characteristics), e.g. DSA or Diffie-Hellman. The group must have the following characteristics:


Group elements must be representable with relatively little memory.
The group size must be known and be a prime number (or a multiple of a known prime number) of appropriate size (at least 160 bits for the traditional security level of "80-bit security").
The group law must be easy to compute.
It shall be hard (i.e. computationally infeasible, up to at least the targeted security level) to solve discrete logarithm in the group.


DSA, DH, ElGamal... were primarily defined in the group of non-zero integers modulo a big prime p, with modular multiplication as group law. The characteristics we look for are reached as long as p is large enough, e.g. at least 1024 bits (that's the minimal size for discrete logarithm to be hard in such a group).

Elliptic curve are another kind of group, appropriate for group-based cryptographic algorithm. An elliptic curve is defined with:


A finite field, usually consisting in integers modulo some prime p (there are also other fields which can be used).
A curve equation, usually $y^2 = x^3 + ax +b$, where $a$ and $b$ are constant values from the finite field.


The curve is the set of pairs of values $(x, y)$ which match the equation, along with a conventional extra element called "the point at infinity". Since elliptic curves initially come from a graphical representations (when the field consists in the real numbers $\mathbb{R}$), the curve elements are called "points" and the two values $x$ and $y$ are their "coordinates".

Then we define a group law, called point addition and denoted with a "$+$" sign. The definition looks quite artifical, with all the business about tracing a line and computing the intersection of that line with the curve; but the bottom-line is that it has the characteristics required for a group law, and it is easily computable (there are several methods; as a rough approximation, it costs about 10 multiplications in the base field). The curve order (the number of points on the curve) is close to $p$ (the size of the finite field): the curve order is equal to $p+1-t$ for some integer $t$ such that $|t| \leq 2\sqrt{p}$.

Compared to the traditional multiplicative group modulo a big prime, elliptic curve variants of cryptographic algorithms have the following practical features:


They are small and fast. There is no known efficient discrete-logarithm solving algorithm for elliptic curves, beyond the generic algorithms which work on every group. So we get appropriate security as soon as $p$ is close to 160 bits. Computing the group law costs ten field operations, but on a field which is 6 times smaller; since multiplications in a finite field have quadratic cost, we end up with an appreciable speedup.
Creating a new curve is uneasy. Generating a new big prime is a matter of
a fraction of a second with a basic PC, but making a new curve is much more expensive (the hard part is figuring out the curve order). Since there is no security issue in using the same group for several distinct key pairs, it is customary, with elliptic curves, to rely on a handful of standard curves which have been created such that their order is appropriate (a big prime value or a multiple of a big enough prime value); see FIPS 186-3. The implementations are thus specialized and optimized for these particular curves, which again considerably speeds things up.
Elliptic curves can be used to factor integers. Lenstra's elliptic curve factorization method can find some factors in big integers with a devious use of elliptic curves. This is not the best known factorization algorithm, except when it comes to finding medium-sized factors in a big non-prime integer.
Some elliptic curves allow for pairings. A pairing is a bilinear operation which can link elements from two groups into elements of a third group. A pairing for cryptography requires all three groups to be "appropriate" (in particular with a hard-to-solve discrete logarithm). Pairings are an active research subject because they can be used to implement protocols with three participants (e.g. in electronic cash systems, with the buyer, the vendor and the bank, all mathematically involved in the system). The only known practical pairings for cryptography use some special elliptic curves.


Elliptic curves are usually said to be the next generation of cryptographic algorithms, in order to replace RSA. Performance of EC computations is the main interest of these algorithms, especially on small embedded systems such as smartcards (in particular Koblitz curves over binary fields); the biggest remaining issue is that public-key operations with group-based algorithms are a bit slow (RSA signature verification or asymmetric encryption, as opposed to signature generation and asymmetric decryption, respectively, is extremely fast, whereas analogous operations in the group-based algorithms are just fast). Also, involved mathematics are a bit harder than with RSA, and there have been patents, so implementers are a bit wary. Yet elliptic curves become more and more common.