Elliptic Curve Cryptography

This post will cover how and why ECC works, which mathematical theorems are used and why. All from a layman’s point of view.

What is ECC?

Elliptic Curve Cryptography (ECC) uses the properties of an elliptic curve to provide a form of public-key cryptography used in key agreement protocols, such as Elliptic-curve Diffie–Hellman, or to create digital signatures via the Elliptic Curve Digital Signature Algorithm used e.g. to sign Bitcoin transactions.

But before we look at the math that is involved with these curves, let’s look at one of these curves first and get an intuitive understanding of what they are and what we can do with them.

What is an elliptic curve?

Elliptic Curve >

An elliptic curve is a curve of the form

\[y^2 = x^3 + ax + b\]

with the further condition that

\[4a^3 + 27b^2 \ne 0\]

so that there are no singular points.

What can we do with this curve?

This curve allows us to perform functions, that are easy to do if you know certain information, but nearly impossible if you don’t have it. This is used in digital signatures where there is a public key, that everybody knows and a private key, that only one person (us, in this example) knows. If we want to prove that we sent a message (or, for example, a Bitcoin transaction) we sign the message with our private key. Everyone else can use our public key to confirm that it was indeed us, because only we know the private key corresponding to the public key.

This is quite abstract, what does this mean for our curve?

On our curve, we can add points together. An addition is defined as taking the two points, say \(P\) and \(Q\) and “drawing” a line through them, with the result \(R\) being the point at which the line intersects with the curve the 3rd time mirrored over the x-axis. Elliptic Curve Addition <>

\[P + Q = R\]

But what if we want to add a point to itself, that is, double the point? In this case, the two points are infinitely close together and we use the tangent of the curve at that point. The rest is the same, intersect it with the curve and mirror it along the x-axis Elliptic Curve Doubling <>

\[P + P = 2P = R\]

This is where the security comes in. Say someone gave you point \(R\), how would you, for example, divide it by 2 to get P? Well, it’s not possible (i. e. very difficult and time consuming). This is a key point to the security of our system.

Elliptic curves in finite fields

Elliptic Curve Doubling > While these elliptic curves were nice to look at and give a nice understanding of what happens visually, all of these curves were shown over the set of real numbers \(\mathbb{R}\). The curves that are actually used, though, are curves over a finite field \(n\mathbb{Z}\), that is, a finite field of integers modulo some prime number \(n\), it must be prime so that each number has an inverse element (more on that in the next step). We do this so that we have a known, closed field of points. Just imagine if we suddenly arrived at a point with a coordinate that was too large for our computer to handle or at an irrational coordinate like \(\sqrt2\), how many bits would we use to store the exact location? 32? 64? As we see, unless we are conformed to a finite field we quickly run into problems.

The math of point addition and multiplication in finite fields

Now, given two points (different or same) how do we actually calculate the resulting point \(R\)? Since we are working in \(n\mathbb{Z}\) some calculations aren’t that straightforward.

1. Calculating the line through \(P\) and \(Q\)

1.1 Calculating the slope when \(P \neq Q\)

While addition, multiplication, exponentiation etc. with whole numbers are relatively straightforward in our finite space, we cannot simply divide numbers. In this case, calculating the slope \(m\) of our line as \(\frac{p_y - q_y}{p_x - q_x}\) would not work as the result could be a non-integer number. Instead, we rewrite the calculation as \((p_y - q_y) * (p_x - q_x)^{-1}\). Now we must find the modular multiplicative inverse \(x\) so that \(x * (p_x - q_x) = 1\). Luckily, because we are working in a finite field modulo a prime number it is guaranteed that there is one!

Let’s see why this is the case. Let’s say we have a number \(a\) and want to find the modular multiplicative inverse \(x\) so that

\[ax \equiv 1 \quad (\text{mod } n)\]

First, we will want to apply the extended Euclidean algorithm so that we get the greatest common denominator (gcd) such as the two coefficients of Bézout’s identity. As Wikipedia puts it:

“Bézout’s identity

Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d. More generally, the integers of the form ax + by are exactly the multiples of d.”

This means that

\[ax + by = gcd(a, b)\]

Furthermore, if a and b are coprime their gcd is 1 by definition. Since we chose \(n\) as a prime and \(a \lt n \Rightarrow a \text{ and } n \text{ are coprime}\). So, calculating the coefficients of Bézout’s identity of \(a\) and \(n\) all mod \(n\) would give us

\[ax + ny = 1 \quad (\text{mod } n)\]

And since

\[ny \text{ mod } n = 0\]

we get

\[ax = 1 \quad (\text{mod } n)\]

So one of the factors of Bézout’s identity will be our modular multiplicative inverse, perfect!

1.2 Calculating the slope when \(P\) = \(Q\)

Knowing how to divide in finite space from the step above, calculating \(m\) as the tangent of our curve is relatively easy, as we can use the derivative of our function:

\[m = \frac{3p_x^2+a}{2p_y}\]

2. Cutting the line with the curve

To start off, we just set the two functions equal:

\[(y_p + s * (x-x_p))^2 = x^3 + ax + b\]

We can rewrite this as:

\[x^3 - s^2x^2 + x * (a + 2s^2x_p - 2sy_p) + b - (y_p + sx_p)^2 = 0\]

Now, using Vieta’s formula \(x_1 + x_2 + x_3 = -\frac{b}{a}\), where \(x_n\) are the roots of the function, we see that:

\[s^2 - x_p - x_q = x_r\]

We can now plug in \(x_r\) into either of the two functions to get \(y_r\). Then we just take that \(* (-1)\) to mirror it across the x-axis and we get our point \(R\).

The security

We can now move on to understand where the security of our system comes from. Imagine we have a point \(A\) on our curve and multiply it by a factor of \(x\) we get a new point \(B\). Even if someone knew \(A\) and \(B\) there is no way determining \(x\) other than testing every possible value. If \(x\) is sufficiently large (e.g. \(2^{256}\)) this will take very long. One last step is figuring out how we who know \(x\) can quickly multiply a point.

Math of efficient scalar point multiplication

If we just added the point \(A\) to itself \(x\) times we would be doing the same work that the attacker would have to do. Instead, we will use the Double-and-add method. The idea behind this method is to first start with the binary representation of \(x\), i.e. in terms of powers of two. We can easily compute powers of two of \(A\) by repeatedly doubling \(A\). Now we just sum up the corresponding powers of two times \(A\) wherever there is a 1 in the binary form of \(x\).

\[B = \sum_{n=0}^{log_2(x)} \begin{cases}\begin{align} A*2^n, \text{if } x_n = 1 \\ 0, \text{if } x_n = 0 \end{align}\end{cases}\]

Note that we can save \(A*2^n\) to quickly calculate \(A*2^{n+1}\) This way we only have \(log_2(x)\) iterations of point adding and doubling.

Actually doing useful stuff

We have now covered the basic principles of ECC, now we’ll look at how this can be used for cryptography.

To make sure that these mathematical operations work, all parties that are involved in the process need to agree on several parameters.

p: Our prime number defining the finite field

a, b: Coefficients which define the curve

G: The generator point. A point that everyone knows on which we can perform our operations

n: Order of G. Look here for more information

h: Cofactor. Look here for more information

I might cover the meaning of the last two parameters in an update to this post.

Elliptic-curve Diffie–Hellman (ECDH)

The Diffie-Hellman key exchange is a protocol to agree on a secret key with a different party over a public channel. The key that is agreed upon could then for example be used in a symmetric encryption algorithm. Imagine trying to agree on a secret word with your friend across the room, only being able to shout whatever you want to communicate with them and having the room filled with other people who want to find out that secred word. This is the problem that this method solves.

There is a nice illustration from Wikipedia on the right. Basically, the abstract procedure shown is the following:

Agree upon a publicly known color and define your private color
“Mix” this with your private color
Exchange these mixed colors
Add your own color to the mixture you receive
You should both arrive at the same color

For an interceptor, it is not possible/very difficult to find out either of the secret colors used, and thus they only have the publicly visible, mixed colors.

From a mathematical point of view the “color mixing” should be commutative, so the order of the “mixing” operation does not matter. And it should be difficult to undo this operation.

This is exactly what the scalar point multiplication is! The concrete mathematical steps would be the following:

Agree upon \((p, a, b, G, n, h)\). Create a private key \(d_A\), which is a random integer in the interval \([1, n-1]\)
Create public key \(Q_A\) by performing the scalar point multiplication \(d_A * G\)
Send \(Q_A\) to the other party, receive \(Q_B\)
Calculate \(K = d_A * Q_B\)
\(K\) is the shared secret.

Seeing why this is the case is simple:

\[Q_A = d_A * G \\ Q_B = d_B * G \\ K = d_A * Q_B = d_B * Q_A \\ \\ K = d_A * (d_B * G) = d_B * (d_A * G)\]

Since \(K\) is a point, we can use the \(x\) coordinate of \(K\) as the key. In addition, often times another hash-based function is used on \(x_K\). This will also have to be on, of course. There are known public ECDH protocols, which have clearly defined instructions and parameters so that all the math works out neatly.

This is just one useful application of ECC, there are many more that I might cover in the future.

Wrapping things up

I hope this was a good primer on what ECC is and how some of the underlying processes work. I plan to update this post covering some more topics and applications. If you want to read some more about this topic, I’ll leave some links to articles that I found useful.

Disclaimer

I am not a security/cryptography expert. All of what I have written about ECC is my understanding of this subject and I did so to the best of my knowledge. Still, I cannot guarantee that there are no mistakes and by no means should this be used as a guide to creating your own cryptographic system.