114 3. Elliptic Curve Arithmetic

3.4Koblitz curves

Koblitz curves, also known as anomalous binary curves, are elliptic curves defined over F2. The primary advantage of these curves is that point multiplication algorithms can be devised that do not use any point doublings. The material in this section is closely based on the detailed paper by Solinas [446] which contains proofs of facts and analyses of algorithms presented.

Definition 3.53 Koblitz curves are the following elliptic curves defined over F2:

E0 : y2 + x y = x3 + 1

E1 : y2 + x y = x3 + x2 + 1.

In cryptographic protocols, one uses the group E0(F2m ) or E1(F2m ) of F2m -rational points for some extension field F2m . Let a {0, 1}. For each proper divisor l of m, Ea (F2l ) is a subgroup of Ea (F2m ) and hence #Ea (F2l ) divides #Ea (F2m ). In particular, since #E0(F2) = 4 and #E1(F2) = 2, #E0(F2m ) is a multiple of 4 and #E1(F2m ) is a multiple of 2.

Definition 3.54 A Koblitz curve Ea

#Ea (F2m ) = hn where n is prime and

h =

2

h is called the cofactor.

has almost-prime group order over F2m if

4 if a = 0

2 if a = 1.

We shall assume throughout the remainder of this section that Ea is a Koblitz curve with almost-prime group order #Ea (F2m ). Observe that #Ea (F2m ) can only be almost prime if m is a prime number. The group orders #Ea (F2m ) can be efficiently computed using Theorem 3.11. Table 3.8 lists the extension degrees m [100, 600], and Koblitz curves Ea for which #Ea (F2m ) is almost prime.

3.4.1 The Frobenius map and the ring Z[τ ]

Definition 3.55 Let Ea be a Koblitz	curve. The Frobenius map τ :
Ea (F2m ) is defined by
τ (∞) = ∞,	τ (x, y) = (x2, y2).

The Frobenius map can be efficiently computed since squaring in F2m inexpensive (see §2.3.4). It is known that

(τ 2 + 2) P = µτ ( P) for all P Ea (F2m ),

Ea(F2m ) →

is relatively

3.4. Koblitz curves

115

m Curve Prime factorization of #Ea (F2m )

101	E1	2	· 1267650600228230886142808508011
103	E0	22		· 2535301200456459535862530067069
107	E0	22		· 40564819207303335604363489037809
107	E1	2	· 81129638414606692182851032212511
109	E1	2	· 324518553658426701487448656461467
113	E1	2	· 5192296858534827627896703833467507
131	E0	22		· 680564733841876926932320129493409985129
163	E1	2	· 5846006549323611672814741753598448348329118574063
233	E0	22		· 3450873173395281893717377931138512760570940988862252126\
		22		328087024741343
239	E0			· 2208558830972980411979121875928648149482165613217098488\
		22		87480219215362213
277	E0			· 6070840288205403346623318458823496583257511049878650876\
		22		4884175561891622165064650683
283	E0			· 3885337784451458141838923813647037813284811733793061324\
				295874997529815829704422603873
283	E1	2	· 7770675568902916283677847627294075626569631244830993521\
				422749282851602622232822777663
311	E1	2	· 2085924839766513752338888384931203236916703635071711166\
				739891218584916354726654294825338302183
331	E1	2	· 2187250724783011924372502227117621365353169430893227643\
				447010306711358712586776588594343505255614303
347	E1	2	· 1433436634993794694756763059563804337997853118230175657\
		22		28537420307240763803325774115493723193900257029311
349	E0			· 2866873269987589389513526119127608675995706236460351478\
				84067443354153078762511899035960651549018775044323
359	E1	2	· 5871356456934583069723701491973342568439206372270799668\
		22		11081824609485917244124494882365172478748165648998663
409	E0			· 3305279843951242994759576540163855199142023414821406096\
				4232439502288071128924919105067325845777745801409636659\
		22		0617731358671
571	E0			· 1932268761508629172347675945465993672149463664853217499\
				3286176257257595711447802122681339785227067118347067128\
				0082535146127367497406661731192968242161709250355573368\
				5276673

Table 3.8. Koblitz curves Ea with almost-prime group order #Ea (F2m ) and m [100, 600].

Z[τ ]: if ul−1τ l−1

116	3.	Elliptic Curve Arithmetic
where µ		= −	1)1−a and τ l ( P) denotes the l-fold application of τ	to P. Hence the
		(
Frobenius map can be regarded as a complex number τ satisfying
			τ 2 + 2 = µτ ;	(3.32)

we choose τ = (µ + √−7)/2. Let Z[τ ] denote the ring of polynomials in τ with integer coefficients. It now makes sense to multiply points in Ea (F2m ) by elements of the ring

+ · · · + u1τ + u0 Z[τ ] and P Ea (F2m ), then

(ul−1τ l−1 + · · · + u1τ + u0) P = ul−1τ l−1( P) + · · · + u1τ ( P) + u0 P. (3.33)

The strategy for developing an efficient point multiplication algorithm for Koblitz

curves is to find, for a given integer k, a “nice” expression of the form k						=	l−1 u	i	τ i ,
							i=0
							small and
and then use (3.33) to compute k P. Here, “nice” means that l is relatively
the	nonzero digits u				i are small (e.g., ±1) and sparse.
			2
Since		τ		= µτ − 2, every element α in Z[τ ] can be expressed in canonical form

α = a0 + a1τ where a0, a1 Z.

Definition 3.56 The norm of α = a0 + a1τ Z[τ ] is the (integer) product of α and its complex conjugate. Explicitly,

N(a0 + a1τ ) = a02 + µa0a1 + 2a12.

Theorem 3.57 (properties of the norm function)

(i)N(α) ≥ 0 for all α Z[τ ] with equality if and only if α = 0.

(ii)1 and −1 are the only elements of Z[τ ] having norm 1.

(iii)N(τ ) = 2 and N(τ − 1) = h.

(iv)N(τ m − 1) = #Ea (F2m ) and N((τ m − 1)/(τ − 1)) = n.

(v)The norm function is multiplicative; that is, N(α1α2) = N(α1)N(α2) for all

α1, α2 Z[τ ].

(vi) Z[τ ] is a Euclidean domain with respect to the norm function. That is, for any α, β Z[τ ] with β = 0, there exist κ, ρ Z[τ ] (not necessarily unique) such that

α= κβ + ρ and N(ρ) < N(β).

τ-adic non-adjacent form (TNAF)

It follows from Theorem 3.57 that any positive integer k can be written in the form

k	=		i=0	i	τ i where each u	i {	± }
			l−1 u			0,	1 . Such a τ -adic representation can be obtained
by		repeatedly dividing k by τ ; the digits u						i are the remainders of the division steps. This

procedure is analogous to the derivation of the binary representation of k by repeated division by 2. In order to decrease the number of point additions in (3.33), it is desirable to obtain a τ -adic representation for k that has a small number of nonzero digits. This can be achieved by using the τ -adic NAF, which can be viewed as a τ -adic analogue of the ordinary NAF (Definition 3.28).

3.4. Koblitz curves

117

Definition 3.58

A τ -adic NAF or TNAF of a nonzero element

κ

Z[

τ

] is an expression

l 1

κ

=

i=0

i

τ i where each u

i {

± }

l−1

=

0, and no two consecutive digits u

i

are

−

u

0,

1 , u

nonzero. The length of the TNAF is l.

Theorem 3.59 (properties of TNAFs) Let κ Z[τ ], κ = 0.

(i)κ has a unique TNAF denoted TNAF(κ ).

(ii)If the length l(κ ) of TNAF(κ ) is greater than 30, then

log2(N(κ )) − 0.55 < l(κ ) < log2(N(κ )) + 3.52.

(iii)The average density of nonzero digits among all TNAFs of length l is approximately 1/3.

TNAF(κ ) can be efficiently computed using Algorithm 3.61, which can be viewed as a τ -adic analogue of Algorithm 3.30. The digits of TNAF(κ ) are generated by repeatedly dividing κ by τ , allowing remainders of 0 or ±1. If κ is not divisible by τ , then the remainder r {−1, 1} is chosen so that the quotient (κ − r )/τ is divisible by τ , ensuring that the next TNAF digit is 0. Division of α Z[τ ] by τ and τ 2 is easily accomplished using the following result.

Theorem 3.60 (division by τ and τ 2 in Z[τ ]) Let α = r0 + r1τ Z[τ ].

(i) α is divisible by τ if and only if r0 is even. If r0 is even, then

α/τ = (r1 + µr0/2) − (r0/2)τ.

(ii) α is divisible by τ 2 if and only if r0 ≡ 2r1 (mod 4).

Algorithm 3.61 Computing the TNAF of an element in Z[τ ]

INPUT: κ = r0 + r1τ Z[τ ].

OUTPUT: TNAF(κ ).

1.i ← 0.

2.While r0 = 0 or r1 = 0 do

2.1If r0 is odd then: ui ← 2 − (r0 − 2r1 mod 4), r0 ←r0 − ui ;

2.2Else: ui ← 0.

2.3t ←r0, r0 ←r1 + µr0/2, r1 ← −t/2, i ← i + 1.

3.Return(ui−1, ui−2, . . . , u1, u0).

To compute k P, one can find TNAF(k) using Algorithm 3.61 and then use (3.33). By Theorem 3.59(ii), the length of TNAF(k) is approximately log2(N(k)) = 2 log2 k, which is twice the length of NAF(k). To circumvent the problem of a long TNAF, notice that if γ ≡ k (mod τ m − 1) then k P = γ P for all P Ea (F2m ). This follows

because

(τ m − 1)( P) = τ m ( P) − P = P − P = ∞.

118 3. Elliptic Curve Arithmetic

It can also be shown that if ρ ≡ k (mod δ) where δ = (τ m − 1)/(τ − 1), then k P = ρ P for all points P of order n in Ea (F2m ). The strategy now is to find ρ Z[τ ] of as small norm as possible with ρ ≡ k (mod δ), and then use TNAF(ρ) to compute ρ P. Algorithm 3.62 finds, for any α, β Z[τ ] with β = 0, a quotient κ Z[τ ] and a remainder ρ Z[τ ] with α = κβ + ρ and N(ρ) as small as possible. It uses, as a subroutine, Algorithm 3.63 for finding an element of Z[τ ] that is “close” to a given complex number λ0 + λ1τ with λ0, λ1 Q.

Algorithm 3.62 Division in Z[τ ]

INPUT: α = a0 + a1τ Z[τ ], β = b0 + b1τ Z[τ ] with β = 0.

OUTPUT: κ = q0 + q1τ , ρ = r0 + r1τ Z[τ ] with α = κβ + ρ and N(ρ) ≤ 47 N(β). 1. g0 ← a0b0 + µa0b1 + 2a1b1,

2. g1 ← a1b0 − a0b1.

3. N ← b02 + µb0b1 + 2b12.

4. λ0 ← g0/N, λ1 ← g1/N.

5. Use Algorithm 3.63 to compute (q0, q1) ← Round(λ0, λ1). 6. r0 ← a0 − b0q0 + 2b1q1,

7. r1 ← a1 − b1q0 − b0q1 − µb1q1. 8. κ ← q0 + q1τ ,

9. ρ ←r0 + r1τ . 10. Return(κ, ρ).

Algorithm 3.63 Rounding off in Z[τ ]

INPUT: Rational numbers λ0 and λ1.

OUTPUT: Integers q0, q1 such that q0 + q1τ is close to complex number λ0 + λ1τ .

1.For i from 0 to 1 do

1.1fi ← λi + 12 , ηi ← λi − fi , hi ← 0.

2.η ← 2η0 + µη1.

3.If η ≥ 1 then

3.1If η0 − 3µη1 < −1 then h1 ← µ; else h0 ← 1.

Else

3.2If η0 + 4µη1 ≥ 2 then h1 ← µ.

4.If η < −1 then

4.1If η0 − 3µη1 ≥ 1 then h1 ← −µ; else h0 ← −1.

Else

4.2If η0 + 4µη1 < −2 then h1 ← −µ.

5.q0 ← f0 + h0, q1 ← f1 + h1.

6.Return(q0, q1).

Definition 3.64 Let α, β Z[τ ] with β = 0. Then α mod β is defined to be the output ρ Z[τ ] of Algorithm 3.62.