It's time to ellipse the shit out of some curves, bro! Elliptic Curve Cryptography makes normal factor-based cryptography look like child's play. Standard factor-based cryptography (like in the traditional Diffie-Hellman Key Exchange protocol) is also quite easy to grasp the concept of. Most of us were taught at a very young age about factoring, prime numbers, exponents, etc. Unfortunately with Elliptic Curve Cryptography (ECC), the concepts are quite foreign to most people, so they are more difficult to grasp. First off, if you even know what an elliptic curve is, you are already more advanced than I was when I started learning about it. ECC deals with a similar type of problem that makes the original DHKE so strong: the one way function.
As a refresher for the DHKE, you take a prime modulus, find a primitive root to use as a generator, raise it to a random secret number, perform the operation, send the result of that crap to someone else, they do the same thing and send their crap to you, you raise your secret crap to their crap, they raise their secret crap to your crap, and you come up with the same shared number (Please read my article on Crypto key exchange for an actual explanation of this process). This works well because of the difficulty in reversing this operation - the operation is easy to perform in one direction, and hard to perform in the other direction. The problem now is that computers are getting faster, and special algorithms have been developed to help reverse this problem with greater ease. This leads to the necessity of using larger numbers for this exponent/modulus operation (larger key size). This also results in requiring more computing resources to perform this one way function. This isn't really a problem for modern computers, but with devices like cell phones, dish washers, and coffee cups performing encryption now, they don't have as much computing resources as a regular computer. Enter elliptic curves. Elliptic curves have a formula of y2= x3 + ax + b, where a and b are parameters of the curve. The curve doesn't look like an ellipse, as the name implies, but rather a funky looking raindrop flipped on its side. The 'tails' of the curve will continue to infinity. The benefit of using elliptic curves in cryptography is that they require a smaller key size to provide the same level of protection. For instance, a 3072-bit traditional RSA key is comparable to a 256-bit ECC key. Much smaller, much happier. So, how exactly do elliptic curves work, and what properties do they have that allows for a one way function?
Here is an example of what an elliptic curve looks like:
Some of the interesting properties of an elliptic curve is the symmetry over the x-axis, and the property that for any non-vertical line drawn across the curve will intersect at most 3 points.
What if you want to add 2 points together? This operation is called a 'dot' operation. The way that you add points together is to draw a line through the 2 points, and where the third point intercepts, you mirror that across the x-axis. So in the above example, you draw a line connecting points 1 and 2 (shown) and end up with a 3rd point (also shown). You then draw a vertical line straight down from the third point, and where it intercepts below the x-axis is the sum of points 1 and 2. Below is an example of adding 2 points, P and Q, together. Notice that the result is -R, and R is the result only after it has been mirrored across the x-axis.
You can also add a point to itself, referred to as point doubling. How is this done? This is done by drawing a tangent line across the point (P) you want to double (a tangent line is a line what touches only a single point on a function). Then, where the tangent line intercepts the curve again, you draw that vertical line straight down to reflect the value across the x-axis, and that is the sum of P+P. Also to note, I keep saying to draw a vertical line and whatever is beneath the x-axis is the result; however, if the line already intercepts below the x-axis, you still draw a vertical line, but this time you reflect above the x-axis. SO, now we know how to perform point addition. We can continue this operation of adding P to itself to get increasing multiples of P (basically P+P+P+P+P..... n times). Below is an example of this.
Now here comes the basis of the elliptic curve discrete log problem (similar to what we saw in the modular arithmetic in classic Diffie-Hellman, but now it's pretty). SO, now that we know how to dot 2 points together, and how to dot a point to itself (doubling), how can you go backwards? For instance, in classic algebra, if I were to give you a function, say, 4n=20, and asked you what n was, it wouldn't take you long before you would calculate the answer to be 5, since you can divide 20 by 4 to get the answer. This same concept does not work in elliptic curves. So for instance, if I were to present you with the following elliptic curve with the starting point P, and ask you how many times P was dotted with itself to get the final result labeled "?P?.
You wouldn't have a clue, and that's the point (pun intended). In order to figure out how many times P was dotted with itself to get that value, you'd have to calculate all of the values one by one and perform trial and error, just as an attacker had to do in classic Diffie-Hellman.
Implementing this in Diffie-Hellman will feel familiar, where in DH, you are moving around the circle (seemingly) randomly, versus here you are moving around the curve (seemingly) randomly. You first establish the parameters of the elliptic curve, and the common starting/generator point P (as well as other shared domain parameters that I won't get into in this primer). So the value that you multiply P by is your secret key, and the result of that calculation gets sent to your friend, or grandma, or whoever. Then they do the same thing, and send you the value of their result from the same calculation using their own secret value. Then, each person takes the public value, multiplies it by their private value, and then multiplies the point P by that number In simple terms, if the secret value is 4, and generator point is 5, then you send the value of 20 to your friend. Their secret value is 6, and they send the value of 30 (6 x the generator point, 5) to you. You take their public value of 30 and multiply that by 4 (your secret number) to get 120. They take your value of 20 and multiple it by their secret value of 6 and get 120. 120 is now your shared key. As stated above, in normal algebra, this process is easy to reverse - but in the land of elliptic curves, division simply isn't feasible. Without the luxury of being able to divide, you are forced to resort to trial and error.
WARNING - MATHY SCARY THINGS 2 FOLLOW (but better drawings)
So obviously computers don't draw out the curve and draw lines across dots, but instead use mathematical formulas. So let's take a quick look at some elliptic curve formulas -
Let's build a simple curve with the parameters y2= x3 - x + 1 (the -x is because the value for "a" is -1, so rather than saying +-1x, we can just say -x)
As you've noticed, I've also selected 2 points to add, labeled P and Q. To start simple, the points are P(-1, 1) and Q(0, 1).
The first thing you have to do is determine the slope (lambda, λ). To determine the slope against 2 points, the equation is λ= yq - yp / xq - xp . That is, the y coordinate from point q minus the y coordinate from point p divided by the x coordinate from point q minus the x coordinate from point p.
In this case, λ=1 - 1 / 0 - -1, or more simplified, 0 / 1, which gives us 0. This makes sense, since the line between P and Q is straight, and the slope/rate of change is 0. OK, so the next thing we do is determine the x and y coordinates of the resultant point r. To find the x coordinate of r, we use the following formula -
xr= λ2 - xp - xq
Filled in with values, this is 02 - -1 - 0, which simplified down to 0+1-0. Solving this equation gives us the value 1 for the x coordinate, so xr=1
To find the y coordinate, we use the following formula -
yr= λ(xp - xr) - yp
Filled in with values, it is 0(-1 - 1) - 1. Solving this equation gives us -1. So now, we have the values for point r, which is r(1, -1). Following this using the geographical models shown above, this follows what we've learned so far.
This was a very simple example since the slope was 0, but if it wasn't 0, you would just substitute in whatever the slope turned out to be, and the numbers still work. But what about point doubling? There you have to find the tangent of P, so the formulas are a little different, but here we go. Below is a point P that we want to double.
In the above example, our new point P= (-.8, 1.135). To calculate the tangent line, we use the following, slightly more complicated formula to determine lambda -
λ= 3xp2 + a / 2yp
To dissect this, we multiply the squared x value of p by 3 and add that to the "a" parameter of the curve (the a value in y2= x3+ax+b. In this case, that value is -1), and then divide that value by the value of the y coordinate multiplied by 2. To fill this out with values, its 3*-.82 - 1/ 2(1.135). Simplifying this a step further, it equates to 3*.64 - 1 / 2.27, which equates to 0.92 / 2.27, which FINALLY equals .4052.
Now, we basically do the same operations as adding 2 points, but use the values of P for both P and Q for the addition operations. so for the x coordinate of the result point r, the formula again is this -
xr= λ2 - xp - xq
In our new case, xr= .40522 - -.8 - -.8, which gives us 1.764, so xr =1.764
To find the y coordinate, we also use the same formula as the addition operation for y above, which is this -
yr= λ(xp - xr) - yp
In our new case, yr= .4052(-.8 - 1.764) - 1.135, which equates to -1.038 - 1.135, which equals -2.173. SO, our results for the point doubling operation are the following coordinates -
Let's see if this looks right on a plot -
So for a computer to calculate 50P, it would perform a series of these doubling and addition functions. To calculate the value of 50P, a computer will determine P, double it to 2P, add P to get 3P, double it to 6P, double that to 12P, double that to 24P, add P to get 25P, then double that to get 50P. This is 7 steps. An attacker would have to perform all 50 steps, computing P+P+P+P+P...50 times. Once you start getting to extremely large multiples of P, these individual additions of P become infeasible, thus illustrating the strength of the one way function.
In most elliptic curve cryptosystems, the range of possible values is restricted from infinity, which is the theoretical maximum of the curve as shown by the 'tails' disappearing off the graph. Instead, a max value is set where all calculated ranges must fall. Anything that gets calculated outside of these bounds gets 'wrapped around' to fall within range. Sound familiar? This is using the same type of prime modulus functions that traditional diffie-hellman uses. Another parameter used is the order of the the base point P, which determines how many times P can be added to itself before the slope becomes infinite (a straight vertical line). The order isn't 'chosen', but rather a property of the value of the base point P. Ideally, the base point is chosen so that this order is a very large prime number, as well as the modulus selected for the restriction of curve values. Using large prime numbers (as I've stated ad nauseam) for these parameters is essential to making a strong cryptosystem.
Success! You now know some of the core mathematical functions associated with elliptic curves. Sweeeeeeeet bro.
TL;DR - Elliptic curves are confusing.