ELLIPTIC CURVE CRYPTOGRAPHY (CONTINUED)

MATH 195

A Review

A summary of all we have seen: An elliptic curve over a field k is given by an equation

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

for a_{i} ∈ k, Δ ≠ 0. We denote E(k) as the set of points (x, y) satisfying this equation together with the point at infinity, O. E(k) is an (additively written) abelian group.

To compute P + Q, for P, Q ∈ E(k):

• If P = O then P + Q = Q;

• If Q = O then P + Q = P;

• Else P = (x_{1}, y_{1}) and Q = (x_{2}, y_{2}); P + Q = O if x_{1} = x_{2} and y_{1} + y_{2} =

−a_{1}x_{1} − a_{3};

• Else let

λ = \begin{cases}\frac{y_{2} − y_{1}}{x_{2} − x_{1}} , & x_{1} ≠ x_{2} \\ \frac{3x_{1}^{2} + 2a_{2}x_{1} + a_{4} − a_{1}y_{1}}{2y_{1} + a_{1}x_{1} + a_{3}} , & x_{1} = x_{2}; \end{cases}

and ν = y_{1} − λx_{1}, x_{3} = λ^{2} + a_{1}λ − a_{2} − x_{1} − x_{2}, y_{4} = λx_{3} + ν, y_{3} =

a_{1}x_{3} − a_{3} − y_{4}, and then P + Q = (x_{3}, y_{3}).

We characterize this group law as follows: To add P ≠ Q, draw the (unique) line y = λx + ν through these two points, the line will intersect the curve E at another (unique) point R, then we take P + Q = −R, its negative.

Doubling

To double P, draw the tangent line to E at P. This must be understood in a formal sense: Let F (x, y) be any polynomial in two variables

F (x, y) = ∑_{i,j≥0}^{<∞} a_{ij}x^{i}y^{j}

(with only finitely many terms). For example, we would take

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

Suppose F (x_{0}, y_{0}) = 0. What is the tangent line to “F = 0” at (x_{0}, y_{0})? We let x = x_{0} + (x − x_{0}) and y = y_{0} + (y − y_{0}) so that we can approximate F by a linear polynomial.

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

Recall the Taylor expansion of a polynomial f(x) at a point x:

f(x) = f(x_{0}) + (x − x_{0})f′(x_{0}) + (x − x_{0})^{2} \frac{f′′(x_{0})}{2} + ⋯ ≈ f(x_{0}) + (x − x_{0})f′(x_{0})

We mimic this in the two variable case, and again throw out any terms of degree ≥ 2: first we write

F (x, y) = ∑_{i,j≥0}^{<∞} a_{ij}(x_{0} + (x − x_{0}))^{i}(y_{0} + (y − y_{0}))^{j};

since by the binomial formula

(x_{0} + (x − x_{0}))^{i} = x_{0}^{i} + ix_{0}^{i−1}(x − x_{0}) + \frac{i(i − 1)}{2}x_{0}^{i−2}(x − x_{0})^{2} + …
≈ x_{0}^{i} + ix_{0}^{i−1}(x − x_{0})

this gives

F (x, y) ≈ ∑_{i,j≥0}^{<∞} a_{ij}(x_{0}^{i} + ix_{0}^{i−1}(x − x_{0}))(y_{0}^{j} + jy_{0}^{j−1}(y − y_{0}))

≈ ∑_{i,j≥0}^{<∞} a_{ij} (x_{0}^{i}y_{0}^{j} + ix_{0}^{i−1}y_{0}^{j}(x − x_{0}) + jx_{0}^{i}y_{0}^{j−1}(y − y_{0}))

= F (x_{0}, y_{0}) + \frac{∂F}{∂x} |_{(x_{0},y_{0})}(x − x_{0}) + \frac{∂F}{∂y} |_{(x_{0},y_{0})}(y − y_{0}).

We also write ∂F/∂x = F_{x} and ∂F/∂y = F_{y}.

Since F (x_{0}, y_{0}) = 0 (the point is on the curve), we call

\frac{∂F}{∂x} |_{(x_{0},y_{0})}(x − x_{0}) + \frac{∂F}{∂y} |_{(x_{0},y_{0})}(y − y_{0})

the tangent line to F at (x_{0}, y_{0}).

Example. Take F = y^{2} − x^{3} − 1, representing the curve E : y^{2} = x^{3} + 1. The point (x_{0}, y_{0}) = (0, −1) is on the curve. We compute F_{x}(x_{0}, y_{0}) = 3x_{0}^{2} = 0, fF_{y}(x_{0}, y_{0}) = 2y_{0} = −2, so the tangent line is 0(x − x_{0}) + (−2)(y − y_{0}) = 0, or simply y = −1. This is a horizontal line!

If F_{x}(x_{0}, y_{0}) = F (x_{0}, y_{0}) = 0, then (x_{0}, y_{0}) is called a singular point of the curve F = 0. Our requirement Δ = 0 provides that the elliptic curve has no singular points.

Note that we can also write it (when F_{y}(x_{0}, y_{0}) ≠ 0):

y = −\frac{F_{x}(x_{0}, y_{0})}{F_{y}(x_{0}, y_{0})}x + \frac{F_{x}(x_{0}, y_{0})x_{0} + F_{y}(x_{0}, y_{0})y_{0}}{F_{y}(x_{0}, y_{0})} .

Now for our equation,

F (x, y) = y^{2} + a_{1}xy + a_{3}y − x^{3} − a_{2}x^{2} − a_{4}x − a_{6},

we have

−\frac{F_{x}(x_{1}, y_{1})}{F_{y}(x_{1}, y_{1})} = λ = \frac{3x_{1}^{2} + 2a_{2}x_{1} + a_{4} − a_{1}y_{1}}{2y_{1} + a_{1}x_{1} + a_{3}} .

This is how one gets this λ: it is the slope of the tangent line at (x_{1}, y_{1}).

Definition of Δ

We want our elliptic curves to be nonsingular. This is the condition that Δ ≠ 0. Define:

b_{2} = a_{1}^{2} + 4a_{2}
b_{4} = 2a_{4} + a_{1}a_{3}
b_{6} = a_{3}^{2} + 4a_{6}
b_{8} = a_{1}^{2}a_{6} + 4a_{2}a_{6} − a_{1}a_{3}a_{4} + a_{2}a_{3}^{2} − a_{4}^{2}

Then

Δ = −b_{2}^{2}b_{8} − 8b_{4}^{3} − 27b_{6}^{2} + 9b_{2}b_{4}b_{6}.

These coefficients have a meaning: if 2 ≠ 0 in k, we multiply our equation F by 4 and complete the square:

(2y + a_{1}x + a_{3})^{2} = 4x^{3} + b_{2}x^{2} + 2b_{4}x + b_{6};

treating the expression in parentheses as a new y, we get a new elliptic curve of a simpler form.

Then we may treat a_{1} = a_{3} = 0, and so we have y^{2} = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}. Then

Δ = 16(a_{2}^{2}a_{4}^{2} − 4a_{4}^{3} − 4a_{2}^{3}a_{6} − 27a_{6}^{2} + 18a_{2}a_{4}a_{6}).

This is none other than the discriminant of the polynomial x^{3} + a_{2}x^{2} + a_{4}x + a_{6}: if the roots of this polynomial are α, β, γ, then this is equal to

16(α − β)^{2}(β − γ)^{2}(γ − α)^{2}.

Other Ways of Defining Elliptic Curves

We have given an elliptic curve (when the characteristic of our field is not 2) as

y^{2} = x^{3} + a_{2}x^{2} + a_{4}x + a_{6},

which can be achieved by a change of variable (completing the square). When the characteristic is not 3, one can “complete the cube”: replace x with (x + a_{2}/3)^{3}, to get a curve of the form

y^{2} = x^{3} + a_{4}x + a_{6}

(with different a_{4} and a_{6}).

On occasion, we may have a curve

uy^{2} + a_{1}xy + a_{3}y = vx^{3} + a_{2}x^{2} + a_{4}x + a_{6}

where u, v ≠ 0. Multiply this equation by u^{3}v^{2} to obtain

u^{4}v^{2}y^{2} + a_{1}u^{3}v^{2}xy + a_{3}u^{3}v^{2}y = u^{3}v^{3}x^{3} + a_{2}u^{3}v^{2}x^{2} + a_{4}u^{3}v^{2}x + a_{6}u^{3}v^{2}

and then replace y by u^{2}vy and x by uvx to get

y^{2} + a_{1}xy + a_{3}uvy = x^{3} + a_{2}ux^{2} + a_{4}u^{2}vx + a_{6}u^{3}v^{2}.

Third, we supplement each term in our curve with z so that the degree of every term is 3:

y^{2}z + a_{1}xyz + a_{3}yz^{2} = x^{3} + a_{2}x^{2}z + a_{4}xz^{2} + a_{6}z^{3}.

It then becomes what we call a homogeneous equation of degree 3. By adding these, we then care only about the ratio (x : y : z). Therefore we write

(x : y : z) = (x′ : y′ : z′)

if and only if there exists a c ∈ k^{∗} such that x′ = cx, y′ = cy, z′ = cz. Note that if you take a solution to the equation and multiply each variable c, each term in the equation is scaled by c^{3}, so it is again zero. “Most of the time”, z ≠ 0, so it has an inverse in the field, and then we may scale by z^{−1} to get

(x : y : z) = (x/z : y/z : 1)

and we get back to the original equation (we substitute z = 1). We exclude the trivial point (x : y : z) = (0 : 0 : 0). We have extended the plane to what is known as the projective plane ℙ^{2}(k) as the set of all such ratios,

ℙ^{2}(k) = ((k × k × k) \ (0, 0, 0))/ ∼

where the equivalence relation

(x, y, z) ∼ (x′, y′, z′)

if and only if there is c ∈ k^{∗} such that x′ = cx, y′ = cy, z′ = cz.

This explains where the point at infinity comes from: we let z = 0, and substituting this into the equation we get x = 0, so the only point, which we denote as O, is O = (0 : y : 0) = (0 : 1 : 0).

To avoid divisions in computing the addition of two points, using projective coordinates we can avoid denominators: (x/d, y/d) = (x/d : y/d : 1) = (x : y : d), for any denominator d.

In fact, we may (in general) take any projective cubic curve C, defined by a homogeneous equation F (x, y, z) = 0 of degree 3, subject to the requirements that F is ‘non-singular’ (so, in particular, F is irreducible), and one is given a point P_{0} ∈ C(k). In this case, P_{0} is the zero element, and if two lines L_{1}, L_{2} intersect the curve C in {P_{1}, Q_{1}, R_{1}} and {P_{2}, Q_{2}, R_{2}}, then

P_{1} + Q_{1} + R_{1} = P_{2} + Q_{2} + R_{2}.

After awhile, you define an elliptic curve as a nonsingular projective one-dimen-sional variety of genus one, together with a point on it. (Think of this as analogous to the abstraction of ℝ^{n} as a vector space over ℝ with a basis.)