Elliptic cryptography

Elliptic curves are a very important new area of mathematics which has been greatly explored over the past few decades. They have shown tremendous potential as a tool for solving complicated number problems and also for use in cryptography.

In 1994 Andrew Wiles, together with his former student Richard Taylor, solved one of the most famous maths problems of the last 400 years, Fermat's Last Theorem, using elliptic curves. In the last few decades there has also been a lot of research into using elliptic curves instead of what is called RSA encryption to keep data transfer safe online.

Public and private

Elliptic curve cryptography, just as RSA cryptography, is an example of public key cryptography. The basic idea behind this is that of a padlock. If I want to send you a secret message I can ask you to send me an open padlock to which only you have the key. I then put my message in a box, lock it with the padlock, and send it to you. The good thing about this approach is that the message can be sent over insecure channels — even if someone intercepts the box, they don't have the key — and that we don't both need a key to the box. You could even get lots of people to send you secret messages in this way, without ever having to give away a single key.

In public key cryptography messages are encrypted using particular pieces of mathematical information, which constitute the public key — that's the open padlock and performing the encryption is like snapping the padlock shut. Decryption is only possible using a mathematical private key, which is next to impossible to determine if you only know the public key.

In RSA cryptography the public key involves a natural number $N,$ which is used by computers to encrypt messages. To decrypt a message, you need to know the factors of $N.$ If $N$ is very large, then factoring it takes such a large amount of computing power that breaking the code is practically impossible. Only people (or, realistically, computers) in possession of the private key — the factors of $N$ — can decrypt the message easily. (You can find out more about RSA here.)

Elliptic curves

Elliptic curve cryptography is based on the difficulty of solving number problems involving elliptic curves. On a simple level, these can be regarded as curves given by equations of the form

$$y^2 = x^3 +ax +b,$$

where $a$ and $b$ are constants. Below are some examples. In each case the graph shows all the points with coordinates $(x,y)$, where $x$ and $y$ satisfy an equation of the form shown above.

For the sake of accuracy we need to say a couple of words about the constants $a$ and $b.$ For an equation of the form given above to qualify as an elliptic curve, we need that $4a^3 + 27b^2 \neq 0.$ This ensures that the curve has no singular points. Informally, it means that the curve is nice and smooth everywhere and doesn't contain any sharp points or cusps. In the examples above the constants $a$ and $b$ were chosen to be whole numbers between $-2$ and $1,$ and $-1$ and $2$ respectively. But in general they can also take on other values. (For uses in cryptography $a$ and $b$ are required to come from special sets of numbers called finite fields). You can find out more about elliptic curves in this article.

Adding points

Given an elliptic curve, we can define the addition of two points on it as in the following example.

Let's consider the curve $$y^2=x^3 - 4x +1$$ and the two points $A=(2,1)$ and $B = (-2, -1),$ which both lie on the curve. We now want to find an answer for $A + B$ which we would also like to lie on the elliptic curve. If we add them as we might vectors we get $(2,1) + (-2,-1) =(0,0)$ – 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$ with a straight line. This line generally intersects the curve in one more place, $C.$ We then reflect the point $C$ in the $x$-axis. We declare this new point, $C^\prime,$ to be the sum of $A$ and $B. $ So $$A + B = C^\prime.$$ In our example this means that $$(2,1) + (-2,-1) = (1/4, -1/8).$$ Trying another example, $$y^2 = x^3 -5x + 4$$ (shown below), with $A = (1,0)$ and $B = (0,2),$ we have $C = (3,-4)$ and $C^\prime = (3,4)$. Therefore $$(1,0) + (0,2) = (3,4).$$ We also need a definition for the sum when $B=A$ to understand what we mean by $A+A = 2A.$ In this case we take the tangent to the curve at the point $A$, and then as before find the intersection of this tangent line and the curve, before reflecting the point. This is probably easier to understand with another graph: Here we use the elliptic curve $$y^2 = x^3 -12x.$$ and consider the point $A = B = (-2, 4).$ We have drawn the tangent to the curve at $A,$ which intersects the curve at a second point $C=(4,4).$ Reflecting in the $x$- axis gives $C^\prime = (4, -4).$ Therefore we say $2A = C^\prime,$ or $2(-2, 4) = (4, -4).$ It's now possible to define what we mean by $nA$ for any point $A$ on the curve and any natural number $n>0:$ $$2A = A+A,$$ $$3A = 2A+A,$$ $$4A = 3A+A,$$ and so on. The only situation in which our definition of $A+B$ doesn't work is when $B$ is the reflection of $A$ in the $x$-axis (which in the case where $B=A$ means that $A$ itself lies on the $x$-axis). In this case, the line we use to define the sum is vertical and there isn't a third point at which it meets they curve. We can get around this problem by adding an extra point to the usual $(x,y)$ plane, called the point at infinity and denoted by $O.$ To make the addition work for our exceptional situation we simply define $A+B=O.$ For any point $A$ we also define $A+O= A$ — so with our new notion of addition, the point $O$ plays the same role as the number $0$ in ordinary addition. It turns out that, given two points $A$ and $B$ on an elliptic curve, finding a number $n$ such that $B = nA$ (if it exists) can take an enormous amount of computing power, especially when $n$ is large. Elliptic curve cryptography exploits this fact: the points $A$ and $B$ can be used as a public key, and the number $n$ as the private key. Anyone can encrypt a message using the publicly available public key (we won't go into the details of the encryption method here), but only the person (or computer) in possession of the private key, the number $n,$ can decrypt them.

NSA and hacking data

Elliptic curve cryptography has some advantages over RSA cryptography – which is based on the difficulty of factorising large numbers – 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 elliptic 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 elliptic 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 elliptic 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.

---

Further reading

To find out more about the development of codes, including modern elliptic curve cryptography, and their links to mathematics, the book by William Stein, Elementary Number Theory: Primes, Congruences and Secrets is an good starting place. Numberphile have also covered the NSA's attempts to circumvent elliptic curve cryptography in one of their ever excellent videos.

---

About the author

Andrew Chambers has an MSc in mathematics and is a teacher at the British International School Phuket, Thailand. He has written news and features articles for the Guardian, Observer and Bangkok Post, and was previously shortlisted for the Guardian's International Development Journalist of the Year Awards. Combining his love of both writing and mathematics, his website ibmathsresources.com contains hundreds of ideas for mathematical investigations (and some code breaking challenges) for gifted and talented students.