Elliptic Curves for Sane People

[!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 $𝑛\cdot 𝑃$. If $𝑛$ is large enough, it is computationally impossible to find $𝑛$ for $𝑄=𝑛\cdot 𝑃$, being given both $𝑄$ and $𝑃$, in a reasonable time.

What is a "reasonable time"?

Let’s suppose we have supercomputer that is able to compute ${10}^{12}$ point multiplications per second (generous assumption).

In a year, we have about $365\ast 24\ast 60\ast 60\simeq {31}^{\prime }{556}^{\prime }952$ seconds, that means we could compute:

$${31}^{\prime }{556}^{\prime }952\cdot {10}^{12}\simeq {10}^{19}\text{[keys/year]}$$

Let’s take a SECP256k1 private key for our example. The elliptic curve is over a 256-bit field, which means we have $2^{256}\simeq {10}^{77}$ possible keys.

$$\frac{{10}^{77}}{{10}^{19}}={10}^{77-19}={10}^{58}\text{[years]}$$

For reference, the age of the universe is about ${10}^{10}$ years :D

Even with a quantum computer capable of running non-stop, using Shor’s algorithm, you’d need to perform $\sqrt{2^{256}}=2^{128}\simeq {10}^{38}$ multiplications:

$$\frac{{10}^{38}}{{10}^{19}}={10}^{19}\text{[years]}$$

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 $\mathrm{𝒪︀}$.

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 ${𝑦}^2={𝑥}^3+𝑎𝑥+𝑏$.

Given two points $𝐴\left({𝑥}_{𝐴},{𝑦}_{𝐴}\right)$ and $𝐵\left({𝑥}_{𝐵},{𝑦}_{𝐵}\right)$, the resulting coordinates of the point $𝐶\left({𝑥}_{𝐶},{𝑦}_{𝐶}\right)=𝐴+𝐵$ can be found by:

1. Finding the slope $𝑚$ of the line between $𝐴$ and $𝐵$.

   $$𝑚=\frac{{𝑦}_{𝐵}-{𝑦}_{𝐴}}{{𝑥}_{𝐵}-{𝑥}_{𝐴}}$$

2. Finding the $𝑥$ coordinate of $𝐶$ by substituting $𝑦=𝑚\left(𝑥-{𝑥}_{𝐴}\right)+{𝑦}_{𝐴}$ into the curve equation.

   $$\begin{array}{c}{𝑦}^2={𝑥}^3+7\\ ⟺{\left(𝑚\left(𝑥-{𝑥}_{𝐴}\right)+{𝑦}_{𝐴}\right)}^2={𝑥}^3+7\\ ⟺\left({𝑚}^2{\left(𝑥-{𝑥}_{𝐴}\right)}^2+2𝑚\left(𝑥-{𝑥}_{𝐴}\right){𝑦}_{𝐴}+{𝑦}_{𝐴}^2\right)={𝑥}^3+7\\ ⟺{𝑚}^2{𝑥}^2-{𝑚}^{2}2{𝑥}_{𝐴}𝑥+{𝑚}^2{𝑥}_{𝐴}^2+2𝑚{𝑦}_{𝐴}𝑥+2𝑚{𝑦}_{𝐴}{𝑥}_{𝐴}+{𝑦}_{𝐴}^2={𝑥}^3+7\end{array}$$

   Grouping each power of $𝑥$ together nicely:

   $${𝑥}^3-{𝑚}^2{𝑥}^2+\left(2{𝑚}^2{𝑥}_{𝐴}-2𝑚{𝑦}_{𝐴}\right)𝑥+\left(7-{𝑚}^2{𝑥}_{𝐴}^2-{𝑦}_{𝐴}^2-2𝑚{𝑦}_{𝐴}{𝑥}_{𝐴}\right)=0$$

   We have an single-variable third degree equation, and our good old friend Viète tells us that for a polynomial $𝑃\left(𝑥\right)={𝑎}_0+{𝑎}_1𝑥+\dots +{𝑎}_{𝑛}{𝑥}^{𝑛}$ of degree $𝑛$, we have $𝑛$ roots:

   $$𝑃\left(𝑥\right)=0⟺\{\begin{array}{c}𝑥={𝑥}_1\\ 𝑥={𝑥}_2\\ \dots \\ 𝑥={𝑥}_{𝑛}\end{array}$$

   Among other properties, these roots ${𝑥}_{𝑖}$ always satisfy:

   $$\sum _{𝑖=0}^{𝑛}{𝑥}_{𝑖}={𝑥}_1+{𝑥}_2+\dots +{𝑥}_{𝑛}=-\frac{{𝑎}_{𝑛-1}}{{𝑎}_{𝑛}}$$

   Which means that in our case, we can write:

   $${𝑥}_{𝐴}+{𝑥}_{𝐵}+{𝑥}_{𝐶}=-\frac{-{𝑚}^2}{1}={𝑚}^2$$

   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 ${𝑥}_{𝐶}$:

   $${𝑥}_{𝐶}={𝑚}^2-{𝑥}_{𝐴}-{𝑥}_{𝐵}$$

3. Finding ${𝑦}_{𝐶}$ is as easy as plugging our freshly found ${𝑥}_{𝐶}$ into the equation of the line and reflecting it over the $𝑥$-axis:

   $${𝑦}_{𝐶}^{\prime }=𝑚\left({𝑥}_{𝐶}-{𝑥}_{𝐴}\right)+{𝑦}_{𝐴}$$

   ${𝑦}_{𝐶}^{\prime }$ is our intermediate point before it being reflected.

   $$\begin{array}{cc}{𝑦}_{𝐶}=-{𝑦}_{𝐶}^{\prime }& =-𝑚\left({𝑥}_{𝐶}-{𝑥}_{𝐴}\right)-{𝑦}_{𝐴}\\ & =𝑚\left({𝑥}_{𝐴}-{𝑥}_{𝐶}\right)-{𝑦}_{𝐴}\end{array}$$

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 $2\cdot 𝐺$.

To find the tangent at $𝐺\left({𝑥}_{𝐺},{𝑦}_{𝐺}\right)$, we need to find the slope $𝑚=\frac{𝑑𝑦}{𝑑𝑥}={𝑦}^{\prime }\left(𝑥\right)$.

Differentiating both sides with respect to $𝑥$, ${𝑦}^2$, which actually depends on $𝑥$ can be written as ${𝑦\left(𝑥\right)}^2$ for clarity:

See this as if we were differentiating ${𝑢}^2$, where $𝑢=𝑦\left(𝑥\right)$.

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 $𝑚={𝑦}^{\prime }\left(𝑥\right)$:

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

• A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography
  Nick Sullivan
  cloudflare.com

• Elliptic Curve Cryptography (ECC)
  Svetlin Nakov
  cryptobook.nakov.com