cstef
/posts/elliptic-curve

Elliptic Curves for Sane People

2024-11-29(6 min. read) - crypto

note

I am not a cryptographer, nor a mathematician. This article is the result of my own research and understanding of the subject. If you find any mistakes, please let me know!

The vast majority of what is written here is taken from various sources, which are listed at the end of this article. I highly recommend you to read them if you want to dive deeper into the subject.

Elliptic curve cryptography (ECC) is a fascinating field of study that has been around for a while. It's a cornerstone of modern cryptography, and it's used in many applications, from secure messaging to cryptocurrencies. RSA, the most widely used public-key cryptosystem, is slowly being replaced by ECC due to its efficiency and security.

The trapdoor function (easy to do one way, hard the other) for an elliptic curve is the multiplication of a point by a scalar which is just adding the point to itself times. This operation is denoted as . If is large enough, it is computationally impossible to find for , being given both and , in a reasonable time.

What is a "reasonable time"?

Let's suppose we have supercomputer that is able to compute point multiplications per second (generous assumption).

In a year, we have about seconds, that means we could compute:

Let's take a SECP256k1 private key for our example. The elliptic curve is over a 256-bit field, which means we have possible keys.

For reference, the age of the universe is about years :D

Even with a quantum computer capable of running non-stop, using Shor's algorithm, you'd need to perform multiplications:

Let's start out by graphically representing the addition of two points and in an elliptic curve.

One easy way to think of the addition is to draw a line that goes through and , and find the third point of intersection with the curve. The symmetrical point is the result of the addition of and . This is because elliptic curve have the property that any line between two points intersects the curve at most one more time.

In the case where there is no third point of intersection (i.e. the line is vertical), we define the result of the addition as the point at infinity, denoted as .

The resulting point is then reflected to over the x-axis. This symmetry property is easily explained by the fact that the curve's coordinates are squared, so for a given coordinate, there are two possible coordinates, and .

The operation can then be done over and over again to find subsequent points.

note

We will be working with Short Weierstrass form curves, which are the most common form of elliptic curves used in cryptography. The equation of the curve is .

Given two points and , the resulting coordinates of the point can be found by:

  1. Finding the slope of the line between and .

  2. Finding the coordinate of by substituting into the curve equation.

    Grouping each power of together nicely:

    We have an single-variable third degree equation, and our good old friend Viète tells us that for a polynomial of degree , we have roots:

    Among other properties, these roots always satisfy:

    Which means that in our case, we can write:

    Because we already know that the line will intersect with and (the grouped equation will be satisfied at both and ), we are left with only :

  3. Finding is as easy as plugging our freshly found into the equation of the line and reflecting it over the -axis:

    is our intermediate point before it being reflected.

In the case where , we can't really draw a line between the two points, so we take the tangent to the curve at and find the third point of intersection. This is the result of the addition of with itself, denoted as .

To find the tangent at , we need to find the slope .

Differentiating both sides with respect to , , which actually depends on can be written as for clarity:

See this as if we were differentiating , where .

The right side is just a function of , so we can differentiate it as we would with any other function:

Our differentiated equation is:

Solving for :

Notice that the tangent's slope depends on both and , which makes sense because we'd have two different slopes otherwise:

And we have our tangent equation for and :

Working with finite fields

Elliptic curves are defined over a finite field, which means that all operations are done modulo a prime number . This is done to ensure that the curve has a finite number of points, which is necessary for cryptographic applications.

References and Suggested readings