Elliptic Curve Cryptography

Why are Elliptic Curves Necessary?

To answer this question, some basic knowledge about elliptic curves is necessary. Essentially, an elliptic curve is defined by the equation y2 = x3 + ax + b which can look something like the picture below.

Alt text

Along this curve, there are two points, P and Q. The addition of these two points can be solved with geometery, or by drawing a straight like through them and looking at the inverse of the point on the curve that this line intersects. Hence, P + Q = R. Much like regular addition, this is both communitive and associate, a fact which will be become more relavent later on.

Along with these points, is a openly known base point called G. This is a very special point that when multiplied with any integer will produce a point along the elliptic curve,or in otherwords, all multiples of G lie on this elliptic curve. Each curve along a finite field has certain paramters including base point G, prime modulo m, and curve equation C. These shared parameters are going to be useful later on in the exchange of information within a “public” setting.

Following this, P and Q are multiples of point G, so any point along the curve can be computed as mG. When this m is very large and trying to solve for R, simple division does not work and the problem becomes exponentially difficult to solve.

How to use Elliptic Curves with Cryptography

We are going to use the same basic principles of elliptic curves, and tie them together with a key-agreement protocal to discuss an ulta secure form of communication called ECDH or Elliptic Curve Diffie-Hellman. Like in the simple example above, we are going to use the principle R = P + Q to derive a secret code.

Lets say we have two people, Alice and Bob. We want them to be able to communicate through a secret channel and we want both of them to agree on the same password for that channel. Now, for this to be truly secure, they must agree on this password and without any prior communication (such as a phone call or text message). How could this be possible?

Well, first we assign Alice and Bob both a private key and a public key. Their private key is a random, secret integer d ranging from [1 , (n-1)] (in our case, [1 , 1.1579209e+77]) and their public key is the point F, where F = d G. For Alice we will call this point FP, and for Bob it will be FB. Now, Alice and Bob are both missing some information to obtain the secret password, mainly the other person’s private key. Therefore, Alice and Bob will exchange their public keys.

Alice will give Bob FP(dAG), and Bob will give Alice FB(dBG). Using these public keys from the other person along with their own private key, they can figure out the same secret key!

Alt text

How exactly does this work? Well, multiplying both private keys and the base point together will produce a point along the curve (since it is multiplied with G). As long as both Alice and Bob recieve each other’s public keys, multiplication will be communitive and they will both compute the same point R without ever explicitly knowing each other’s secret integer.

You may also question, well wait, in the previous example we were adding P and Q, and now we are multiplying them? How does this still work? The principle is still the same. Since P and Q are both multiples of this base point G, then their product is also a multiple of G (since a multiple is really just addition many times over).

Now, lets say there is a “man in the middle” attack, or someone happens to intercept FP and FB. What then?

Well, as it turns out, knowing these two peices of information will not yield helpful. To figure out the secret, the middle man needs dA or dB, both of which require solving F = dG for d, a discrete logarithm and np-hard problem. You may think, well, why can’t this hacker just guess and check his way to the right value? This is certainly not as simple as it sounds.

To give some perspective on np-hard problems, np stands for nondeterministic polynomial time. Solving np-hard problems within an possible amount of time even on a super computer has not yet been done, and so they remain, in a sense, “unsolvable”.

Using Temporary Keys and Digitial Signitures

How can this possibly get any more secure than it already is?

First, instead of using keys that Alice and Bob will keep forever, new keys will be generated every time Alice and Bob want to make a connection. This is called Ephemeral ECDH and this sort of solution is used in a wide variety of client/server communications. This becomes particularly important when things may get stored on the browser, leaving vulnerabilities at the end point. Along with this, it also makes sure that the same d is not getting reused every time, which would indeed make the code much harder to crack.

Second, we want to include digital signitures to confirm that indeed Alice is the one sending her public key, and Bob is indeed sending his. This prevents the “man in the middle” from sending his own generated public keys because the digitial signiture will not be confirmed from the other side. Bob can validate that Alice is indeed herself by using the public key that she sends. Because Alice and Bob are using the same domain parameters (such as field size, modulo value, G), then a secret message can be made using those values, and can be confirmed by the other party. Again, in order to solve for some of these values resolves to an np-hard problem, leaving the malicious intruder in a less than preferable situation.