Elliptical Curve Cryptography

This post builds on some of the ideas in the previous post on elliptical curves.  The excellent Numberphile video above expands on some of the ideas below.

On a (slightly simplified) level elliptical curves they can be regarded as curves of the form:

y² = x³ +ax + b

So for example the curve below is an elliptical curve.  This curve also has an added point at infinity though we don’t need to worry about that here.  Elliptical curve cryptography is based on the difficulty in solving arithmetic problems on these curves.  If you remember from the last post, we have a special way of defining the addition of 2 points.

Let’s say take 2 points A and B on y² = x³ -4x + 1. In the example we have A = (2,1) and B = (-2,1). We now want to find an answer for A + B which also is on the elliptical curve. If we add them as we might vectors we get (0,2) – but unfortunately this is not on the curve. So, we define the addition A + B through the following geometric steps.

We join up the points A and B. This line intersects the curve in one more place, C.

We then reflect the point C in the x axis. We then define this new point C’ = A + B. In this case this means that (2,1) + (-2,1) = (1/4, -1/8).

Trying another example, y² = x³ -5x + 4 (below), with A = (1,0) and B = (0,2) we have C = (3,-4) and C’ = (3,4). Therefore (1,0) + (0,2) = (3,4).

We also need to have a definition when A and B define the same point on the curve. This will give us the definition of 2A.  In this case we take the tangent to the curve at that point, and then as before find the intersection of this line and the curve, before reflecting the point.  This probably is easier to understand with another graph:

Here we used the graph y² = x³ -5x + 4 again.  This time point A = B = (-1.2, 2.88) and we have drawn the tangent to the curve at this point, which gives point D, which is then reflected in the x axis to give D’. D’ = (2.41, -2.43).  Therefore we can say 2A = D’, or 2(-1.2, 2.88) = (2.41, -2.43).

Now addition of points is defined we can see how elliptical curve cryptography works.  The basic idea is that given 2 points on the curve, say A and B, it takes a huge amount of computing power to work out the value a such that aA = B.  For example, say I use the curve y² = x³ -25x to encrypt, and the 2 points on the curve are A = (-4,6) and B = (1681/144 , -62279/1728).  Someone who wanted to break my encryption would need to find the value a such that a(-4,6) = (1681/144 , -62279/1728).   The actual answer is a =2 which we can show graphically.  As we want to show that 2(-4,6) = (1681/144 , -62279/1728) , we can use the previous method of finding the tangent at the point (-4,6):

We can then check with Geogebra which shows that B’ is indeed (1681/144 , -62279/1728).  When a is chosen so that it is very large, this calculation becomes very difficult to attack using brute force methods – which would require checking 2(4,-6), 3(4,-6), 4(4,-6)… until the solution (1681/144 , -62279/1728) was found.

NSA and hacking data

Elliptical curve cryptography has some advantages over RSA cryptography – which is based on the difficulty of factorising large primes – as less digits are required to create a problem of equal difficulty.  Therefore data can be encoded more efficiently (and thus more rapidly) than using RSA encryption.  Currently the digital currency Bitcoin uses elliptical curve cryptography, and it is likely that its use will become more widespread as more and more data is digitalised.  However, it’s worth noting that as yet no-one has proved that it has to be difficult to crack elliptical curves – there may be a novel approach which is able to solve the problem in a much shorter time.  Indeed many mathematicians and computer scientists are working in this field.

Government digital spy agencies like the NSA and GCHQ are also very interested in such encryption techniques.  If there was a method of solving this problem quickly then overnight large amounts of encrypted data would be accessible – and for example Bitcoin currency exchange  would no longer be secure.  It also recently transpired that the NSA has built “backdoor” entries into some elliptical curve cryptography algorithms which have allowed them to access data that the people sending it thought was secure.   Mathematics is at the heart of this new digital arms race.