Crypto-series: Elliptic Curve Cryptography
After a long long while, it's time to go on with our crypto series. Last time we talked about the RSA cryptosystem, and we learned its security is based on the integer factorization problem (plus the DL problem for message secrecy). Today, we'll continue with public key cryptosystems: we'll look into Elliptic Curve Cryptography.
Elliptic Curves
If we are talking about Elliptic Curve Cryptography, first we need to define what an Elliptic Curve is. Mathematically, an Elliptic Curve 
This means that every point (x,y) for which the above expression is met will be part of the curve. However, it turns out in our case we can simplify the equation because the curves we'll be using can generally be written as:
Such a curve, over the reals (i.e. x and y are real numbers) and with a=-3, b = 1, looks like this:
Elliptic Curve y^2 = x^3 - 3x +1 over the real numbers
What makes these curves special is that we can define an abelian group with them. To do that, we define the point at infinity and an addition law. The addition law is depicted in the following picture from Wikipedia:
Elliptic Curve Addition law
As you can see, if you want to add two points P and Q, you draw a line through them. The intersection of this line and the curve is the point -(P+Q). Then, you just need to invert this point (negate the y coordinate) to obtain the final result.
Of course, we have special cases. If the point is added to itself, the line is defined as the tangent to the curve at that point, as intuitively the tangent touches 'two times' the point.
If we add a point to its inverse, we get a vertical line... and that's a problem because it will never touch the curve. Here is where the point at infinity comes to rescue. The point at inversity is simply 'up there' (and 'down there'), and is the zero element of the group.
Elliptic Curves for Cryptography
We have defined above how an elliptic curve looks like over the reals, and how to perform additions of two points. Obviously, when addition is defined we also have multiplication for free: just add a point to itself several times in a row (although you can do it in smarter and more efficient ways).
But how do we use it for cryptography? I mean, where is the difficult problem here? Actually, the difficult problem is again the discrete logarithm problem. In this case, we define it as follows:
Given a curve E and all its parameters, a base point P and a point Q=nP, obtain n.
And how is this difficult in the curves defined above, you might be thinking... The truth is we do not use real curves in ECC, but we use curves over finite fields instead. We can do it over prime fields GF(p), or we can do it over binary fields GF(2^n). I'll look only at GF(p) here, but similar concepts apply (although the simplified expression I defined above is slightly different in that case).
So, the curve I depicted previously taken over GF(8761) looks like this:
Elliptic Curve y^2 = x^3 -3x+1 over GF(8761)
Messy, huh? Exactly the same addition laws apply here, but now when you add two points you draw a line... and when the line gets out of the GF(p) x GF(p) plane it wraps around and comes back from the other side. It is a little more difficult to depict and to visualize, but the concept is the same as before. And now you probably start seeing why this is difficult to solve...
Why Elliptic Curves?
Now you might be wondering... why do we use Elliptic Curve cryptography at all? What are the benefits? The answer is that the ECC allows us to use smaller keys than other algorithms like RSA / 'normal' DL systems for the same amount of security.
This is because the best known general methods for solving the DL in Elliptic Curve are of exponential complexity, while for the other systems we know subexponential methods. Hence, the DL problem under Elliptic Curves is believed to be more difficult than the equivalent base problems for other public key cryptosystems.
Now that we know how elliptic curves are used in cryptography and what benefits they have over traditional
Elliptic Curve Diffie-Hellman
So, if you remember from when we talked about Diffie-Hellman, this is a key exchange protocol that relies on the Discrete Logarithm problem (and the Diffie-Hellman assumption). Usually this is done over a finite field GF(p), but now we have just defined a group based on Elliptic Curves which we can use as well.
In this case, Alice has a private key 
This protocol relies on the assumption that the DL problem is infeasible in the elliptic curve (which requires a base point G of high order) and the Diffie-Hellman assumption.
Other ECC algorithms
Besides the EC Diffie-Hellman algorithm defined above, there are several other algorithms based on Elliptic Curves. For example, one could compute digital signatures using Elliptic Curve DSA or Elliptic Curve Nyberg Rueppel. Each algorithm has its own details, but the important problem used as a foundation for each of them is the Discrete Logarithm problem over Elliptic Curves as we have defined it here.
Beware, however, that similarly to other algorithms, ECC algorithms rely also on other conditions. For example, for ECDSA (and DSA) there is a secret parameter that must be unique, and two signatures with the same value for this parameter will reveal your secret key. As usual, if you implement cryptography. you need to be aware of the requirements and limitations or you will certainly screw up (toc toc SONY!).