Elliptic curves over finite fields

After a quick introduction to simple elliptic curves used in cryptography and finally for securing our online communication, we cannot move forward without solving one major problem. How to represent these curves, and all of their points thereof, in computer memory. Why this is a major problem? There is an infinite number of real numbers, but computers can store only a finitely-sized things – including numbers. I’d like to explain how we can overcome this inherent trouble and show you that anyone can understand these modern cryptographic fundamentals.

As elliptic curve is actually a two-dimensional object on the infinite plane of pairs of real numbers^[1], our problem is – for a lack of better words – squared. Picture 1 shows an elliptic curve satisfying a simple Weierstrass equation. Actually it depicts only a very small part of it around the origin of the coordinate system. We all intuitively understand that the curve continues to positive and negative infinity on the Y axis (infinitely up and down) as we move towards the infinity on the X axis – that is to the right.

Picture 1: Elliptic curve satisfying the simple Weierstrass equation: $y^2=x^3-2x+2$

But how can we work with infinite numbers without losing precision? Trust me – even the slightest deviation from exact numbers means, the whole scheme will be useless for practical cryptography. What if we could limit the curve to finitely-sized plane? Would that work?

Of course it works – but we cannot do it naively. We have to invoke a bit of mathematical magic. The domain we can use is called finite field^[2] and it has two important properties:

1. you can go in any direction infinitely,
2. if we count all distinct object forming the field, there is an finite number of them.

Sounds familiar? Of course, for one dimension, such object would be a circle. You can go around it infinitely and yet, it is contained within a finite two-dimensional space. How about two dimensions? We can cut a small part from the infinitely large two-dimensional plane and wrap it around a torus. Once again, you can walk infinitely in any direction, yet it is contained within a finite three-dimensional space.

We are almost there – we have limited our infinitely large plane to finite one. But still there is an infinite number of points on any line and also in any two-dimensional object with non-zero size. Think about rectangles, circles, polygons or cartoon characters. They all occupy finite space but you can divide them infinitely! The last part of the trick we need to perform is that we forget about this divisibility and keep only whole numbers in our finite field. For one-dimensional circle that would be the clock circle where we use only hours for example. But that is not the best example, because in order for this to work properly, the size of the finite field should be a prime number[3]. For example a 23-hour clock would do the job.

And that is it. Now we only map our elliptic curve on this torus and we can easily see, what actually lies behind our digital signatures and TLS handshakes. And if you got this far, have a look at the following video where you can see how we create a doughnut sprinkled with sugar.

Video 1: mapping elliptic curve specified by the simple Weierstrass equation $y^2=x^3-2x+2$ over finite field $GF(23)$

You probably guessed it is not actual sugar. The rational points shown in the video and picture 2 are points where the curve – as we have winded it around the torus – hits the crosses of the grid. Remember – not only limited size, but also object (point) count must be finite. As mentioned above, in order for this magic to work properly, it is best to use finite field of prime size – in our examples we always use finite field of size 23. The finite field is sometimes called Galois^[4] field and its denoted $GF(p)$ where $p$ means “prime”. Our field is therefore $GF(23)$.

Picture 2: Elliptic curve satisfying the simple Weierstrass equation: $y^2\equiv x^3-2x+2\mod 23$

In mathematics we use an operation called modulo to force numbers to stay lesser than some specified number. Sounds complicated, but this operation is nothing more than a remainder after an integer division – which everyone remembers from elementary school. And in case you wonder what that $\equiv$ symbol means – it is called congruence and basically it states that both sides of the equation are the same under the operation modulo 23 in this case. Of course you can use regular equal sign but then you would have to write the modulo on both sides of the equation so mathematicians usually lean towards this notation.

And that is all, folks. I promised everyone can understand how this works.

Rest assured that working with elliptic curves over a finite field can be a lot of fun and everyone can dig even deeper into how it works and how we can leverage it for actually encrypting or signing something. But we will get to that eventually. See ya!

References

1. Wikipedia contributors. (2018, February 22). Real number. In Wikipedia, The Free Encyclopedia. Retrieved 20:39, February 24, 2018, from https://en.wikipedia.org/w/index.php?title=Real_number&oldid=827131029

2. Weisstein, Eric W. “Finite Field.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/FiniteField.html

3. Wikipedia contributors. (2018, February 24). Prime number. In Wikipedia, The Free Encyclopedia. Retrieved 20:48, February 24, 2018, from https://en.wikipedia.org/w/index.php?title=Prime_number&oldid=827434633

4. Wikipedia contributors. (2018, February 10). Évariste Galois. In Wikipedia, The Free Encyclopedia. Retrieved 20:47, February 24, 2018, from https://en.wikipedia.org/w/index.php?title=%C3%89variste_Galois&oldid=824956034