Exploring Elliptic Curve Cryptography

Jun 24, 2021

---

This time we'll be exploring Elliptic Curve Cryptography or ECC. This is a form of public-key or asymmetric cryptography. The math of elliptic curves allows us to create systems with strong cryptographic properties. We'll take an in-depth look at how elliptic curves are used in cryptography.

My previous article served as a quick introduction to the general concept of public-key cryptography. If you're not familiar–or would like a refresher–with the concepts of public/private keys, encryption/decryption, I suggest reading that article first. Also, knowledge of basic algebra and calculus is useful–although not necessary. I'll try my best to explain how all this works.

What Is an Elliptic Curve?

An elliptic curve is a curve that also forms an algebraic group. The graph of an elliptic curve is represented by an equation of the form

$$y^2 = x^3 + Ax + B$$

Where $A$ and $B$ are constants. This equation is called the Weierstrass equation. The graph below shows an elliptic curve over the real numbers $\mathbb{R}$.

Graph of an elliptic curve of the form $y^2 = x^3 + Ax + B$

In ECC, we define elliptic curves over finite fields. This means that there's a finite number of points $(x,y)$ in the group (formed by the elliptic curve defined over the finite field). More precisely, the points in an elliptic curve from an additive abelian group. Abelian groups have interesting properties, which are useful for our cryptographic purposes. Let's first take a look at them.

Abelian Groups

An abelian group–also called a commutative group–consists of a set, together with an operation. In our case, the set consists of all the possible values for $x, y, A$ and $B$ in the Weierstrass equation. Also, we include an especial point–called the point at infinity–in our set. As we'll see later, this point is quite useful. Then the operation for our group is addition–hence the name additive abelian group ¹. We denote it as $(A, +)$, where $A$ is our set, and $+$ is the operation. To be considered as abelian, the group must satisfy the abelian group axioms.

These axioms are the following:

• Closure: this requires that after applying the group's operation to any elements in the set, the result is still inside the set. E.g. if $a$ and $b$ are elements of set $A$, then the result of $a+b$ must also be an element in $A$.

• Associativity: requires that for elements $a, b, c$ in $A$, the equation $(a+b)+c = a+(b+c)$ is true.

• Identity element: the group must have an identity element, let's call it $d$. This element is one such that for all $a$ in $A$, the equations $a+d = d+a = a$ are true. Notice that, in our case (an additive group), this element is equivalent to $0$. This element is the point we introduced as the point at infinity.

• Inverse element: An inverse element $e$ satisfies the equations $e+a = a+e = d$, where $d$ is the identity element from above, i.e. $0$. For our additive group, the inverse element is equivalent to $-a$ for any $a$ in $A$.

• Commutativity: requires that for all $a, b$ in $A$, $a+b = b+a$.

Also, we define addition by the following rule: given three aligned points $P, Q$, and $R$ on the curve, their sum is $P+Q+R=0$. So, if we want to add $P$ and $Q$, we get $P+Q=-R$, where $-R$ is the inverse of $R$ as defined by the axiom above. Later, we'll go into the details of adding two points on an elliptic curve.

Note that we can still perform multiplication in the usual way. If we think of multiplication as repeated addition, we can see that, if $P$ is a point on the elliptic curve and $k$ is a positive integer, then $k \cdot P = P+P+...$ ($P$ added to itself $k$ times).

We can think of the axioms as the rules that dictate what is possible inside the group.

$$\cdots$$

So, we have defined elliptic curves and how they constitute an abelian group.

Now, if we were to work with elliptic curves defined over the reals–such as the one in the graph above–addition operations will quickly yield extremely large numbers. This is because the set $\mathbb{R}$ is infinite, and as $x$ increases, $E$ increases exponentially. Such large numbers will become impossible to handle by a computer. We will constrain our curves to finite fields. Working within a finite field also provides some useful properties for cryptography. In the next few sections, we'll see how elliptic curves are applied to cryptography.

The following section explains how to add two points on an elliptic curve. This is the type of operation we do when computing our public/private keys.

Adding Two Points on an Elliptic Curve

It's easier to visualize elliptic curves defined over the reals. So, I'll use such a curve to show how to add two points. The math is the same for curves defined over finite fields. Let's get started.

We have a curve $E$ defined by $y^2=x^3+Ax+B$ and two points $P_{1}(x_{1}, y_{1})$ and $P_{2}(x_{2}, y_{2})$ on the curve. To obtain $P_{3} = P_{1} + P_{2}$: draw a line $L$ connecting $P_{1}$ and $P_{2}$, this line is defined by $y = mx + b$. Next, extend $L$ until it intersects the curve $E$ on a third point $P_{3} ^{'}$, then reflect $P_{3} ^{'}$ across the $x$-axis (i.e. change the sign of the $y-$coordinate) to obtain $P_{3}$.

It's important to note that this definition of $P_{3} = P_{1} + P_{2}$ is not the same as adding two coordinates. This is shown in the graph below.

Adding two points, $P_{3} = P_{1} + P_{2}$ on the elliptic curve $E$

As you can see, $L$ intersects $E$ at exactly 3 points. To find $P_{3}$, we first need to find the third intersection point $P^{'} _{3}$. In general, if $E$ and $L$ intersect, it means that the $(x,y)$ coordinates at the intersection are the same for both equations. In other words, we need to find the solutions to the equation where $E = L$.

We already defined $E$ as $y^2=x^3+Ax+B$ and $L$ as $y=mx+b$. Substituting $L$ into $E,$ we have:

$$(mx+b)^2 = x^3+Ax+B$$

Next, subtract $(mx+b)^2$ on both sides of the equation:

$$0 = x^3+Ax+B-(mx+b)^2$$

now expand the last term on the right side:

$$0 = x^3+Ax+B-(m^2x^2+2mbx+b^2)$$

and rearrange terms:

$$0 = x^3 - m^2x^2 + (A + 2mb)x + (B + b^2)$$

We now have a cubic polynomial whose roots are the intersection points between $E$ and $L$. In this case, we already know two of the roots, these are the $x$-coordinates of points $P_{1}$ and $P_{2}$. Namely $x_{1}$ and $x_{2}$. A common technique to find the roots of a polynomial is to factor out the equation and then set each term to $0$ to solve for the roots. We can do this to find the third root $x^{'} _{3}$. But, since we already know two of the roots, there's an easier way.

Notice that, for any numbers $a, b, c$ we have:

$$(x-a)(x-b)(x-c) = x^3 - (a+b+c)x^2 + (ab+bc+ac)x - abc$$

here, the terms on the left side of the equation are the three factors of the polynomial on the right side. If we were to find the roots, we set each factor to $0$ and solve for $x$. For example, the first root would be:

$$x-a=0$$ $$x = a$$

we do the same with the other two factors to obtain the three roots of the polynomial: $a,b$, and $c$. Looking at the polynomial on the right side of the equation we can see that, when the coefficient of $x^3$ is $1$, the negative coefficient of $x^2$ is the sum of the roots. We can use this finding to solve for the third root of our polynomial above.

Going back to our cubic polynomial, the coefficient of $x^2$ is $-m^2$, and our roots are $x_{1}, x_{2}$ and $x^{'} _{3}$. So, we can write:

$$-m^2 = -(x_{1} + x_{2} + x_{3} ^{'})$$

solving for $x_{3} ^{'}$ we get:

$$x_{3} ^{'} = m^2-x_{1}-x_{2}$$

This is the $x$-coordinate of our third intersection point, now we just need to find the $y$-coordinate. To do this, we simply use our equation for $L$ as:

$$y_{3} ^{'} = mx_{3} ^{'} + b$$

plugging in the value of $x_{3} ^{'}$:

$$y_{3} ^{'} = m(m^2-x_{1}-x_{2}) + b$$

and rearranging terms:

$$y_{3} ^{'} = m^3 -m(x_{1}+x_{2}) + b$$

We now have the coordinates of the third intersection point $P_{3} ^{'} = (x_{3} ^{'} , y_{3} ^{'})$. Finally, to find $P_{3}$ we project $P_{3} ^{'}$ across the $x$-axis by changing the sign of $y_{3} ^{'}$:

$$y_{3} = -m^3 + m(x_{1}+x_{2}) - b$$

So, the $(x,y)$ coordinates for $P_{3} = P_{1} + P_{2}$ are:

$$\boxed{P_{3} = P_{1} + P_{2} = (m^2-x_{1}-x_{2}, -m^3+m(x_{1}+x_{2})-b)}$$

The terms $m$ and $b$ come from our line equation $L:y=mx+b$, where $m$ is the slope of the line and $b$ is the $y$-intercept (since we know $P_{1}$ and $P_{2}$, these can be easily computed using standard Calculus techniques).

With these formulas, we can compute the $(x,y)$ coordinates of the point resulting from the addition of any two points on an elliptic curve. We just need to know $P_{1}$ and $P_{2}$.

I should say that these results are valid when $P_{1}$ and $P_{2}$ are different points on the curve, i.e. $P_{1} \neq P_{2}$. Three special cases require different calculations to find the intersection point:

• Adding a point $P$ to itself: in this case, we consider the line $L$ to be a tangent line to $P$, then find where $L$ intersects $E$ a second time. The result of the sum is the inverse of the second intersection point.

• When $x_{1} = x_{2}$, but $y_{1} \neq y_{2}$: here $L$ is a vertical line, but $L$ intersects $E$ at the point at infinity $d$ (i.e. $L$ does not intersect $E$ a third time). Reflecting $d$ across the $x$-axis gives us $d$ again. Therefore, in this case $P_{1} + P_{2} = d$, where $d$ is the point at infinity.

• When $P_{2}$ is the point at infinity: this means that $L$ is a vertical line, but in this case $L$ will intersect $E$ a third time at the point at infinity (i.e. if we extend the line further into infinity, we'll still be at infinity). If we call the third intersection point $P_{1} ^{'}$ , when reflected across the $x$-axis, it will take us back to $P_{1}$, then:

$$P_{1} + d = P_{1}$$

where $d$ is the point at infinity. This is consistent with our "identity element" axiom.

$$\cdots$$

Now that we know how to compute the addition of two points on an elliptic curve, let's explore how these concepts apply to cryptography.

Elliptic Curves and Cryptography

Using elliptic curves for cryptography provides similar security to other cryptosystems–such as RSA. However, the advantage of ECC comes from the more efficient use of data. ECC provides similar security while using fewer bits and ultimately less power. This is especially important for mobile devices.

As I mentioned before, in ECC we define our elliptic curve over a finite field. Moreover, the field is of prime order, and we denote it as $\mathbb{F}_{p}$. Where $p$ is a prime number, indicating the number of elements in the field. This means we can construct the field as the integers modulo $p$. For example, the curve ²

$$y^2 = (x^3 + 7)~\text{over}~(\mathbb{F}_p)$$

can be expressed as:

$$y^2 \mod p = (x^3 + 7) \mod p$$

where $mod$ is the modulo operation.

Another aspect of ECC is that its security depends on the difficulty of solving the discrete logarithm problem. Other cryptosystems may rely on prime factorization for example. When $p$ is large, the existing algorithms to solve the discrete log problem are not efficient.

The Discrete Logarithm Problem

The discrete logarithm problem is defined as follows. Suppose $p$ is a prime number and $a,b$ positive integers. Then we have another integer $k$ so that:

$$a^k = b \mod p$$

The goal of the discrete logarithm problem is to find $k$. As you can see, to find $k$, we need to take the $log_{a}$ (with base $a$) on both sides of the equation. For a group comprised by an elliptic curve over the reals, this would be a rather (computationally) easy calculation. However, since our curve is defined over a finite field of prime order, solving the discrete log is hard when $p$–the field's order–is large.

Different cryptosystems use slightly different approaches, but here's an example of how this applies in practice. Let's suppose we're generating a public/private key pair, and we have defined an elliptic curve $E$ over a finite field, denoted as $E(\mathbb{F}_p)$. First, we need to select a fixed point $G$ on the curve. This point is referred to as the generator point. Then we select a private key $k$–usually a randomly chosen number. Finally, we generate a public key $K$ by computing:

$$K = kG$$

$K$, $G$, and $E(\mathbb{F}_p)$ are public information. Now, we're supposed to keep $k$–the private key–secured. If an attacker wants to obtain this key, they need to be able to solve discrete logs in $E(\mathbb{F}_p)$. An easy way to see it is if we let the group's operation be multiplication (instead of addition). In this case $k \cdot G = G\cdot G\cdot G$... ($G$ multiplied by itself $k$ times). This is equivalent to calculating $G^k$, and therefore to find $k$ we need to compute the discrete log.

Cryptosystems use the discrete log problem to make it hard to guess our secret keys. There are several methods for attacking discrete logs. One example is Pollard's rho algorithm, which works for general groups. The runtime for this algorithm is $O(\sqrt{n})$, where $n$ is the group's order–in our case $p$. It's important to choose the appropriate curve and other mathematical constants–such as the group's order–to have a strong cryptosystem.

$$\cdots$$

Once we have defined an elliptic curve, we can use it as part of our cryptosystem to derive our public/private key pairs. In practice, there's a set of curves defined in standards established by the NIST (National Institute of Standards and Technology). For example, Bitcoin uses an elliptic curve defined in a standard called secp256k1. Next, let's take a look at some of the cryptosystems using elliptic curves.

Elliptic Curve Cryptosystems

In this section, I'll briefly describe two examples of cryptosystems using ECC. I won't go into much detail, but there's plenty of resources available on the internet to learn how they work.

Recall that we can use public-key cryptography in two ways: to encrypt information, or to digitally "sign" information. In the case of data encryption, public-key cryptosystems are used to generate the key pairs, while the encryption is done with a symmetric encryption protocol–where there's a shared key. The reason is that public-key encryption–although more secure–is slower than symmetric systems.

The Elliptic Curve Diffie-Hellman or ECDH key exchange protocol is a scheme used in data encryption. ECDH is used to establish a shared secret–using the public/private key pairs–between two parties. The key pairs are obtained using an agreed-upon elliptic curve. Once this is in place, the information can be encrypted and transmitted. This information can only be decrypted using the shared secret key.

An example for digital signatures is the Elliptic Curve Digital Signature Algorithm or ECDSA. This is an elliptic curve version of the Digital Signature Algorithm (DSA). Here, the key pair is, again, derived from an elliptic curve over a finite field. The private key is used to generate a signature, which is sent along with the message and public key. In this case, the message may or may not be encrypted ³. The receiver can then use the public key to verify that the signature is valid, thus confirming that the message came from the sender (who owns the private key).

These are only two examples of elliptic curve cryptosystems. But, there's more that work similarly. ECC is used in applications such as web browsers, messaging apps, and almost every cryptocurrency and blockchain project out there.

$$\cdots$$

Conclusions

Public-key cryptosystems based on elliptic curves improve over other asymmetric schemes such as RSA. They require less memory to achieve the same level of security. I went over some of the math behind elliptic curves and their use in cryptography. I think knowing the theory behind elliptic curves is useful.

More advanced cryptographic systems use elliptic curve math under the hood. For example, the emerging zero-knowledge proofs and zk-SNARKS. These are powerful cryptographic constructs that allow us to prove the knowledge of certain information without revealing that information. They are relatively new, but they seem to be gaining a lot of attention. Knowing about elliptic curves can help us understand how they work and keep exploring the fascinating world of cryptography.

Notes