Introduction to elliptic curves

We are about to start a journey to the realm of elliptic curve cryptography. It may seem strange at this point as why we should bother with that, but rest assured that we will eventually find out how to use this knowledge to secure our email communication. In this introduction, you can expect to see what an elliptic curve looks like, how it is defined and how it can be simplified if we want to make some practical use of it.

Although the name says “elliptic”, elliptic curve is definitely not an ellipse. But – as ellipse – it is an one-dimensional object defined in two-dimensional plane. Its definition basically says: the curve is formed from all points in the plane, which solve the Weierstrass equation. The equation is named for Karl Weierstrass^[1], who studied elliptic functions extensively during the nineteenth century and the general form of such equation is:

$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$

First thing you might notice, it is not simple. Second one may be the fact, the $a_5$ coefficient is missing. That is just a matter of history and to avoid confusion, mathematicians even today use this coefficient naming. But how does such curve look like? To give you an impression, you can find one in picture 1.

Picture 1: Elliptic curve defined by Weierstrass equation $y^2+2xy-y=x^3+2x^2+x+3$

It is true, as mentioned above, the equation is not actually simple. And it is also true that mathematicians like to simplify things when possible. In this case we can use Riemann-Roch’s theorem^[2] – actually its variation studied by Friedrich Karl Schmidt^[3] – applied to algebraic curves. As long as the genus of the curve remains the same and we are working in the same topological space, we can easily transform the equation into much simpler form using the following transformation – effectively transforming the coordinate system:

$x’=u^2x+r$

$y’=u^3y+su^2x+t$

You might be wondering why am I talking about simplification when it looks even more complex than before? It is rather simple, somebody has already done the job of calculating the proper values for $r$, $s$, $t$ and $u$ and they are:

$r=-\frac{a_1^2+4a_2}{12}$

$s=-\frac{a_1}{2}$

$t=\frac{a_1^3+4a_1a_2-12a_3}{24}$

$u=1$

Yes, it looks even worse, but you can probably guess, that as long as you have some initial coefficients, calculating these is just a matter of calculating their values – which is something a computer can do at virtually no cost. But what is the result? The result is that coefficients $a_1$, $a_2$ and $a_3$ become zero after this transformation and by using $a=a_4$ and $b=a_6$ for the two remaining coefficients, we get the simplified Weierstrass equation which is much better to work with:

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

The transformation from generic Weierstrass equation to simplified can be seen in the following video:

And the resulting simplified curve can be seen in picture 2.

Picture 2: Elliptic curve defined by simplified Weierstrass equation $y^2=x^3-3x+5.25$

In case you wonder how the coefficients $a$ and $b$ were calculated, you can get the idea:

$a=-2st-a_1(t+rs)-a_3s+3r^2+2a_2r+a_4$
$b=-t^2-a_1rt-a_3t+r^3+a_2r^2+a_4r+a_6$

Once again – this might seem pretty complex, but remember that this is a solved equation and if you want to know the numbers, that is when some computing machinery comes handy.

I hope this got you excited about elliptic curves and maybe next time we will fast forward on to how these elliptic curves form a basis of very interesting cryptographic schemes. See you then!

References

1. Karl Weierstrass. (2018, February 13). In Wikipedia, The Free Encyclopedia. Retrieved 21:17, February 18, 2018, from https://en.wikipedia.org/w/index.php?title=Karl_Weierstrass&oldid=825470901

2. Riemann–Roch theorem. (2017, December 21). In Wikipedia, The Free Encyclopedia. Retrieved 21:15, February 18, 2018, from https://en.wikipedia.org/w/index.php?title=Riemann%E2%80%93Roch_theorem&oldid=816382095

3. Friedrich Karl Schmidt. (2017, October 22). In Wikipedia, The Free Encyclopedia. Retrieved 21:15, February 18, 2018, from https://en.wikipedia.org/w/index.php?title=Friedrich_Karl_Schmidt&oldid=806504696