Elliptic curves

Relevant readings: Aumasson ch. 12, Hoffstein, et al. 6.1–6.3, 6.8, Katz and Lindell 9.3.4

Introducing elliptic curve cryptography

Elliptic curve cryptography (ECC) was first introduced in 1985, which paved the way for stronger security with smaller key sizes. It is more powerful and efficient than traditional public-key algorithms like RSA and (classic) Diffie–Hellman, since a 256-bit key in ECC is stronger than a 4096-bit RSA key. It does not deal with the multiplicative group of integers, but rather, it uses a weird mathematical object called an elliptic curve, thus the math behind ECC is a lot more complicated.

ECC did not gain widespread adoption until the early 2000s; the OpenSSL library only added support for ECC in 2005. Most cryptographic applications that rely on the discrete logarithm problem (DLP) will also work when based on its elliptic curve counterpart, ECDLP.

What is an elliptic curve?

An elliptic curve is the set of solutions to an equation of the form $$y^2 = x^3 + Ax + B,$$ where the constants \(A\) and \(B\) must satisfy \(4A^3 + 27B^2 \ne 0\).¹ We call the above equation the (short) Weierstrass form, and we occasionally refer to elliptic curves of this form as Weierstrass curves. Figure [fig:elliptic-curves] shows two examples of elliptic curves \(y^2 = x^3 - 3x + 3\) and \(y^2 = x^3 - 6x + 5\).

Despite the name, elliptic curves have absolutely nothing to do with ellipses!

The group law for elliptic curves

One important property of elliptic curves is that the points form an abelian group under point addition.

Point addition

An amazing feature of elliptic curves is that there is a natural way to take two points on an elliptic curve and “add” them to produce a third point, and we can derive the addition law geometrically.

Let \(P = (x_1, y_1)\) and \(Q = (x_2, y_2)\) be points on an elliptic curve \(E\). To get the third point, we draw a line \(L\) that passes through \(P\) and \(Q\). This line \(L\) intersects \(E\) at three points, namely \(P\), \(Q\), and one other point \(R\). We take that point \(R\) and reflect it across the \(x\)-axis (i.e., flip the sign of the \(y\)-coordinate) to get a new point \(R^\prime\). Then \(R^\prime\) corresponds to the sum \(P + Q\). See Figure 1 for a visualization.

To get line \(L\), we recall the point-slope formula from high-school algebra: $$y = \lambda \cdot (x-x_1) + y_1,$$ where the slope \(\lambda\) is equal to \((y_2-y_1)/(x_2-x_1)\). In order to find the points where \(E\) and \(L\) intersect, we substitute \(y\) from the point-slope formula to the original Weierstrass equation and then solve for \(x\).

I’m going to handwave some of the details here, but once you solve for \(x\) from the previous step, we eventually arrive at a formula to get the \(x\)-coordinate of the third point, which we can compute as $$x_3 \gets \lambda^2 - x_1 - x_2,$$ and to get the corresponding \(y\)-coordinate, we just use the point-slope formula as before, but we flip the sign of \(y_1\) to get the reflection along the \(x\)-axis: $$y_3 \gets \lambda \cdot (x_3 - x_1) - y_1.$$

Point negation

If \(P\) and \(Q\) have the same \(x\)-coordinates but not necessarily \(P = Q\), then their \(y\)-coordinates have the same absolute value but with opposite signs. In this case, \(Q\) is the inverse (negation) of \(P\), which we denote as \(-P\).

If we add \(P\) and \(-P\) together, we get the special point called the point at infinity, denoted by \(\mathcal{O}\). Despite the name, the point at infinity actually behaves more like a zero than infinity, thus we consider \(\mathcal{O}\) to be the identity element.

Point doubling

What if \(P = Q\)? Since we have the same two points, they have the same \(x\)-coordinates, which would lead to a division by zero when we try to compute for the slope \(\lambda\). Rather than using the secant line as before, we will instead find the tangent line at point \(P\), as shown in Figure 2.

One way to find the tangent line given some equation is to use implicit differentiation (remember this from your calculus class?); here we implicitly differentiate the Weierstrass equation with respect to \(x\): $$\begin{align} y^2 &= x^3 + Ax + B \\ 2y y^\prime &= 3x^2 + A \\ y^\prime &= \frac{3x^2 + A}{2y}.\end{align}$$ Then \(y^\prime\) would correspond to the slope of the tangent line. To find the specific tangent line passing through point \(P\), we just substitute \(x\) and \(y\) with the \(x\)- and \(y\)-coordinates of \(P\): $$\lambda \gets \frac{3x_1^2 + A}{2y_1}.$$

Once we get \(\lambda\), we can simply apply the previous formulas for \(x_3\) and \(y_3\) to get the “third point.”

Scalar multiplication

Recall that for a multiplicative group \(G\), the exponentiation operation is defined as the result of multiplying an element \(x \in G\) with itself \(k\) times: $$x^k = \underbrace{x \cdot x \cdots x}_{\text{$k$ times}}.$$

If \(k = 0\), then \(x^0 = e\), the identity element of \(G\). For an additive group, exponentiation is called scalar multiplication, as it is defined as the result of adding an element \(x \in G\) with itself \(k\) times: $$kx = \underbrace{x + x + \cdots + x}_{\text{$k$ times}}.$$

Since the points of an elliptic curve form a group under point addition, scalar multiplication for a point \(P\) is then: $$kP = \underbrace{P + P + \cdots + P}_{\text{$k$ times}}.$$ If \(k = 0\), then we get \(kP = \mathcal{O}\), the point at infinity.

In similar fashion to exponentiation by repeated squaring, we can do scalar multiplication efficiently through repeated doubling. We then have a similiar-looking algorithm called the double-and-add algorithm:

The running time is \(O(\log k)\), or \(O(n)\) where \(k\) is \(n\) bits long.

Elliptic curves over finite fields

So far we have been dealing with elliptic curves over \(\QQ\). If the underlying field is changed to a finite field, we now get a cloud of points instead of a nice, smooth curve. Figure 3 shows the plot of the elliptic curve over \(\FF_{71}\) defined by \(y^2 = x^3 + 13x + 45\).

Despite this change, the group law still holds!

The elements \(E(\FF_p)\) are called the points on the elliptic curve \(E\) defined by the above equation.

Elliptic curves over finite fields of prime-power order

If we allow the order of the finite field to be a prime power, i.e., \(q = p^k\) for prime \(p\) and integer \(k > 1\), then the equation takes a different form called the generalized Weierstrass form: $$y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6.$$ Note that the short Weierstrass form is a special case, where \(a_1 = a_2 = a_3 = 0\), and \(a_4\) and \(a_6\) correspond to the constants \(A\) and \(B\), respectively.

Computation with elliptic curves in Sage

Suppose \(E\) is an elliptic curve over a finite field \(\FF_q\) in short Weierstrass form: $$y^2 = x^3 + Ax + B,$$ where \(q = p^k\) for prime \(p\) and positive integer \(k\). We can construct \(E\) in Sage using the following syntax:

E = EllipticCurve(GF(q), [A, B])

For example, to define the elliptic curve over \(\FF_7\) defined by \(y^2 = x^3 + x - 1\), we can do: E = EllipticCurve(GF(7), [1, -1]) E

If the underlying finite field has a prime-power order (i.e., of the form \(p^k\) where \(k > 1\)), then we "expose" another variable, say \(a\), to denote elements in \(\FF_{p^k}\): FF_27.<a> = GF(3^3) E2 = EllipticCurve(FF_27, [a^2, a+1]) E2

A point \((x, y)\) is entered using E(x, y), and the point at infinity \(\mathcal{O}\) with E(0). E(2, 4) # point (2, 4) E(0) # point at infinity

Note that Sage represents points on an elliptic curve using projective coordinates of the form \((X : Y : Z)\), as opposed to affine coordinates of the form \((x, y)\). (More details about using affine or projective coordinates to represent points are discussed here.)

We can do basic arithmetic on elliptic curve points (i.e., addition, negation, scalar multiplication) using the typical syntax. P = E(2, 3) Q = E(4, 2) R = E(3, 1) print('-P =', -P) print('5Q =', 5*Q) print('P+R =', P+R) print('R-Q =', R-Q)

To determine the set of points on this curve, we can use the E.points() method. If you only want the number of points (also called the order of the elliptic curve), we can use E.order(). print(f'There are {E.order()} points') E.points()

The elliptic curve discrete logarithm problem

The elliptic curve discrete logarithm problem (ECDLP) is exactly like the “normal” DLP for multiplicative cyclic groups. More concretely, let \(E\) be an elliptic curve over \(\FF_p\) and let \(P\) and \(Q\) be points in \(E(\FF_p)\). Then the ECDLP is the problem of finding an integer \(k\) such that \(Q = kP\).

For some families of curves, the best algorithms known to solve ECDLP are generic group algorithms like Pollard \(\rho\) and baby step–giant step.

Counting points

Counting the number of points on an elliptic curve \(E(\FF_q)\) (also called the order of \(E(\FF_q)\), denoted by \(\Len{E(\FF_q)}\)) efficiently is very tricky. The problem of counting points is of cryptographic relevance, since the hardness of ECDLP depends on the number of points on the underlying elliptic curve. This can help us classify elliptic curves in terms of security levels and thus use the appropriate elliptic curve for the level of security that we actually need.

The absolute maximum number of points of \(E(\FF_q)\) is \(2q+1\) since there could be two points for each \(x \in \FF_q\), plus \(\mathcal{O}\). However, a famous theorem by Hasse establishes a tighter and more useful lower and upper bounds for \(\Len{E(\FF_q)}\):

Rearranging this result, we get $$q+1 - 2\sqrt{q} \le \Len{E(\FF_q)} \le q+1 + 2\sqrt{q},$$ which we can then use to get concrete tight bounds.

Elliptic curve Diffie–Hellman (ECDH)

The elliptic curve version of Diffie–Hellman is identical to that of classical Diffie–Hellman but with different notations:

1. Alice and Bob agree upon an elliptic curve \(E(\FF_p)\) of order \(q\) (where \(q\) is \(n\) bits long) and a base point \(P \in E(\FF_p)\).

2. Alice chooses \(a \getsrandom \ZZ_q\) uniformly at random and sends \(h_A \gets aP\) to Bob.

3. Bob receives \(h_A\), then chooses \(b \getsrandom \ZZ_q\) uniformly at random and sends \(h_B \gets bP\) to Alice.

4. Alice receives \(h_B\), and computes the shared key \(k_A \gets a (bP) = (ab) P\).

5. Bob computes the shared key \(k_B \gets b (aP) = (ba) P = (ab) P\).

The security of ECDH follows from the hardness of ECDLP. Diffie–Hellman protocols that rely on DLP can therefore be adapted to work with elliptic curves and rely on ECDLP as a hardness assumption.

Signing with elliptic curves

The standard algorithm used for signing with elliptic curve cryptography is the elliptic curve digital signature algorithm, or ECDSA for short.

As with all such schemes, the public key is pretty much always generated according to the same formula:

• The private key is a large number \(x\) generated randomly.

• The public key is computed using \(Q \gets xG\), where \(G\) is a group generator (also called the base point) of order \(n\).

To compute an ECDSA signature, you need a hash of the message you’re signing \(H(m)\), your private key \(x\), and a random number \(k\) that is unique per signature. An ECDSA signature is a pair of integers \((r, s)\), computed as follows:

• \(r\) is the \(x\)-coordinate of \(kG\)

• \(s \gets k^{-1} (H(m) + xr) \bmod n\)

To verify an ECDSA signature, a verifier needs to use the same hashed message \(H(m)\), the signer’s public key, and the signature values \(r\) and \(s\). The verifier then:

1. Computes \(u_1 \gets H(m) s^{-1} \bmod n\),

2. Computes \(u_2 \gets r s^{-1} \bmod n\), and

3. Validates that the \(x\)-coordinate of the point \(u_1 G + u_2 Q\) is the same as the value \(r\) of the signature.

The random number \(k\) is sometimes called a nonce because it is a number that must only be used once, and is also sometimes called an ephemeral key because it must remain secret. It is important that \(k\) must never be repeated nor be predictable! Without that, it is trivial to recover the private key.

In general, cryptographic libraries perform the generation of this nonce (the \(k\) value) behind the scenes, but sometimes they don’t and let the caller provide it. This is, of course, a recipe for disaster. For example, in 2010, Sony’s PlayStation 3 was found using ECDSA with repeating nonces (which leaked their private keys).²

ECDSA vs. RSA signatures

RSA’s verification process is often faster than ECDSA’s signature generation because it uses a small public key \(e\). But ECDSA has two major advantages over RSA: shorter signatures and signing speed. Using OpenSSL’s benchmarking tool openssl speed, we can see that signing with ECDSA is about \(225\) times faster than signing with RSA, mainly because ECDSA works with much smaller numbers than RSA does for a similar security level.

brian@thonkpad ~/classes/csci184.03
% openssl speed ecdsap256 rsa4096
Doing 4096 bits private rsa's for 10s: 3228 4096 bits private RSA's in 9.98s
Doing 4096 bits public rsa's for 10s: 180249 4096 bits public RSA's in 9.98s
Doing 256 bits sign ecdsa's for 10s: 417901 256 bits ECDSA signs in 9.95s
Doing 256 bits verify ecdsa's for 10s: 138465 256 bits ECDSA verify in 9.98s
version: 3.0.5
--- snipped for brevity ---
                  sign    verify    sign/s verify/s
rsa 4096 bits 0.003150s 0.000063s    317.4  15900.0
                              sign    verify    sign/s verify/s
 256 bits ecdsa (nistp256)   0.0000s   0.0001s  42627.6  13952.5

The takeaway is this: you should prefer ECDSA to RSA except when signature verification is critical and you don’t care about signing speed, as in a sign-once, verify-many situation (e.g., when digitally signing an app, the developer only needs to sign once, the app’s signature will be verified as many times as the number of devices that would install the app).

Other kinds of elliptic curves

The Weierstrass form is not the only way to define an elliptic curve, and other forms are often used for reasons of efficiency and/or implementation-level security.

Montgomery curves

An elliptic curve in Montgomery form involves equations of the form $$B y^2 = x^3 + Ax^2 + x,$$ where \(B \ne 0\) and \(A \ne \pm 2\). In contrast to the Weierstrass form, not every curve can be expressed in Montgomery form; in particular, the order of any elliptic-curve group written in Montgomery form is a multiple of \(4\).

Twisted Edwards curves

An elliptic curve in twisted Edwards form involves equations of the form $$ax^2 + y^2 = 1 + d x^2 y^2,$$ where \(a, d \ne 0\) and \(a \ne d\). The special case where \(a = 1\) is called the Edwards form. Unlike Weierstrass and Montgomery curves, twisted Edwards curves do not need to define a point at infinity since the point \((0, 1)\) fulfills the role of the identity element.

A nice feature of twisted Edwards curves is that when \(a\) is a square in \(\FF_p\), but \(d\) is not, the addition law is simpler. Given points \(P = (x_1, y_1)\) and \(Q = (x_2, y_2)\), we can compute the sum \(P+Q = (x_3, y_3)\) as: $$(x_3, y_3) = \left( \frac{x_1 y_2 + x_2 y_1}{1 + d x_1 x_2 y_1 y_2}, \frac{y_1 y_2 - a x_1 x_2}{1 - d x_1 x_2 y_1 y_2} \right).$$ No special cases needed!

Other curves

There are lots more curves in use that we don’t have time to discuss, such as Hessian curves, Jacobi curves, and Doche–Icart–Kohel curves. A website called the Explicit-Formulas Database collects all the formulas for doing point addition and scalar multiplication for various forms, almost all of which are heavily optimized for efficient implementation.

Standardized elliptic curves

In practice, we don’t use our own elliptic curves for the same reason we don’t roll our own cryptographic algorithms. To quote the SafeCurves website:³

There are many attacks that break real-world ECC without solving ECDLP. The core problem is that if you implement the standard curves, chances are you’re doing it wrong:

• Your implementation produces incorrect results for some rare curve points.

• Your implementation leaks secret data when the input isn’t a curve point.

• Your implementation leaks secret data through branch timing.

• Your implementation leaks secret data through cache timing.

Rather, we typically use one of these standardized curves that have been optimized for efficiency and security.

NIST curves

NIST released a document called FIPS 186⁴ which introduces the NIST curves under Appendix D “Recommended Elliptic Curves for Federal Government Use.”⁵ Five NIST curves work modulo a prime number, while ten other NIST curves work with binary polynomials that allow for efficient hardware implementation.

The most common of the NIST curves is the P-256 curve. It is an elliptic curve over \(\FF_p\) for the \(256\)-bit prime \(p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\), defined by the equation \(y^2 = x^3 - 3x + B\) where \(B\) is a specified constant. The prime was chosen to have this form because it allows for efficient implementation of arithmetic modulo \(p\). Letting \(A\) in the defining equation to be \(-3\) allows for optimization of elliptic curve operations. NIST also provides prime curves of \(192\) bits, \(224\) bits, \(384\) bits, and \(521\) bits.

Some people grew suspicious about the constants used for the NIST curves because only the NSA, which created the curves, knows how the constants in their equations were derived, thereby insinuating at the possibility of a backdoor planted by the NSA. However, there is insufficient evidence so far that this is the case.

Curve25519

Introduced by Daniel J. Bernstein in 2006, Curve25519 (pronounced as “curve two-fifty-five nineteen”) is an elliptic curve designed for fast performance and uses shorter key lengths than other curves. Unlike the NIST curves, it has no suspicious constants and can use the same unified formula for point addition and doubling.

More formally, Curve25519 is a Montgomery curve over \(\FF_p\) defined by: $$y^2 = x^3 + 486662x^2 + x,$$ where \(p = 2^{255} - 19\), hence the name. It can also be represented in twisted Edwards form, where it is known as Edwards25519.

Even though Curve25519 isn’t standardized by NIST, it is used everywhere from web browsers such as Google Chrome, to protocol implementations such as OpenSSH.

secp256k1

The secp256k1 curve is defined in SEC 2: “Recommended Elliptic Curve Domain Parameters,”⁶ written by the Standards for Efficient Cryptography Group (SECG). It gained a lot of traction after Bitcoin decided to use it instead of the more popular NIST curves, due to the lack of trust in the NIST curves.

It is a type of elliptic curve called a Koblitz curve. A Koblitz curve is just an elliptic curve with some constraints in its parameters that allow implementations to optimize some operations on the curve. The elliptic curve is defined by the equation \(y^2 = x^3 + 7\), where \(x\) and \(y\) are defined over \(\FF_p\), and \(p\) is defined as $$p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1.$$ This defines a group of prime order, like the NIST curves.

Practical considerations

Point compression

A shortcoming of using an elliptic curve \(E(\mathbb{F}_p)\) for cryptography is the fact that it takes two coordinates to specify a point in \(E(\mathbb{F}_p)\). However, the second coordinate actually conveys very little additional information.

Instead of spending another \(\lfloor \log_2 p \rfloor + 1\) bits to represent the \(y\)-coordinate, it is enough to simply send a single bit \(\beta\). For short Weierstrass curves, there are two possible solutions to \(y^2 = x^3 + Ax + B\), which are \(b\) and \(p-b\) for some \(b\). We assume here that we have a way to get \(b\) (i.e., find the square roots modulo \(p\)) efficiently, such as using the Tonelli–Shanks algorithm. Notice that either one of \(b\) and \(p-b\) is less than half of \(p\), while the other one is greater than half of \(p\). Based from this observation, we can use the single bit \(\beta\) to indicate which half the \(y\)-coordinate belongs to.

Affine vs. projective coordinates

So far, we represented points on an elliptic curve using affine coordinates, those in the form of \((x, y)\). Another way is to represent points using projective coordinates, as ratios \((X : Y : Z)\).

Points in projective coordinates are instead represented as an ordered triple of numbers \((X : Y : Z)\) where \(X, Y, Z \in \FF_p\). Converting a point (that’s not \(\mathcal{O}\)) between one form to another is easy: $$\begin{align} (x, y) &\mapsto (xz : yz : z), \\ (X : Y : Z) &\mapsto (X/Z, Y/Z).\end{align}$$ The point at infinity \(\mathcal{O}\) can be represented as \((0 : Y : 0)\) for any nonzero \(Y\), for which these are the only points where \(Z = 0\).

The advantage of using projective coordinates is that we can add points without computing inverses modulo \(p\). Suppose we have two points \(P = (X_1 : Y_1: Z_1)\) and \(Q = (X_2 : Y_2 : Z_2)\) where \(P, Q \ne \mathcal{O}\). Then we can express \(P\) and \(Q\) in affine coordinates as $$P = (X_1/Z_1, Y_1/Z_1) \quad\text{and}\quad Q = (X_2/Z_2, Y_2/Z_2),$$ so we can compute \(S \gets P+Q\) (in projective coordinates) as $$S = P+Q = \left(\lambda^2 - X_1/Z_1 - X_2/Z_2 \;:\; \lambda \cdot (X_1/Z_1 - \lambda^2 + X_1/Z_1 + X_2/Z_2) \;:\; 1 \right),$$ where $$\lambda = (Y_2/Z_2 - Y_1/Z_1)(X_2/Z_2 - X_1/Z_1)^{-1} = (Y_2 Z_1 - Y_1 Z_2)(X_2 Z_1 - X_1 Z_2)^{-1}.$$

We’re not necessarily limited to \(Z_3 = 1\) as we did above. In fact, if we let \(Z_3 = Z_1 Z_2 (X_2 Z_1 - X_1 Z_2)^3\) (i.e., multiply each coordinate by this quantity), we can represent \(S\) as $$S = (vw \;:\; u(v^2 X_1 Z_2 - w) - v^3 Y_1 Z_2 \;:\; Z_1 Z_2 v),$$ where $$\begin{align} u &= Y_2 Z_1 - Y_1 Z_2, \\ v &= X_2 Z_1 - X_1 Z_2, \\ w &= u^2 Z_1 Z_2 - v^3 - 2v^2 X_1 Z.\end{align}$$

A potential downside of using projective coordinates is that a point expressed in projective coordinates may reveal information about how that point was computed, which may in turn leak some secret information.

Invalid curve attack

Elliptic curve Diffie–Hellman can be broken if input points are not validated. This is because computing the sum \(P + Q\) given two points does not involve the coefficient \(B\) in any way, as it only relies on the coordinates of \(P\) and \(Q\) and the coefficient \(A\) (when doubling points).⁷ As a consequence, it is entirely possible to add two points that come from curves with different \(B\) coefficients! This is the main idea behind the invalid curve attack.

To see this attack in action, consider the following scenario involving Alice and Bob using ECDH:

1. Alice and Bob agree upon an elliptic curve and a base point \(P\).

2. Bob sends his public key \(h_B \gets bP\) to Alice.

3. Alice, instead of sending a public key \(h_A \gets aP\) on the agreed upon curve, sends a point on a different curve, either intentionally or accidentally.

   Unfortunately, this new curve is weak and allows Alice to choose a point \(Q\) for which solving ECDLP is easy. She chooses a point of low order, for which there is a relatively small \(k\) such that \(kP = \mathcal{O}\).

   Alice then sends \(h_A \gets aQ\) instead.

4. Bob receives \(h_A\) and computes the shared key \(k_B \gets b h_A = b(aQ)\).

   Bob unknowingly computed the shared key on the weaker curve!

Because \(Q\) was chosen to belong to a small subgroup within the larger group of points, the result \(b h_A\) will also belong to that small subgroup, allowing an attacker to determine the shared secret \(b h_A\) efficiently if they know the order of \(Q\).

An instance of an invalid curve attack is found on certain implementations of the TLS protocol, which uses ECDH to negotiate session keys.