76 3. Elliptic Curve Arithmetic

§3.1 provides an introduction to elliptic curves. The group operations of addition and doubling for the points on an elliptic curve are given, along with fundamental structure and other properties. §3.2 presents projective-coordinate representations (and associated point addition and doubling algorithms), of principal interest when field inversion is expensive relative to field multiplication. §3.3 discusses strategies for point multiplication, the operation which dominates the execution time of schemes based on elliptic curves.

The methods in §3.4, §3.5, and §3.6 are related in the sense that they all exploit endomorphisms of the elliptic curve to reduce the cost of doubling in point multiplication. §3.4 discusses the special Koblitz curves, which allow point doubling for curves over F2 to be replaced by inexpensive field squaring operations. §3.5 examines a broader class of elliptic curves which admit endomorphisms that can be used efficiently to reduce the number of doublings in point multiplication. Strategies in §3.6 for elliptic curves over binary fields replace most point doublings by a potentially faster halving operation. §3.7 contains operation count comparisons for selected point multiplication methods. §3.8 concludes with chapter notes and references.

3.1Introduction to elliptic curves

Definition 3.1 An elliptic curve E over a field K is defined by an equation

E : y2 + a1x y + a3 y = x3 + a2 x2 + a4 x + a6

(3.1)

where a1, a2, a3, a4, a6 K and = 0, where is the discriminant of E and is defined as follows:

= −d22d8 − 8d43 − 27d62 + 9d2d4d6
	= 1 +
	=		+
d2		a2		4a2
		2
d4		2a4			a1a3												(3.2)
d6	=	a3 +		+				−				+		−
				4a6
	= a2a 4a a a a a a a2
d															a2
																.
8		1	6			2	6		1	3	4		2	3	4

If L is any extension field of K , then the set of L-rational points on E is

E(L) = {(x, y) L × L : y2 + a1 x y + a3 y − x3 − a2 x2 − a4 x − a6 = 0} {∞}

where ∞ is the point at infinity.

3.1. Introduction to elliptic curves

77

y
2
1
0	2	x
–1
–2

(a) E1 : y2 = x3 − x

y
4
2
0	1	2	x
–2
–4
(b) E2 : y2 = x3 + 41 x + 45

Figure 3.2. Elliptic curves over R.

Remark 3.2 (comments on Definition 3.1)

(i)Equation (3.1) is called a Weierstrass equation.

(ii)We say that E is defined over K because the coefficients a1, a2, a3, a4, a6 of its defining equation are elements of K . We sometimes write E/K to emphasize that E is defined over K , and K is called the underlying field. Note that if E is defined over K , then E is also defined over any extension field of K .

(iii)The condition = 0 ensures that the elliptic curve is “smooth”, that is, there are no points at which the curve has two or more distinct tangent lines.

(iv)The point ∞ is the only point on the line at infinity that satisfies the projective form of the Weierstrass equation (see §3.2).

(v)The L-rational points on E are the points (x, y) that satisfy the equation of the curve and whose coordinates x and y belong to L. The point at infinity is considered an L-rational point for all extension fields L of K .

Example 3.3 (elliptic curves over R) Consider the elliptic curves

E1 : y2 = x3 − x

E2 : y2 = x3 + 1 x + 5 4 4

defined over the field R of real numbers. The points E1(R) \ {∞} and E2(R) \ {∞} are graphed in Figure 3.2.

78 3. Elliptic Curve Arithmetic

3.1.1Simplified Weierstrass equations

Definition 3.4 Two elliptic curves E1 and E2 defined over K and given by the Weierstrass equations

E1 : y2 + a1 x y + a3 y = x3 + a2 x2 + a4 x + a6

E2 : y2 + a1x y + a3 y = x3 + a2 x2 + a4x + a6

are said to be isomorphic over K if there exist u, r, s, t K , u = 0, such that the change

of variables
(x, y) → (u2 x + r, u3 y + u2sx + t)	(3.3)

transforms equation E1 into equation E2. The transformation (3.3) is called an admissible change of variables.

A Weierstrass equation

E : y2 + a1x y + a3 y = x3 + a2 x2 + a4 x + a6

defined over K can be simplified considerably by applying admissible changes of variables. The simplified equations will be used throughout the remainder of this book. We consider separately the cases where the underlying field K has characteristic different from 2 and 3, or has characteristic equal to 2 or 3.

1.If the characteristic of K is not equal to 2 or 3, then the admissible change of variables

(x, y)			x − 3a12 − 12a2		,	y − 3a1 x		a13 + 4a1a2	− 12a3
	→						−	24
			36	216
transforms E to the curve				y2 = x3 + ax + b
									(3.4)

where a, b K . The discriminant of this curve is = −16(4a3 + 27b2).

2.If the characteristic of K is 2, then there are two cases to consider. If a1 = 0, then the admissible change of variables

	→		+ a1			+	a13
(x, y)		a2 x		a3	, a3 y		a12a4 + a32
		1	1

transforms E to the curve

y2 + x y = x3 + ax2 + b

(3.5)

where a, b K . Such a curve is said to be non-supersingular (cf. Definition 3.10) and has discriminant = b. If a1 = 0, then the admissible change of variables

(x, y) → (x + a2, y)

3.1. Introduction to elliptic curves	79
transforms E to the curve
y2 + cy = x3 + ax + b	(3.6)

where a, b, c K . Such a curve is said to be supersingular (cf. Definition 3.10) and has discriminant = c4.

3. If the characteristic of K is 3, then there are two cases to consider. If a12 = −a2,

then the admissible change of variables				+ a3 ,
(x, y) → x +	d4	, y + a1 x + a1	d4
	d2		d2
where d2 = a12 + a2 and d4 = a4 − a1a3, transforms E to the curve
y2 = x3 + ax2 + b				(3.7)

where a, b K . Such a curve is said to be non-supersingular and has discriminant = −a3b. If a12 = −a2, then the admissible change of variables

(x, y) → (x, y + a1x + a3)

transforms E to the curve

y2 = x3 + ax + b

(3.8)

where a, b K . Such a curve is said to be supersingular and has discriminant

= −a3.

3.1.2Group law

Let E be an elliptic curve defined over the field K . There is a chord-and-tangent rule for adding two points in E(K ) to give a third point in E(K ). Together with this addition operation, the set of points E(K ) forms an abelian group with ∞ serving as its identity. It is this group that is used in the construction of elliptic curve cryptographic systems.

The addition rule is best explained geometrically. Let P = (x1, y1) and Q = (x2, y2) be two distinct points on an elliptic curve E. Then the sum R, of P and Q, is defined as follows. First draw a line through P and Q; this line intersects the elliptic curve at a third point. Then R is the reflection of this point about the x-axis. This is depicted in Figure 3.3(a).

The double R, of P, is defined as follows. First draw the tangent line to the elliptic curve at P. This line intersects the elliptic curve at a second point. Then R is the reflection of this point about the x-axis. This is depicted in Figure 3.3(b).

Algebraic formulas for the group law can be derived from the geometric description. These formulas are presented next for elliptic curves E of the simplified Weierstrass form (3.4) in affine coordinates when the characteristic of the underlying field K is not 2 or 3 (e.g., K = F p where p > 3 is a prime), for non-supersingular elliptic curves E of the form (3.5) over K = F2m , and for supersingular elliptic curves E of the form (3.6) over K = F2m .

80 3. Elliptic Curve Arithmetic

y

y

= P = (x1, y1) Q (x2, y2)

x

P = (x1, y1)

R = (x3, y3)

x

R = (x3, y3)

(a) Addition: P + Q = R.

(b) Doubling: P + P = R.

Figure 3.3. Geometric addition and doubling of elliptic curve points.

Group law for E/ K : y2 = x3 + ax + b, char( K) = 2, 3

1.Identity. P + ∞ = ∞ + P = P for all P E(K ).

2.Negatives. If P = (x, y) E(K ), then (x, y) + (x, −y) = ∞. The point (x, −y) is denoted by − P and is called the negative of P; note that − P is indeed a point in E(K ). Also, −∞ = ∞.

3.Point addition. Let P = (x1, y1) E(K ) and Q = (x2, y2) E(K ), where P =

±Q. Then P + Q = (x3, y3), where

x3 =	y2	y1		2		y3 =	y2	y1	(x1
		−		− x1 − x2	and			−		− x3) − y1.
	x2	x1					x2	x1
		−						−

4.Point doubling. Let P = (x1, y1) E(K ), where P = − P. Then 2P = (x3, y3), where

	3x12 + a		2		3x12 + a
x3 =			− 2x1 and y3 =			(x1 − x3) − y1.
	2y1				2y1
Example 3.5 (elliptic curve over the prime field F29)					Let p = 29, a = 4, and b = 20,
and consider the elliptic curve

E : y2 = x3 + 4x + 20

defined over F29. Note that = −16(4a3 + 27b2) = −176896 ≡ 0 (mod 29), so E is indeed an elliptic curve. The points in E(F29) are the following:

				3.1.	Introduction to elliptic curves			81
∞ (2, 6)		(4, 19)	(8, 10)	(13, 23)	(16, 2)	(19, 16)	(27, 2)
(0, 7)	(2, 23)	(5, 7)	(8, 19)	(14, 6)	(16, 27)	(20, 3)	(27, 27)
(0, 22)	(3, 1)	(5, 22)	(10, 4)	(14, 23)	(17, 10)	(20, 26)
(1, 5)	(3, 28)	(6, 12)	(10, 25)	(15, 2)	(17, 19)	(24, 7)
(1, 24)	(4, 10)	(6, 17)	(13, 6)	(15, 27)	(19, 13)	(24, 22)

Examples of elliptic curve addition are (5, 22) + (16, 27) = (13, 6), and 2(5, 22) = (14, 6).

Group law for non-supersingular E/F2m : y2 + x y = x3 + ax2 + b

1.Identity. P + ∞ = ∞ + P = P for all P E(F2m ).

2.Negatives. If P = (x, y) E(F2m ), then (x, y) + (x, x + y) = ∞. The point

(x, x + y) is denoted by − P and is called the negative of P; note that − P is indeed a point in E(F2m ). Also, −∞ = ∞.

3.Point addition. Let P = (x1, y1) E(F2m ) and Q = (x2, y2) E(F2m ), where

P = ±Q. Then P + Q = (x3, y3), where

x3 = λ2 + λ + x1 + x2 + a and y3 = λ(x1 + x3) + x3 + y1 with λ = (y1 + y2)/(x1 + x2).

4.Point doubling. Let P = (x1, y1) E(F2m ), where P = − P. Then 2P = (x3, y3), where

x3 = λ2 + λ + a = x12	+	b		= x12 + λx3 + x3
			and y3
		x2
with λ = x1 + y1/x1.	1

Example 3.6 (non-supersingular elliptic curve over F24 ) Consider the finite field F24 as represented by the reduction polynomial f (z) = z4 + z + 1 (cf. Example 2.2). An element a3z3 + a2z2 + a1 z + a0 F24 is represented by the bit string (a3a2a1a0) of length 4; for example, (0101) represents z2 + 1. Let a = z3, b = z3 + 1, and consider the non-supersingular elliptic curve

E : y2 + x y = x3 + z3x2 + (z3 + 1)

defined over F24 . The points in E(F24 ) are the following:

∞	(0011, 1100)	(1000, 0001)	(1100, 0000)
(0000, 1011)	(0011, 1111)	(1000, 1001)	(1100, 1100)
(0001, 0000)	(0101, 0000)	(1001, 0110)	(1111, 0100)
(0001, 0001)	(0101, 0101)	(1001, 1111)	(1111, 1011)
(0010, 1101)	(0111, 1011)	(1011, 0010)
(0010, 1111)	(0111, 1100)	(1011, 1001)

Examples of elliptic curve addition are (0010, 1111) + (1100, 1100) = (0001, 0001), and 2(0010, 1111) = (1011, 0010).