Elliptic curves over 𝔽2k – Elliptic Curves

8.3.2 Elliptic curves over 𝔽2k

Although not strictly necessary in the context of TLS, for the sake of completeness, we’ll also briefly discuss here how elliptic curves over 𝔽2k can be made a group. Readers who are not interested in these curves may safely skip this section.

Now, the characteristic of 𝔽 is 2, so that our curve equations look different than before. Here, we focus on the non-supersingular case

For these equations it can be shown that Δ = −a6, so for a smooth curve we add the requirement a6≠0.

What do these curves look like? As an example, we take the field 𝔽23, with M(X) = X3 + X + 1 as generating an irreducible polynomial. The element g(X) = X (or g = (010) for short) generates the cyclic group 𝔽23∗, as g1 = (010),g2 = (100),g3 = (011),g4 = (110),g5 = (111),g6 = (101),g7 = (001). Therefore we can label the elements of 𝔽23 as the powers of g, plus the zero element 0 = (000).

Our example curve is given by

As g6≠0, it is smooth.

Let’s look for some points on E. For example, if we plug x = g3 into the equation, we get

as the condition for y. But g2g6 = g8 = g1, and g9 = g2. As g1 + g2 + g6 = (010) + (100) + (101) = (011) = g3, the condition for y becomes

A little trial and error shows that y = g6 provides a solution. Indeed,

So P = (g3,g6) is a point on E, and Q = (g3,g4) is another point on E with the same x coordinate. The set of all points on E (minus the point O at infinity) is shown in Figure 8.7.

Figure 8.7: The curve E : y2 + xy = x3 + g2x2 + g6 over 𝔽23

Again, we can ask how many points there are on an elliptic curve over 𝔽2k, and in this case the following version of Hasse’s Theorem for 𝔽2k applies:

The number N of points of an elliptic curve E over 𝔽2k lies between 2k + 1 − 2 and 2k + 1 + 2.

Now let’s turn to the arithmetic in elliptic curves over 𝔽2k. The general intuition is the same as before, but the explicit addition and point doubling formulae change a little in this case because the reduced Weierstrass form looks different now.

Let P = (x1,y1) and Q = (x2,y2) be points on a smooth elliptic curve over 𝔽2k in reduced Weierstrass form: E : y2 + xy = x3 + a2x2 + a6. Now, let’s add and double these points:

• Point Addition Let R = P + Q and let s = . Then, the coordinates (x3,y3) of R are given by:

If x1 == x2, we set R = P + Q = O.

• Point Doubling Let R = P + P = 2P, where P≠(0,0). Let s = x1 + y1∕x1. Then, the coordinates (x3,y3) of R are given by

If x1 = 0, we set P + P = O.

If P = (α,β) is a point on E, how can we find −P? According to the point addition formula, −P must have the same x coordinate as P. However, we cannot set −P = (α,−β) as for the other fields, because in 𝔽2k, we have −β = β, which would mean −P = P. But we can find −P = (α,γ) by looking at the defining equation.

If P = (α,β) is a point on E, then y = β is a solution of

This means the left-hand side can also be written as

where γ is the unknown y coordinate of −P. Equating coefficients, we see that β + γ = α, or γ = α − β, which is the same as γ = α + β in 𝔽2k.

So for P = (α,β) ∈ E, we have

Again, we can conclude that elliptic curves over 𝔽2k in the form

where ai ∈𝔽2k,a6≠0 form an abelian group with respect to point addition as defined above.