ELLIPTIC CURVE CRYPTOGRAPHY

MATH 195

For a reference on elliptic curves and their cryptographic applications, see: • Alfred J. Menezes, Elliptic curve public key cryptosystems, 1993.

• Joseph H. Silverman and John Tate, Rational points on elliptic curves, 1992. (An undergraduate mathematics text on elliptic curves.)

• J.W.S. Cassels, Lectures on elliptic curves, 1991. (Informal and mathemat-

ical.) An elliptic curve is not an ellipse! An ellipse is a degree 2 equation of the form

x^{2} + ay^{2} = b. (However, given such an ellipse, you could try to compute the arc length of a certain portion of the curve; the integral which arises can be associated to an elliptic curve.)

Elliptic curves

Let k be a field, e.g. k = ℝ, ℂ, ℚ, 𝔽_{q}. An elliptic curve E over k is defined by an equation of the form

E : y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}

with a_{1}, …, a_{6} ∈ k, satisfying a weak condition Δ = Δ(a_{1}, …, a_{6}) ≠ 0. We number the coefficients this way because we give x degree 2, y degree 3, so that y^{2} and x^{3} both have degree 6, and then the “degree” of the coefficient records the difference to make every term have degree 6.

We define

E(k) = {(x, y) ∈ k × k : y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}} ∪ {O},

where O is the ‘point at infinity’. Some explanations are to follow.

Example. If k = ℝ, we take the honest elliptic curve E : y^{2} = x^{3} − x. You can graph this equation by graphing f(x) = x^{3} − x and then plotting the squareroot of this function (omitting when x^{3} − x < 0). Notice that we have two ‘loops’ (over ℝ), but we may also have only one, as in the case E : y^{2} = x^{3} + x.

The condition Δ ≠ 0 is equivalent to every point being a “smooth” point, i.e. there is a uniquely defined tangent line at each point. For example, the curve y^{2} = x^{3} + x^{2} has a “node” at (x, y) = (0, 0), and is not an elliptic curve as Δ = 0. Similarly, the curve y^{2} = x^{3} has a “cusp” at the origin, and again is not allowed. Do not worry about this condition: any homework problem will be given satisfying this condition.

The ‘point at infinity’ is the point ‘connecting’ the second loop in the example. The problem: if you consider the plane, ℝ^{2}, two lines “usually” intersect, but sometimes lines are parallel. This is an unsatisfactory situation, because too many exceptional circumstances can arise when trying to prove theorems. Instead of this affine plane, which we denote 𝔸^{2}(ℝ), we let

This is some of the material covered April 30–May 2, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

ℙ^{2}(ℝ) = 𝔸^{2}(ℝ) ∪ {line at infinity}.

where the line at infinity corresponds to all of the possible slopes. We call this the projective plane. Two lines which are parallel in the affine plane have the same slope and hence ‘intersect’ at one of these additional points in the projective plane. This has other advantages: in most cases, two curves of degree d and e intersect in de points.

Example. We may take k = ℚ: E : y^{2} = x^{3} + 1. Euler (1706-1783) proved that E(ℚ) = {(0, ±1), (−1, 0), (2, ±3)}∪{O}. This is all of the points which are rational numbers!

For E : y^{2} = x^{3} + x, we have E(ℚ) = {O} ∪ {(0, 0)}. A proof: if x = a/b, gcd(a, b) = 1, say b > 0. Then

x^{3} + x = \frac{a(a^{2} + b^{2})a}{b^{3}} = \frac{c^{2}}{d^{2}} = y^{2}

is the square of a rational number, again with gcd(c, d) = 1. Now the numerator and denominator of a(a^{2} + b^{2})/b^{3} are also relatively prime: if p | b^{3} and p | a(a^{2} + b^{2}), then p | b so p ∤ a so p | (a^{2} + b^{2}) so p | a^{2} so p | a, a contradiction. This representation as fractions is unique, so a(a^{2} + b^{2}) = c^{2}, and b^{3} = d^{2}. Therefore b must be a square by the second equation, say b = e^{2}. We have gcd(a, a^{2} + b^{2}) = 1, and their product is a square, so they must each be squares: a = f^{2}, a^{2} + b^{2} = g^{2}. Then e^{4} + f^{4} = g^{2}. Now by Fermat, this has no solutions in strictly positive integers. This does it! Geez!

Elliptic Curves over 𝔽_{q}

Now let k = 𝔽_{q}, a finite field.

Example. Now consider the curve E : y^{2} = x^{3} + x over 𝔽_{3}. Then what is E(𝔽_{3})? We make a table (using Fermat’s little theorem: x^{3} ≡ x (mod 3):

\begin{matrix}x & x^{3} + x = −x & y \\ 0 & 0 & 0 \\ 1 & -1 & - \\ -1 & 1 & ±1 \end{matrix}

Notice that −1 is not a square in 𝔽_{3} = ℤ/3ℤ, so the second line has no corresponding y value. Therefore E(𝔽_{3}) = {O} ∪ {(0, 0), (−1, ±1)}, a group of order 4.

Now consider k = 𝔽_{9} = 𝔽_{3}[X]/(X^{2} + 1). What is E(𝔽_{9})? Notice that we may write X = i, since then i^{2} = X^{2} = −1. (This is purely formal!) We again make a table:

\begin{matrix}x & x^{3} + x & y \\ 0 & 0 & 0 \\ 1 & -1 & ±i \\ -1 & 1 & ±1 \\ i & 0 & 0 \\ i + 1 & (i^{3} + 1^{3}) + (i + 1) = −1 & ±i \\ i − 1 & 1 & ±1 \\ −i & 0 & 0 \\ −i + 1 & −(−1) = 1 & ±1 \\ −i − 1 & −1 & ±i \end{matrix}

This gives

E(𝔽_{9}) = {O, (1, ±i), (−1, ±1), (±i, 0), (±(i − 1), ±1), (±(i + 1), ±i), (0, 0)}

so #E(𝔽_{9}) = 16.

What can we say about #E(𝔽_{q})? There is always the point at infinity, and at most q possibilities for both x and y, so

1 ≤ E(𝔽_{q}) ≤ q^{2} + 1.

(Don’t forget the point at infinity!)

In fact, E(𝔽_{q}) ≤ 2q + 1: for x there are at most q choices, and then y satisfies a polynomial of degree 2, hence there are at most 2 choices for y given x.

There is a more precise statement, due to Hasse:

Theorem (Hasse, first version). If E is an elliptic curve over 𝔽_{q}, then

|#E(𝔽_{q}) − (q + 1)| ≤ 2\sqrt{q}.

This is a probablistic calculation: try out every x ∈ 𝔽_{q}, together with the point at infinity, half of the time there will be a squareroot (and hence two values of y) and half the time not: the average is then q + 1, and the variance (like flipping a coin q times) is 2\sqrt{q}. Phrased in another way, we have

(\sqrt{q} − 1)^{2} = q + 1 − 2\sqrt{q} ≤ #E(𝔽_{q}) ≤ q + 1 + 2\sqrt{q} = (\sqrt{q} + 1)^{2}.

In fact, for almost all values in this range, there exists an elliptic curve with that many points. (There are exceptions, but they are completely under control.)

Note that for the example E : y^{2} = x^{3} + x over 𝔽_{3}, we have #E(𝔽_{9}) = 16 = (\sqrt{9} + 1)^{2}, hence this is the richest elliptic curve over 𝔽_{9}, no other can have more points.

Theorem (Hasse, second version). For every elliptic curve E over 𝔽_{q} there is a complex number π with |π| = \sqrt{q} (π ≠ 3.141592 …!) such that for all n ≥ 1, one has

E(𝔽_{q^{n}}) = (π^{n} − 1)(\overline{π}^{n} − 1) = q^{n} + 1 − (π^{n} + \overline{π}^{n}).

We often write t_{n} = π^{n} + \overline{π}^{n}, this is the “trace of Frobenius”. Note that

|t_{n}| ≤ |π^{n}| + |\overline{π}^{n}| ≤ 2\sqrt{q^{n}}.

Taking n = 1, we obtain the inequality in the first version of the theorem. Returning to our example, we see that for E : y^{2} = x^{3} + x, we had

#E(𝔽_{3}) = 4 = 3 + 1 − (π + \overline{π}),

and π\overline{π} = 3, so we see that π = ±\sqrt{3}i. We check:

#E(𝔽_{9}) = (π^{2} − 1)(\overline{π}^{2} − 1) = (−4)(−4) = 16.

Group Structure on an Elliptic Curve

There is an abelian group law on the set of points of an elliptic curve over a field. Given a field k and an elliptic curve E defined over k, and P, Q ∈ E(k), how do we compute the “addition” P + Q? Property 1: The zero element is the point O at infinity.

Property 2: −O = O, −(x, y) = (x, −y − a_{1}x − a_{3}). This is the ‘other’ solution to the equation

y^{2} + (a_{1}x + a_{3})y − (x^{3} + a_{2}x^{2} + a_{4}x + a_{6}) = 0.

This quadratic has two roots, y_{1}, y_{2}, and y_{1}+y_{2} = −a_{1}x−a_{3}, so y_{2} = −a_{1}x−a_{3}−y_{1}. If a_{1} = a_{3} = 0, then −(x, y) = (x, −y).

Now take the example y^{2} = x^{3} + x over 𝔽_{3}. Let us build a table of the points. We have

+  O  (0, 0) (−1, 1) (−1, −1)
O  O  (0, 0) (−1, 1) (−1, −1)
(0, 0)  (0, 0)
(−1, 1) (−1, 1)
(−1, −1) (−1, −1)

Now we see that (−1, 1) = −(−1, −1) by Property 2, so (−1, 1) + (−1, −1) = O, and therefore (0, 0) + (0, 0) = O. This gives

+  O  (0, 0) (−1, 1) (−1, −1)
O  O  (0, 0) (−1, 1) (−1, −1)
(0, 0)  (0, 0)  O
(−1, 1) (−1, 1)  O
(−1, −1) (−1, −1)  O

Finally, this table must represent a group, so you cannot repeat elements in any row or column. Therefore (−1, 1) + (0, 0) = (−1, −1), since it cannot be any of the other three. This allows us to fill out the table:

\begin{matrix}+ & O & (0, 0) & (−1, 1) & (−1, −1) \\ O & O & (0, 0) & (−1, 1) & (−1, −1) \\ (0, 0) & (0, 0) & O & (−1, −1) & (−1, 1) \\ (−1, 1) & (−1, 1) & (−1, −1) & (0, 0) & O \\ (−1, −1) & (−1, −1) & (−1, 1) & O & (0, 0) \end{matrix}

In the other cases, we have formulae to compute P + Q:

• If P = O, then P + Q = O + Q = Q. Otherwise P = (x_{1}, y_{1}).

• If Q = O, then P + Q = P. Otherwise Q = (x_{2}, y_{2}).

• If x_{1} = x_{2} = x and y_{1} + y_{2} = −a_{1}x − a_{3}, then P = −Q and P + Q = O. Otherwise y_{1} + y_{2} + a_{1}x + a_{3} ≠ 0.

• If P ≠ Q (x_{1} ≠ x_{2}), compute the (unique) line through the points P, Q, y = λx + ν:

λ = \frac{y_{2} − y_{1}}{x_{2} − x_{1}} ;

otherwise, if P = Q, then we compute the tangent line to the curve at the point P:

λ = \frac{3x_{1}^{2} + 2a_{2}x_{1} + a_{4} − a_{1}y_{1}}{2y_{1} + a_{1}x_{1} + a_{3}} .

(Note that we have taken derivatives in a formal sense: use implicit differentiation on the equation for E, and solve for dy/dx.) We always have

ν = y_{1} − λx_{1}.

Now intersect y = λx + ν with the curve

x^{3} + a_{2}x^{2} + a_{4}x + a_{6} − y^{2} − (a_{1}x + a_{3})y = 0.

This intersects a degree 3 equation with a line (degree 1), so we expect 3 · 1 = 3 solutions: two of these are P and Q, so we will obtain another, R. We solve by substitution:

x^{3} + (a_{2} − a_{1}λ − λ^{2})x^{2} + (a_{4} − 2λν − a_{1}ν − a_{3}λ) + (−ν^{2} + a_{6} − a_{3}ν) = 0.

The three roots add up to the negative of the coefficient on x^{2}:

x_{3} = λ^{2} + a_{1}λ − a_{2} − x_{1} − x_{2}.

We let y_{4} = λx_{3} + ν, and then y_{3} = −y_{4} − a_{1}x_{3} − a_{3}. The point P + Q = R = (x_{3}, y_{3}).

Property 3: If a straight line intersects the curve in points P, Q, R, then P +Q+ R = O. This is why P + Q = −R above.

Example. Take y^{2} = x^{3} + 1 over k = ℝ. We add the points P = (−1, 0) and Q = (0, 1). We see the line y = λx + ν that goes through these points is λ = 1, ν = 1. We see then that

x_{3} = 1 − x_{1} − x_{2} = 1 − (−1) = 2

and

y_{3} = −(λx_{3} + ν) = −(2 + 1) = −3.

Therefore (−1, 0) + (0, 1) = (2, −3).

Example. Let us verify an entry in our table above, E : y^{2} = x^{3} + x over 𝔽_{3}, P = (−1, 1), Q = (0, 0). We then compute that λ = −1, ν = 0, and x_{3} = 1 − (−1) + 0 = −1, y_{3} = −((−1)(−1)+0) = −1. So we have verified that (−1, 1)+(0, 0) = (−1, −1).