Elliptic Curve and Shenanigans for Sane People

A gentle introduction to elliptic curve cryptography, without the need for a PhD in mathematics.

04/12/2024 · 6 min read · sapling 🪴

Info

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 n dot P n dot P . If is large enough, it is computationally impossible to find for Q = n dot P , 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 10^12 point multiplications per second (generous assumption).

In a year, we have about 365 * 24 * 60 * 60 tilde.eq 31'556'952 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 2^256 tilde.eq 10^77 possible keys.

For reference, the age of the universe is about 10^10 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) tilde.eq 10^38 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 cal(O) cal(O) .

The resulting point B = G + A 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.

Given two points A(x_A, y_A) and B(x_B, y_B) , the resulting coordinates of the point C(x_C, y_C) = A + B can be found by:

Finding the slope of the line between and .
Finding the coordinate of by substituting into the curve equation.
$y^2 = x^3 + 7 \ <==> (m(x - x_A) + y_A)^2 = x^3 +$ $y^2 = x^3 + 7 \ <==> (m(x - x_A) + y_A)^2 = x^3 +$
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 :
Finding is as easy as plugging our freshly found into the equation of the line and reflecting it over the -axis:
$y'_C = m(x_C - x_A) + y_A \$ $y'_C = m(x_C - x_A) + y_A \$
is our intermediate point before it being reflected.
$y_C = -y'C &= -m(x_C - x_A) - y_A \ &= m(x$ $y_C = -y'C &= -m(x_C - x_A) - y_A \ &= m(x$

In the case where G = A G = A , 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 and , denoted as 2 dot G 2 dot G .

To find the tangent at G(x_G, y_G) , we need to find the slope m = (d y)/(d x) = y'(x) .

Differentiating both sides with respect to , y^2 y^2 , which actually depends on can be written as y(x)^2 y(x)^2 for clarity:

See this as if we were differentiating u^2 u^2 , where u = y(x) .

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 m = y'(x) :

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 x_G x_G and y_G y_G :

$t: y &= m(x - x_G) + y_G \ &= (3x_G^2)/(2y_G)$ $t: y &= m(x - x_G) + y_G \ &= (3x_G^2)/(2y_G)$

References / 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