Elliptic curves over finite fields

Section 4.3 Elliptic curves over finite fields

As we showed in the previous section, given an elliptic curve \(E: Y^2 = X^3 + AX + B\text{,}\) we can form a group \(G = E \cup \{\mathcal O\}\) with the operation of elliptic addition. This object is a fascinating object of study. However, for cryptographic applications, and in particular groups of the size typical to cryptographic appliations, we have to reduce the group to a finite group. In the integer setting, we did this by reducing the integers \(\Z\) to the finite field \(\F_p\text{.}\) In the elliptic setting, we can perform the same maneuver by restricting an elliptic curve to just the points with integer coordinates in some finite field.

Definition 4.3.1.

Let \(p \geq 3\) be a prime. Let \(E\) be the curve \(E:Y^2 = X^3 + AX + B\) with \(4A^3 + 27B^3 \neq 0\text{.}\) The elliptic curve over \(\F_p\), denoted \(E(\F_p)\text{,}\) is the set of points

\begin{equation*} E(\F_p) = \{(x,y): x, y \in \F_p \text{ and } y^2 = x^3 + Ax + B\} \end{equation*}

It is a striking fact that this the points in this set form a group under the previous definition of elliptic addition \(\pmod p\text{.}\) Examine the computational algorithm given in Theorem 4.2.2. Notice that we use nothing more than addition, subtraction, multiplication and division of integers in the calculation of the sum of points \(P, Q\text{.}\) These operations easily translate to the finite field setting, as long as we're careful abouy interpretation. For example, consider the calculation of \(m = \frac{y_2 - y_1}{x_2 - x_1}\) in \(\F_p\text{.}\) Interpreting fractions as multiplication by inverses in \(\F_p\text{,}\) we get

\begin{align*} m \amp= \frac{y_2 - y_1}{x_2 - x_1} \pmod p\\ \amp= (y_2 - y_1)\frac{1}{x_2 - x_1} \pmod p\\ \amp= (y_2 - y_1)(x_2 - x_1)\inv \pmod p. \end{align*}

Theorem 4.3.2. Elliptic curve addition over \(\F_p\).

\(E\)\(\F_p\text{,}\)\(P, Q\)\(E\text{.}\)

If \(P = \mathcal O\text{,}\) then \(P+ Q = Q\text{.}\)
Else, if \(Q = \mathcal O\text{,}\) then \(P + Q = P\text{.}\)
Else, write the coordinates \(P = (x_1, y_1), Q = (x_2, y_2)\text{.}\)
If \(x_1 = x_2\) and \(y_1 = -y_2\) then \(P+ Q = \mathcal O\text{.}\)
Else, compute the slope \(m\text{.}\)
1. If \(P \neq Q\) then
  \begin{equation*} m = (y_2 - y_1)*(x_2 - x_1)\inv \bmod p. \end{equation*}
2. Else
  \begin{equation*} m = (3x_1^2 + A)*(2y_1)\inv \bmod p. \end{equation*}
Then
\begin{gather*} x_3 = m^2 - x_1 - x_2 \pmod p,\\ y_3 = m(x_1 - x_3) - y_1 \pmod p. \end{gather*}
and \(P + Q = (x_3, y_3).\)

As an example, we'll compute the group \(E(\F_7)\) where \(E: Y^2 = X^3 + 3X + 5\text{.}\) Unlike the case where the inputs \(X\) can be elements in \(\R\text{,}\) we need to restrict the \(x\)-coordinates of the group to those elements that produce perfect squares in \(F_7\) in the expression \(x^3 + 3x + 5\) (else there can be no \(y \in \F_7\) that satisfies the curve condition). We start with a table of perfect squares in \(\F_7\text{.}\)

Table 4.3.3. Squares in \(\F_7\)

Notice then that the perfect squares in \(F_7\) are 0, 1, 2, and 4. Each perfect square has two square roots (expected, since we know that in \(\Z\) that \(\sqrt{x^2} = \pm x\)).

To generate \(E(\F_7)\text{,}\) we'll plug in every number in \(\F_7\) into \(X^3 + 3X + 5\) and check for square roots.

Table 4.3.4. Computation of elements in \(E(\F_7)\) for \(E:X^3 + 3X + 5\)

That is, we now have a list of all of the points in \(E(\F_7)\text{:}\)

\begin{equation*} E(\F_7) = \{\mathcal O, (2, 3), (2,4), (4,2), (4,5), (1,1), (1,6)\} \end{equation*}

Once we've produced a list of squares, we can use it to generate an associated elliptic curve.

Note that the method used here is extremely inefficient for large values of \(p\text{,}\) and is intended to illustrate the basic idea of using a computer program to produce mathematical objects.

Theorem 4.3.5.

\(\F_p\)\(\F_p\text{.}\)

We will perform a sample computation and add \(P(4,5) + Q(6,1)\) in \(E(\F_7)\text{.}\) As \(P\) and \(Q\) are distint, we compute

\begin{align*} m \amp = \frac{y_2 - y_1}{x_2 - x_1}\bmod 7 \\ \amp = \frac{1 - 5}{6 - 4}\bmod 7 \\ \amp = (-4)(2)\inv \bmod 7\\ \amp = (-4)(4) \bmod 7 \\ \amp = -16 \bmod 7 \\ \amp = 5 \bmod 7 \end{align*}

Thus,

\begin{equation*} x_3 = m^2 - x_1 - x_2 = 5^2 - 4 - 6 = 1 \bmod 7 \end{equation*}

and

\begin{equation*} y_3 = m(x_1 - x_3) - y_1 = 5(4 - 1) - 5 = 3 \bmod 7 \end{equation*}

and so \((4,5) + (6,1) = (1,3)\) in \(E(\F_7)\text{.}\)

For the purposes of cryptography, we need to know that \(E(\F_p)\) has many points. For any given \(x \in \F_p\text{,}\) one of three things can happen:

\(x^3 + Ax + B\) is a square in \(\F_p\text{,}\) which leads to two points in \(E(\F_p)\text{.}\) This happens about 50% of the time.
\(x^3 + Ax + B = 0\text{.}\) This can happen at most three times, as a cubic polynomial has at most three roots.
\(x^3 + Ax + B\) is not a square, meaning that \(x\) cannot be the \(x\)-coordinate of a point in \(E(\F_p)\text{.}\)

Thus,

\begin{equation*} \# E(\F_p) = 50\% \cdot 2p + 1 \approx p + 1 \end{equation*}

Exercises Exercises

1.

\(E: Y^2 = X^3 + 3X + 5\)\(\F_13\)\(\F_13\)\(E(\F_13)\)

2.

\(p = 10000019 \)