Generation Methods of Elliptic Curves
byHarald Baier and Johannes Buchmann

August 27, 2002

An evaluation report for the
Information-technology Promotion Agency, Japan

Contents
1 Introduction1

1.1

Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22 Elliptic Curves in Cryptography
2.1
2.2

Elliptic Curve Groups over Fp . . . . . . . . . . . . . . . . . . . . . . . . . . .
Elliptic Curve Groups over F2n . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Generation Methods

3
3
5
7

3.1

Primality Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.2

Finding Suitable Elliptic Curve Groups over Fp . . . . . . . . . . . . . . . . .

8

3.2.1

Random Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2.2

Complex Multiplication Approach . . . . . . . . . . . . . . . . . . . .

10

3.2.3

Finding a Point of Large Prime Order . . . . . . . . . . . . . . . . . .

11

3.2.4

Comparison of Both Generation Methods . . . . . . . . . . . . . . . .

12

Finding Suitable Elliptic Curve Groups over F2n . . . . . . . . . . . . . . . .

13

3.3.1

Random Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

3.3.2

Complex Multiplication Approach . . . . . . . . . . . . . . . . . . . .

15

3.3.3

Koblitz Approach. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.3.4

Finding a Point of Large Prime Order . . . . . . . . . . . . . . . . . .

16

3.3.5

Comparison of the Three Generation Methods . . . . . . . . . . . . .

17

3.3

4 Implementation Issues
4.1

4.2

19

Arithmetic in Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

4.1.1

Arithmetic in Finite Prime Fields . . . . . . . . . . . . . . . . . . . . .

19

4.1.2

Arithmetic in Finite Fields of Characteristic 2 . . . . . . . . . . . . . .

20Polynomial Basis Representation . . . . . . . . . . . . . . . . . . . . .

20

Normal Basis Representation . . . . . . . . . . . . . . . . . . . . . . .

21

Recommended Fields of Characteristic 2 . . . . . . . . . . . . . . . . .

21

Scalar Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

ii

Contents
4.2.1

Point Addition for Elliptic Curves over Fp . . . . . . . . . . . . . . . .

22

4.2.2

Point Addition for Elliptic Curves over F2n . . . . . . . . . . . . . . .

23

4.2.3

Scalar Multiplication on Koblitz Curves . . . . . . . . . . . . . . . . .

24

4.2.4

Scalar Multiplication on a General Elliptic Curve . . . . . . . . . . . .

24

4.2.5

Scalar Multiplication on Special Elliptic Curves . . . . . . . . . . . . .

25

4.3

Point Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

4.4

Implementation on Smart Cards . . . . . . . . . . . . . . . . . . . . . . . . .

27

Bibliography

27

Index

32

Chapter 1

Introduction
1.1

Preface

Let q be a prime power, and let E be an elliptic curve over the field Fq of q elements. As
usual we associate to E a finite set called the set of rational points of E over Fq . We denote
this set by E(Fq ). We will explain these terms in Chapter 2. Once we know that E(Fq )actually is a finite Abelian group, we may define the discrete logarithm problem in E(Fq ) as
usual. However, since the use of elliptic curves in cryptography, various algorithms to solve
the discrete logarithm problem in the group of rational points of an elliptic curve have beenfound. Hence, in order to keep the discrete logarithm problem intractable, we have to choose
the elliptic curve diligently.
As of today the security of an elliptic curve cryptosystem is determined by the cardinalityof E(Fq ). Thus in order to decide whether a group of rational points is suitable for use
in cryptography, we have to know its group order. It turns out that in general this is aburdensome and nontrivial task. The following methods are known to find a suitable group.
The first approach, mostly referred to as the random approach, first chooses a random curve
E. Using point counting algorithms, the group order of E(Fq ) is determined. Once thecardinality is known, we can decide whether the group is suitable for use in cryptography ornot. If it turns out that the curve does not yield a secure cryptosystem, a new elliptic curveis chosen.
The second method makes use of the theory of complex multiplication. It is therefore referred
to as the complex multiplication method. We abbreviate this method by CM-method. Its
proceeding is quite different from the random approach. In the complex multiplication method
one first searches for candidates of a suitable group cardinality. This can be done without
knowing the corresponding elliptic curves. Once a suitable cardinality is found, the elliptic
curve is determined using complex multiplication.
Finally, let q = pn be a prime power with n > 1. In addition, let m be a positive divisor ofn, m 6= n. If E is defined over Fpm and if we know the group order of E(Fpm ), a theorem ofWeil may be used to get |E(Fq )|. The use of Weil’s theorem was first proposed by Koblitz([Kob92]). Thus we refer to this method as the Koblitz approach. We remark that in [X9.62]
this approach is called the Weil method.

2

Introduction

In this document we report on these methods to find a suitable group. We give both theoreticaland practical run times of all methods, and we compare the advantages and disadvantages of
either algorithm.
This report is organized as follows: The subsequent section lists the notation we use in thisdocument. In Chapter 2 we introduce the security conditions we have to impose on an elliptic
curve group. Next, in Chapter 3 we discuss in detail all known algorithms to find such agroup. Finally, Chapter 4 deals with implementation issues.

1.2

NotationIn this evaluation report we use a notation similar to [P1363].
pq

a rational prime
a power of p, i.e. q = pn
Fq
the finite field of q elements
E
an elliptic curve over a finite field(a, b)
the parameters of an elliptic curveE(Fq )
the group of rational points of E over the field Fq|E(Fq )| the group order of E(Fq )O
the point at infinity
Ga base point of an elliptic curve cryptosystemrthe cryptographic prime factorkthe cofactor
In the framework of the CM-method we make use of the following symbols.
∆
an imaginary quadratic discriminantO∆the imaginary quadratic order of discriminant ∆h(∆) the class number of discriminant ∆hc (∆) the crossover class number
As usual we describe the complexity of an algorithm in terms of its bit-complexity. The
bit-complexity estimates the number of basic operations a processor has to perform when
executing an algorithm. Throughout this document we estimate the bit-complexity of analgorithm as its ’ordinary’ bit-complexity, that is we assume that a schoolbook implementationof the algorithm is used. From a practical point of view this is more reasonable than using
theoretical bit-complexities of optimized algorithms. Often the optimized variants are not
implemented, as their complexity is only asymptotically superior to the ordinary algorithm.
Furthermore by log we denote the natural logarithm, that is the logarithm to the base e. In
addition, the logarithm to the base 2 is written as log2 .

Chapter 2

Elliptic Curves in Cryptography
In this chapter we review the security conditions we have to impose on an elliptic curve groupfor use in cryptography. As usual we distinguish two different cases. First, in Section 2.1 welist the requirements if q = p is a large prime. Second, in Section 2.2 we turn to elliptic curves
defined over a finite field of characteristic 2.

2.1

Elliptic Curve Groups over Fp

Let q = p be a prime, p ≥ 5. An elliptic curve over Fp is a pair E = (a, b) ∈ F2p with
4a3 + 27b2 6= 0. A point on E is a solution (x, y) ∈ F2p of y 2 = x3 + ax + b or the point at
infinity O obtained by considering the projective closure of this equation. The set of points
on E over Fp is denoted by E(Fp ). It carries a group structure with the point at infinity
acting as the identity element. It is called the group of rational points of E over Fp .
In the scope of this report we call the elliptic curve group E(Fp ) cryptographically strong if
it satisfies the following conditions which make the cryptosystems, in which E(Fp ) is used,secure and efficient.
We first consider security. If E(Fp ) is used in a cryptosystem, the security of this cryptosystem
is based on the intractability of the discrete logarithm problem in E(Fp ). Several discrete
logarithm algorithms are known. To make their application impossible, we require that E(Fp )satisfies the following conditions.
1. We have |E(Fp )| = k · r with a prime r > 2160 and a positive integer k.
2. The primes r and p are different.
3. The order of p in the multiplicative group F×r of Fr is at least B, where B ≥ 20.
The first condition excludes the application of generic discrete logarithm algorithms. Theirrunning time is roughly the square root of the largest prime factor of the group order (see forexample [vOW99]). We make use of the bound 2160 as proposed in [X9.62], as this bound isconsensus in the cryptographic community. The second condition makes the anomalous curve
attack impossible (see [SA98], [Sem98], [Sma99]).

4

Elliptic Curves in Cryptography

The last condition excludes the attacks of Menezes, Okamoto, Vanstone ([MOV91]), and theattack of Frey, Rück ([FR94]). Both methods reduce the discrete logarithm problem in E(Fp )to the discrete logarithm problem in a finite extension field of Fp . The degree of this extension
over Fp is at least the order of p in F×
r , where in general equality holds, as shown in [BK98].
The third condition is based on the assumption that the discrete logarithm problem in a finite
field of order of magnitude pB is intractable. The bound B = 20 is explicitely given in [SEC1].
In [X9.62] the standard requires B ≥ 21 (Annex A.1.1 of [X9.62]). Furthermore, we pointout that the German Information Security Agency [GIS01] requires B ≥ 104 . However, if thefirst condition holds and if B ≥ 20, an attacker will have to compute a discrete logarithm ina finite field of order of magnitude at least 23200 . This is currently not possible, and following
Lenstra/Verheul ([LV01]) will stay impossible for at least the next 40 years. We therefore
consider B ≥ 20 to be a good choice.
Let us now consider efficiency. Suppose that an elliptic curve E over a prime field Fp satisfies
the security conditions. If this curve is used in a cryptosystem, the efficiency of this systemdepends on the efficiency of the arithmetic in Fp . So p should be as small as possible. It
follows from a theorem of Hasse thatqq
2
( |E(Fp )| − 1) ≤ p ≤ ( |E(Fp )| + 1)2 .
(2.1)

Hence, we try to make |E(Fp )| as small as possible. Now the first security condition implies|E(Fp )| = k · r(2.2)

with a prime number r > 2160 and a positive integer k, the so called cofactor. The securityof the cryptosystem, in which E(Fp ) is used, is based on the intractability of the discrete
logarithm problem in the subgroup of order r in E(Fp ). This security is independent of k.
Therefore, k can be as small as possible. An explicit bound of k is given in [SEC1]. We
therefore refine the first security condition as follows:
4. We have |E(Fp )| = k · r with a prime number r > 2160 and a positive integer k ≤ 4.
We remark that this requirement is stricter than the notion of trialdivision with a bound 255,
as proposed in [X9.62], Annex A.3.2 . However, our practical results give evidence that curves
with k ≤ 4 are found in reasonable time.
We explain an additional security condition required by the German Information Security
Agency GISA ([GIS01]). The third condition implies that the endomorphism ring End(E(Fp ))of the elliptic curve over the algebraic closure of Fp is an imaginary quadratic order. The
GISA requires the following.
5. The class number of the maximal order which contains End(E(Fp )) is at least 200.
The reason for this condition is that among all curves over a prime field only very few haveendomorphism rings with small class numbers. So those curves may be subject to specificattacks. However, no such attacks are known. As this condition is not considered in any
international cryptographic standard, we do not take it into account.
To summarize we say that an elliptic curve group E(Fp ) is cryptographically strong if itsatisfies the conditions from Table 2.1. They are labelled (O1) - (O3), where ’O’ stands forodd.

2.2 Elliptic Curve Groups over F2n
(O1)
(O2)
(O3)

5

|E(Fp )| = k · r, r > 2160 prime, k ≤ 4
p 6= rps 6≡ 1 mod r, 1 ≤ s < 20

Table 2.1: Security conditions for an elliptic curve group E(Fp )2.2

Elliptic Curve Groups over F2n

In this section let q = 2n . An elliptic curve over F2n is a pair E = (a, b) ∈ F22n with b 6= 0.
A point on E is a solution (x, y) ∈ F22n of y 2 + xy = x3 + ax2 + b or the point at infinity
O. Again the set of points on E over F2n is denoted by E(F2n ) and again it carries a groupstructure with the point at infinity acting as the identity element.
The security and efficiency conditions on E(F2n ) are similar to the requirements of Section
2.1. We summarize them in Table 2.2. They are labelled (E1) - (E3), where ’E’ stands for
even.
(E1)
(E2)
(E3)

|E(F2n )| = k · r, r > 2160 prime, k ≤ 4
2ns 6≡ 1 mod r, 1 ≤ s < 20
n is prime

Table 2.2: Security conditions for an elliptic curve group E(F2n )We remark that the anomalous curve condition is r 6= 2 in this case. As (E1) requires r to bea large prime, the anomalous curve condition follows from (E1). In addition we point out thatthe primality of n is not required by any standard. However, recent results in the frameworkof the Weil descent make the condition (E3) necessary (see [GHS02a], [GHS02b]).
Finally, we remark that in contrast to the GISA we do not require that E may not be definedover F2 . Hence we allow the use of the two elliptic curves (0, 1) and (1, 1) as proposed by
Koblitz ([Kob92]).

6

Elliptic Curves in CryptographyChapter 3

Generation Methods
In this chapter we discuss various methods to find a cryptographically strong elliptic curvegroup. The task we have to solve is as follows: Let r0 and k0 be positive integers withr0 ≥ 2160 and k0 ≤ 4. In addition to the requirements of Chapter 2 we have to find an elliptic
curve group whose order factors as k · r with r ≥ r0 and k ≤ k0 . Thus the integers r0 and k0
serve as bounds for r and k, respectively, to define an individual security and efficiency level.
Before actually investigating the generation methods we turn to the important question ofprimality testing.

3.1

Primality Tests

Testing integers for primality is an important task in public key cryptography. However, as
primality proving is rather slow probabilistic primality tests are used in practice. The term
’probabilistic’ means that the primality test may output a wrong answer.
Throughout the different cryptographic standards the Miller-Rabin test is proposed for use
in practice (e.g. [X9.62], Annex A.2.1). Let i be an integer and T a positive integer. If theMiller-Rabin test says that i is composite, the answer is true. However, if the Miller-Rabin
test claims i to be prime, the answer is wrong with a probability at most 1/4. Thus in orderto decrease the error probability, the Miller-Rabin test is performed independently T times
for the input i. A common number of independent tests is T = 50, as proposed in [X9.62],
Annex A.2.1 . Then the probability of accepting a composite i as prime number is at most2−100 . This error bound is sufficient for practical applications. We write isPrime(i, 50) to
denote the Miller-Rabin test. isPrime(i, 50) returns false, if i is shown to be composite
within at most 50 tests. It returns true otherwise.
Finally, the bit-complexity of isPrime(i, 50) is O(log3 i) ([Coh95]). We remark that very
recently a deterministic polynomial time primality test was published ([AKS02]). However,its applicability in practice is not yet clear.

8

3.2

Generation Methods

Finding Suitable Elliptic Curve Groups over Fp

In this section we present two methods to find a cryptographically strong elliptic curve groupover a finite prime field. First, the random approach is discussed in Section 3.2.1. Second,
we present the CM-method in Section 3.2.2. We remark that the Koblitz approach is notapplicable in the case of a finite prime field. In Section 3.2.3 we show how to find a point oforder r. Finally, in Section 3.2.4 we compare the random approach to the CM-method.
Before turning to the algorithms we describe the algorithm isStrongP(r0 , k0 , p, N ). It requires
positive integers r0 and k0 as input with r0 ≥ 2160 and k0 ≤ 4, respectively. In addition thealgorithm gets a prime p and a positive integer N . The algorithm implements the requirements(O1) - (O3) of Table 2.1, where we substitute 2160 by r0 and 4 by k0 in (O1). It returns aprime r if N = k · r is the order of a cryptographically strong elliptic curve group over Fp
with r ≥ r0 and k ≤ k0 . Otherwise isStrongP returns 0.

Algorithm 3.1: isStrongP(r0 , k0 , p, N )Input: Positive integers r0 and k0 with r0 ≥ 2160 and k0 ≤ 4.
A prime p and the order N of a group of rational points of an elliptic curve over Fp .
Output: A prime r if N = k · r is the order of a cryptographically strong elliptic curve group over Fp
with r ≥ r0 and k ≤ k0 , and 0 otherwise.
1: //check if N is in the Hasse interval√
2: if |N − (p + 1)| > 2 p then3:
return (0);4: r ← 0; k ← 0; //initialize both r and k with 0
5: //check condition (O1) by trialdivision
6: for i ← 1; i ≤ k0 ; i ← i + 1 do
7:
if i | N AND isPrime(N/i, 50) = true AND N/i ≥ r0 then8:r ← N/i; k ← i; break;
9: if r = 0 then10:
return (0);11: //check condition (O2)
12: if p = r then13:
return (0);14: //check condition (O3)
15: pr ← 1 mod r;
16: for i ← 1; i ≤ 19; i ← i + 1 do
17:
pr ← p · pr mod r;
18:
if pr = 1 then19:
return (0);20: return (r);√We estimate the bit-complexity of isStrongP(r0 , k0 , p, N ). First, the computation of p inline 2 and the trialdivision in line 7 are negligible. As we have N = O(p), the Miller-Rabin
test in line 7 is of bit-complexity O(log3 p). Finally, the multiplication and reduction modulo
r in line 17 are of bit-complexity at most O(log3 p), too. Thus in all isStrongP(r0 , k0 , p, N )is of bit-complexity O(log3 p).

3.2 Finding Suitable Elliptic Curve Groups over Fp

3.2.1

9

Random Approach

We present an algorithm to randomly generate a cryptographically strong elliptic curve group
E(Fp ). We denote this algorithm by randomApproachP(r0 , k0 ). Its input are positive integers
r0 and k0 with r0 ≥ 2160 and k0 ≤ 4. The algorithm outputs a prime p, positive integers r andk, and an elliptic curve E such that |E(Fp )| = k · r and such that isStrongP(r0 , k0 , p, k · r)
returns r.
The first task is to find a prime p. As of today no attacks on elliptic curve cryptosystems are
known which exploit special properties of some field Fp . Thus the choice of the prime p is
not critical. However, we have to consider the boundary conditions r ≥ r0 and k ≤ k0 . We
write b for the bitlength of k0 · r0 . We propose to choose p such that k0 · r0 ≤ p ≤ 2b . The
method getPrime(r0 , k0 ) returns such a prime. The user may choose his own implementationof getPrime. For instance, one may want to use primes in the interval [k0 · r0 , 2b ] which are
generated by some pseudorandom number generator as described in FIPS 186 ([FIPS186]).
Once p is known the further proceeding is as follows: Choose parameters a and b with
4a3 + 27b2 6≡ 0 mod p, determine the order of the group of rational points of the curve(a, b) over Fp , and finally check if this group is cryptographically strong.
We first explain how to choose a and b. It is common to choose parameters verifiably at
random. This method is e.g. explained in [X9.62], Annex A.3.3.2 . The basic idea is to makeuse of the one-way property of a cryptographic hash function. By h we denote such a hashfunction and by l the length in bits of the output of h. We assume l ≥ 160 (e.g. SHA-1 or
RIPEMD-160). In order to generate a curve verifiably at random one first chooses a bitstringof length at least l. We write SEED for this string. Once SEED is known the value h(SEED) isused to compute a and b deterministically by a publicly known algorithm. Thus if we provide
SEED, the hash function h, and the deterministic algorithm to compute (a, b) from h(SEED),
any entity may verify that a and b actually are computed using SEED. The one-way propertyof h guarantees that the parameters actually are chosen at random. In this report we write
getParametersP(p, SEED) for any algorithm which returns an elliptic curve E defined overFp verifiably at random.
If the curve E = (a, b) is chosen we have to determine the group order of E(Fp ). Currently,
the best known algorithm for this task is the SEA-algorithm. The SEA-algorithm is due to
Schoof, Elkies and Atkin (see for instance [Mül95], [BSS99]). We write SEA(p, E). It requiresa prime p and an elliptic curve E defined over Fp as input. The algorithm returns |E(Fp )|. We
denote the result of SEA(p, E) by N . If isStrongP(r0 , k0 , p, N ) 6= 0 we are done. Otherwise
we have to invoke getParametersP(p, SEED), SEA(p, E), and isStrongP(r0 , k0 , p, N ) until we
succeed.

We point out two methods for speeding up randomApproachP. First, one may use an earlyabort-strategy. The fundamental idea of the SEA-algorithm is to write N = p + 1 − t, where t
is called the trace of E over Fp . The SEA-algorithm computes the trace t modulo some small
primes pi . Then t is recovered using the Chinese Remainder Theorem. If we know t mod pi
for such a small prime, we can check if pi | N . Thus if this is true and if in addition pi > k0 ,the condition k ≤ k0 is false for the current chosen curve. This early-abort-strategy has no
cryptographic implications.
A second enhancement is due to the fact that |E 0 (Fp )| = p + 1 + t, where E 0 denotes a twisted
elliptic curve of E over Fp (the term twisted elliptic curve is defined in Section 3.2.2). Thus

10

Generation Methods

Algorithm 3.2: randomApproachP(r0 , k0 )Input: Positive integers r0 and k0 with r0 ≥ 2160 and k0 ≤ 4.
Output: Primes p and r, and a positive integer k.
An elliptic curve E over Fp with |E(Fp )| = k · r and such that isStrongP(r0 , k0 , p, k · r) = r.
1: p ← getPrime(r0 , k0 );2: while true do3:
E ← getParametersP(p, SEED);4:N ← SEA(p, E);5:r ← isStrongP(r0 , k0 , p, N );6:
if r 6= 0 then7:
return (p, E, r, N/r);

if E(Fp ) turns out to fail the test isStrongP, we may test E 0 (Fp ) without performing the
SEA-algorithm. However, this approach is not covered by the above mentioned algorithm tochoose a curve verifiably at random. Nevertheless, if E is chosen verifiably at random, it iseasy to extend the above algorithm to allow the use of E 0 , too.
Depending on the implemented SEA-algorithm the bit-complexity of randomApproachP(r0 , k0 )may be shown to be O(log5+ k0 · r0 ) up to O(log7 k0 · r0 ) where  > 0 (see [BSS99], [Bai02b]).

3.2.2

Complex Multiplication Approach

In this section we discuss the CM-method to find an elliptic curve group over Fp . It is out of
the scope of this report to present in detail the theory of complex multiplication. We remarkthat none of the relevant standards comprises a detailed algorithm if a security level r0 and
k0 is defined in advance. We therefore sketch the algorithm cryptoCurve as developed in[Bai02a]. A rather abstract description of an algorithm using the CM-method may be foundin the standards of IEEE ([P1363]) or of ANSI ([X9.62], [X9.63]).
The central term in the framework of the CM-method is that of an imaginary quadratic
discriminant. We denote such a discriminant by ∆. It is a negative integer with ∆ ≡0, 1 mod 4. By O√∆ we denote the imaginary quadratic order of discriminant ∆, that is wehave O∆ = Z[ ∆+2 ∆ ]. In addition we write h(∆) for the class number of O∆ . If p is a prime
number then p is said to be a norm in O∆ if integers t, y exist such thatt2 − ∆y 2 = 4p .

(3.1)

If p is a norm in O∆ , using complex multiplication, elliptic curves E1,p and E2,p over Fp withendomorphism ring O∆ and|E1,p (Fp )| = p + 1 − t,|E2,p (Fp )| = p + 1 + t(3.2)

can be constructed as follows (see [AM93], [BSS99], [Bai02a]).
√Let H ∈ Z[X] be the minimal polynomial of j( ∆+2 ∆ ) where j is the elliptic modular function.
The degree of H is h(∆). Modulo p the polynomial H splits into linear factors. Let jp be azero of H mod p that is, jp is an integer such that H(jp ) ≡ 0 mod p. We assume ∆ < −4 in3.2 Finding Suitable Elliptic Curve Groups over Fp

11what follows (the cases ∆ = −3 and ∆ = −4 are not covered in this report). Then we havejp ∈/ {0; 1728}. Let sp be a quadratic nonresidue mod p. Withjp,1728 − jp(ap , bp ) = (3κp , 2κp )(3.3){E1,p , E2,p } = {(ap , bp ), (ap s2p , bp s3p )}.

(3.4)

κp =
we have

The elliptic curves E1,p and E2,p are said to be twisted elliptic curves over Fp . After thisconstruction it is not known which of the curves is E1,p and which is E2,p . However bychoosing points on each curve and testing whether their order is a divisor of p + 1 + t or
p + 1 − t, the curves E1,p and E2,p can be identified.
The crucial observation is that we can decide whether one of the groups E1,p (Fp ) or E2,p (Fp )is cryptographically strong before we actually construct those curves. We only need to know
the prime number p and its representation (3.1). Then we know the group orders of E1,p (Fp )and E2,p (Fp ) from (3.2). Using those orders and algorithm isStrongP we can check the
security conditions (O1), (O2), and (O3).

In general most of the time is spent to compute the polynomial H. The reason is thatthe coefficients of H become rather large, even for a discriminant of a small class number.
However, as explained in [P1363], [X9.62], [X9.63], and [Bai02a] depending on the value∆ mod 24 one may use alternative polynomials whose coefficients are very small comparedto H. Although working with these polynomials accelerates the CM-method significantly inpractice, the bit-complexity of the CM-method is invariant. We remark that Enge and Morain
recently proposed further alternative polynomials speeding up the CM-method ([EM02]).
Let h0 be a positive integer (its meaning will become clear soon). In [Bai02a] the algorithm
cryptoCurve(r0 , k0 , h0 ) is described. It implements the above proceeding. The input parameter h0 allows to choose an individual lower bound of the class number of the imaginary
quadratic discriminant in use. Its output is a discriminant ∆ with h(∆) ≥ h0 , a prime p ofbitlength blog2 k0 · r0 c + 1, a prime r with r ≥ r0 , a positive integer k ≤ k0 , and an elliptic
curve group E(Fp ) of order k · r such that isStrongP(r0 , k0 , p, r · k) returns r. In addition
the algorithm returns a base point G ∈ E(Fp ) of order r. An algorithm to find such a point
G is described in Section 3.2.3.
In cryptoCurve one may choose a prime p in advance, too. It is shown in [Bai02a] that the bitcomplexity of cryptoCurve(r0 , k0 , h0 ) is at most O(log4 r0 k0 (log r0 k0 + h20 log h0 log log h0 ) +h60 log h0 ), if p is not given. As explained in Section 1.2 the term ’at most’ means that we do
not assume to work with optimized algorithms.

3.2.3

Finding a Point of Large Prime Order

We explain how to find a base point G. Let a prime p and an elliptic curve E over Fp be
given. As usual we write |E(Fp )| = k · r with a prime r. We then choose a random elementx0 ∈ Fp , that is we uniformly take a non-negative integer x0 , x0 < p. If x30 + ax0 + b is asquare in Fp , we denote by y0 a square root of x30 + ax0 + b in Fp . Otherwise we choose new
random values x0 until we succeed.
We may assume 1 ≤ y0 ≤ p − 1. y0 may be computed using Shank’s RESSOL algorithm([Coh95]) or the algorithm in Annex D.1.4 of [X9.62]. One may flip a coin to choose a root12

Generation Methods

p+1
1 ≤ y0 ≤ p−1
2 or 2 ≤ y0 ≤ p − 1. Then (x0 , y0 ) is a point in E(Fp ) \ {O}. If k · (x0 , y0 ) 6= O,
then G := k · (x0 , y0 ) is a point of order r due to a theorem of Lagrange. However, in order torecover a false input, we propose to compute r · G. If r · G 6= O, an error message is output.

The computation of G is dominated by drawing a square root in Fp . The bit-complexityof this procedure is O(log4 p) ([Coh95]). In addition, the verification of the order of G is ofbit-complexity O(log4 p), too. Thus the whole computation of G and verifying its order is ofbit-complexity O(log4 p).

3.2.4

Comparison of Both Generation Methods

In this section we compare the random approach to the CM-method to find a cryptographicallystrong elliptic curve group over Fp . We compare the security and performance implicationsof both generation methods.
Let us first turn to security. The main advantage of the random approach is that every
cryptographically strong elliptic curve group over Fp is computed with approximately thesame probability. Thus the generated curves are not special in any sense. Contrary the CMmethod is only applicable if discriminants of reasonable small class numbers are in use, say
discriminants of class number at most 1000 (see [Bai02a]). Then the generated curves are
special in the sense that their endomorphism ring has a class number at most 1000. Thus
not every cryptographically strong elliptic curve group may be output by the CM-method.
However, as no attack makes use of this property, we do not consider a small class number to
imply cryptographic weakness.
Next we discuss the practical performance. We present practical data for the case k0 = 1,
that is we search for an elliptic curve group of prime order. We write b for the bitlength of r0 .
We stated in Section 3.2.1 that the bit-complexity of the random approach only depends on b.
However, as explained in Section 3.2.2 the bit-complexity of the CM-method depends on theclass number of the imaginary quadratic discriminant in use, too. In [Bai02b] we investigate
in detail for which class number both approaches have the same run time in practice for somegiven, fixed b. We call this class number the crossover class number and denote it by hc (b).
In order to determine hc (b) we first measured the run time of randomApproachP(r0 , k0 ). We
point out that we implemented the early-abort-strategy and the use of a twisted curve as
explained in Section 3.2.1. We then invoked cryptoCurve(r0 , k0 , h0 ) for various class number
bounds h0 to get the crossover class number hc (b) (for details we refer to [Bai02b]). All tests
are performed on an ordinary PC (Athlon XP1600+ running Linux 2.4.10 at 1.4 GHz andhaving 1GByte main memory) using freely available software. The result is given in Table
3.1.
b
Run time in minuteshc (b)

160
3.63
750

170
4.87
820

180
7.97
960

190
10.3
1040

200
13.1
1090

210
16.7
1200

Table 3.1: Average run time of the random approach to find a cryptographically strong
elliptic curve group E(Fp ) of prime order. b denotes the bitlength of p. For each b we performed
100 tests. In addition, crossover class numbers hc (b) are given.

3.3 Finding Suitable Elliptic Curve Groups over F2n13

The CM-method is supposed to be faster in practice if h(∆) < hc (b) for the discriminant∆ used in the CM-method. We conclude from Table 3.1 that the crossover class number israther large. Thus even if one respects the additional requirement of the GISA that the classnumber of the fundamental discriminant corresponding to ∆ is at least 200, the CM-method
is superior to the random approach for bitlengths of cryptographic interest. Finally, we expect
the crossover class number to increase if polynomials proposed by Enge and Morain ([EM02])
are used in the CM-method.

3.3

Finding Suitable Elliptic Curve Groups over F2n

In this section we present three methods to find a cryptographically strong elliptic curve groupover a finite field of characteristic 2. First, in Section 3.3.1 we describe the random approach.
Then in Section 3.3.2 we present the CM-method. Finally, in Section 3.3.3 we turn to the
Koblitz approach.
We first describe an algorithm to check the conditions (E1), (E2), and (E3) of Section 2.2.
The algorithm is called isStrong2(r0 , k0 , n, N ), which is very similar to algorithm isStrongP.
It requires positive integers r0 and k0 as input with r0 ≥ 2160 and k0 ≤ 4, respectively. In
addition the algorithm gets a prime n and a positive integer N . As in the case of odd
characteristic we substitute 2160 by r0 and 4 by k0 in (E1). isStrong2(r0 , k0 , n, N ) returns
a prime r if N = k · r is the order of a cryptographically strong elliptic curve group over F2nwith r ≥ r0 and k ≤ k0 . Otherwise it returns 0. We point out that |E(F2n )| is even for acryptographically strong elliptic curve group E(F2n ).

Algorithm 3.3: isStrong2(r0 , k0 , n, N )Input: Positive integers r0 and k0 with r0 ≥ 2160 and 2 ≤ k0 ≤ 4.
A prime n and the order N of a group of rational points of an elliptic curve over F2n .
Output: A prime r if N = k · r is the order of a cryptographically strong elliptic curve group overF2n with r ≥ r0 and k ≤ k0 , and 0 otherwise.
1: //check if N is in the√Hasse interval
2: if |N − (2n + 1)| > 2 2n then3:
return (0);4: r ← 0; k ← 0; //initialize both r and k with 0
5: //check by trialdivision if cofactor is at most k0 ; if not, return 0
6: for i ← 2; i ≤ k0 ; i ← i + 1 do
7:
if i | N AND isPrime(N/i, 50) = true AND N/i ≥ r0 then8:r ← N/i; k ← i; break;
9: if r = 0 then10:
return (0);11: //check condition (E2)
12: qr ← 1 mod r;
13: for i ← 1; i ≤ 19; i ← i + 1 do
14:
qr ← 2n · qr mod r;
15:
if qr = 1 then16:
return (0);17: return (r);14Generation Methods

Once we know that the bit-complexity of isStrongP(r0 , k0 , p, N ) is O(log3 p), it is obviousthat the bit-complexity of isStrong2(r0 , k0 , n, N ) is O(n3 ).

3.3.1

Random Approach

In this section we describe an algorithm to randomly generate a cryptographically strong
elliptic curve group E(F2n ). We denote this algorithm by randomApproach2(r0 , k0 , n). Its
input are positive integers r0 and k0 with r0 ≥ 2160 and 2 ≤ k0 ≤ 4, and a prime n,n = dlog2 k0 · r0 e. The algorithm outputs positive integers r and k, and an elliptic curve E
over F2n such that |E(F2n )| = k · r and such that isStrong2(r0 , k0 , n, k · r) returns r.
Similar as in the case q = p the proceeding is as follows: Choose parameters a and b in F2nwith b 6= 0, determine the order of the group of rational points of the curve (a, b) over F2n ,and finally check if this group is cryptographically strong.

Again we recommend to choose a and b verifiably at random. The algorithm is very similar tothe case q = p. A detailed explanation may be found for example in [X9.62], Annex A.3.3.1.
We write getParameters2(n, SEED) for any algorithm which returns an elliptic curve E
defined over F2n verifiably at random.

If the curve E = (a, b) is chosen we have to determine the group order of E(F2n ). Currently,
the best known algorithm for this task is a variant of an algorithm due to Satoh ([Sat99]).
This variant is proposed by Fouquet, Gaudry, and Harley ([FGH00], [FGH01]). It uses a
combination of the early-abort-strategy in the SEA-algorithm and the Satoh-algorithm. We
denote their method by SFGH(n, E). It requires a prime n and an elliptic curve E as input.
It returns |E(F2n )|, if the early-abort-strategy does not show cryptographic weakness, and 0
otherwise. We denote the result of SFGH(n, E) by N . If N 6= 0 and isStrong2(r0 , k0 , n, N ) 6=
0 we are done. Otherwise we have to invoke getParameters2(n, SEED), SFGH(n, E), andisStrong2(r0 , k0 , n, N ) until we succeed.

Algorithm 3.4: randomApproach2(r0 , k0 , n)Input: Positive integers r0 and k0 with r0 ≥ 2160 and 2 ≤ k0 ≤ 4.
A prime n with n = dlog2 k0 · r0 e.
Output: A prime r and a positive integer k.
An elliptic curve E over F2n with |E(F2n )| = k · r and such that isStrong2(r0 , k0 , n, k · r) = r.
1: while true do2:
E ← getParameters2(n, SEED);3:N ← SFGH(n, E);
4:
if N 6= 0 then5:r ← isStrong2(r0 , k0 , n, N );6:
if r 6= 0 then7:
return (E, r, N/r);

We remark that one may again use a twisted elliptic curve of E over F2n to speed up
randomApproach2. The bit-complexity of Satoh’s algorithm may be shown to be O(n3+ )for some  > 0 ([Sat99]). Although SFGH uses a mixed strategy, we assume that SFGH has

3.3 Finding Suitable Elliptic Curve Groups over F2n15

the same bit-complexity. Thus the bit-complexity of algorithm randomApproach2(r0 , k0 , n) isO(n4+ ).

3.3.2

Complex Multiplication Approach

In this section we discuss the CM-method to find an elliptic curve group over F2n . In orderto implement this approach efficiently, we assume that a database of discriminants of classnumbers m · n is to our disposal, where m ∈ N. For instance, such a database was computedin the framework of [Bai02a].
Let ∆ be an imaginary quadratic discriminant of class number h(∆), n | h(∆). We first haveto investigate the following two norm equations:t02 − ∆y 02 = 8 ,2

t − ∆y

2

= 2

n+2

(3.5)
.

(3.6)

In order to find an elliptic curve having the desired properties, we have to ensure that Equation (3.5) has no integer solution (t0 , y 0 ), while Equation (3.6) has a solution (t, y) ∈ Z2 .
If this is true, using complex multiplication, elliptic curves E1,2n and E2,2n over F2n withendomorphism ring O∆ and|E1,2n (F2n )| = 2n + 1 − t,|E2,2n (F2n )| = 2n + 1 + t(3.7)

can be constructed as explained below (see [LZ94], [X9.62]). We set N1 = |E1,2n (F2n )| andN2 = |E2,2n (F2n )| in what follows.
√

As in Section 3.2.2 let H ∈ Z[X] denote the minimal polynomial of j( ∆+2 ∆ ). Modulo 2 thepolynomial H splits into pairwise different polynomials of degree n, all of which are irreducible
in F2 [X]. Let j2n be a zero of H in F2n . We have j2n 6= 0. If N1 ≡ 0 mod 4 we set
E1,2n = (0, j2−1n ),E2,2n = (1, j2−1
n ) .

(3.8)

E1,2n = (1, j2−1n ),E2,2n = (0, j2−1
n ) .

(3.9)

If N1 ≡ 2 mod 4 we define

As n is odd, it is well known that this definition is correct (e.g. [LZ94]). The elliptic curves
E1,2n and E2,2n in Equations (3.8) and (3.9) are called twisted elliptic curves over F2n .
As in the case q = p we can check if one of the numbers N1 or N2 is the order of a cryptographically strong elliptic curve group before we actually construct the corresponding curves.
Furthermore, again we can use alternative polynomials whose coefficients are very small compared to H. The bit-complexity of the CM-method for fields of even characteristic is the sameas in the case of a finite prime field.

3.3.3

Koblitz Approach

In this section we explain the Koblitz approach. The Koblitz approach bases on a theoremof Weil. In the scope of this report, it works as follows.

16

Generation Methods

In all, there are two elliptic curves defined over F2 as introduced in Section 2.2. By K1
we denote the elliptic curve (0, 1), by K2 the curve (1, 1). It is easy to see that K1 (F2 ) ={(0, 1), (1, 0), (1, 1), O} and K2 (F2 ) = {(0, 1), O}. Thus we have |K1 (F2 )| = 4 and |K2 (F2 )| =2. For both groups we write the group order as 2 + 1 − ti , where i ∈ {1, 2}. We then associate
to each curve a polynomial Fi := 2X 2 − ti X + 1. Let α1i be a (complex) root of Fi , and let m
be a positive integer. Then a theorem of Weil states that |Ki (F2m )| = 2m + 1 − (αim + αi m ),where αi is the complex conjugate of αi .
√√It is easy to see that α1 = −1+2 −7 and α2 = 1+ 2 −7 . For instance, we have|K1 (F2163 )| = 22 · 653 · 6521 · 34101072914026637 · 20129541232727197849723433 ,|K2 (F2163 )| = 2 · 5846006549323611672814741753598448348329118574063 ,where we write both integers with respect to their prime factorization. The group K2 (F2163 )obviously respects the requirements (E1) and (E3). In addition, condition (E2) is satisfied,
too. Hence according to our definition K2 (F2163 ) is a cryptographically strong elliptic curvegroup. In general, once we know n we can easily determine whether one of the groups Ki (F2n )is cryptographically strong. The elliptic curves Ki are called Koblitz curves.
For all primes n, 163 ≤ n ≤ 500, we determined if the groups K1 (F2n ) and K2 (F2n ) are cryptographically strong, respectively. We implemented a C++ program and used the computer
algebra system LiDIA ([LiDIA]). The result is given in Table 3.2. It is in conformance withthe results of Solinas ([Sol97]). We see that there are only 6 exponents n for which the group
K1 (F2n ) is secure. The same is true for K2 (F2n ).
K1 (F2n ): nK2 (F2n ): n

233
163

239
283

277
311

283
331

349
347

409
359

Table 3.2: Exponents n, 163 ≤ n ≤ 500, yielding a cryptographically strong elliptic curvegroup Ki (F2n ).
We remark that the endomorphism ring of both K1 and K2 is O−7 . Thus its class number
is equal to 1. Finally, we point to a security issue of elliptic curve groups generated by the
Koblitz approach. Let K(F2n ) be the group in√use. Then a method due to Gallant, Lambert,
and Vanstone ([GLV00]) is faster by a factor 2n than the standard square root attacks.

3.3.4

Finding a Point of Large Prime Order

We explain how to find a base point G for elliptic curve groups E(F2n ). The proceeding issimilar to the case q = p as described in Section 3.2.3. The following algorithm may be foundin [X9.62].
Let a prime n and an elliptic curve E = (a, b) over F2n be given. As usual we write |E(F2n )| =k · r with a prime r. We then choose a random element x0 ∈ F2n . If x0 = 0, the corresponding
n−1
point (0, b2 ) is of order 2 in E(F2n ). Hence this point is not a suitable choice. We therefore
assume x0 6= 0. We set α = x30 +ax20 +b. If α = 0, we set P = (x0 , 0). For fields of characteristic
2 it is common to solve quadratic equations of the form z 2 + z = β (an algorithm is given−1
in Annex D.1.6 of [X9.62]). Thus we set β = α · x−2
0 , z = y · x0 , and test if the equation

3.3 Finding Suitable Elliptic Curve Groups over F2n17

z 2 + z = β has a solution z0 ∈ F2n . If not, we choose a new random value x0 . Otherwise we
set P = (x0 , z0 · x0 ). Then P is a point in E(F2n ) \ {O}. If k · P 6= O, then G := k · (x0 , y0 ) isa point of order r due to a theorem of Lagrange. As in the case q = p we propose to computer · G. If r · G 6= O, an error message is output. If k · P = O a new element x0 is chosen.

The computation of G involves solving a quadratic equation in F2n and computing scalarmultiplies of a point. The bit-complexity depends on the representation of the finite fieldF2n . For instance, if we choose a normal basis, solving a quadratic equation is for free (only
XOR and squaring).

3.3.5

Comparison of the Three Generation Methods

We compare the three generation methods described in the previous sections.
First, we discuss the random approach. We cite timings from [FGH01] in Table 3.3. The
authors of [FGH01] do not clearly state what they mean by a secure elliptic curve. However,they use the term almost prime in the context of the corresponding group order. We therefore
assume that the timings in Table 3.3 give a reasonable estimation for run times to find a
cryptographically strong elliptic curve group in the sense of this report.
n
Run time in seconds

163
5

193
10

197
10

233
21

239
22

Table 3.3: Average run time of the random approach to find an elliptic curve group E(F2n )of almost prime order. The timings come from [FGH01] and are measured on an Alpha EV6
running at 750 MHz.
We point out that the timings are measured on a quite different platform compared to the
PC used in Section 3.2.4. Nevertheless the run times give evidence that the SFGH withearly-abort-strategy is very fast in practice. Again we point to the advantage of the random
approach that every cryptographically strong elliptic curve group is chosen with approximately the same probability. Thus again the selected groups are not special in any sense.
Second, we do not have current run times of the CM-method. However, we do not expect
the CM-method to be significantly faster than the random approach as we have to choose theclass number of the discriminant to be a multiple the field degree n. As n ≥ 160 the classnumber is at least 160, too. We therefore recommend not to use the CM-method in the caseq = 2n .
Third, we remark that the current record of counting the number of rational points of ageneral group E(F2n ) is hold by a group of INRIA ([Har02]). They succeeded to determine
the group order of a randomly chosen curve for n = 32003. The run time on the DEC Alpha
EV6 was about 27 hours. This shows that the random approach is very fast in case of fields
of characteristic 2, even for large fields.
Finally, we turn to the Koblitz approach. As stated in Section 3.3.3, if we assume 160 ≤n ≤ 500 there are only 12 elliptic curve groups suitable for use in cryptography. This isa very restricted choice. In addition, as mentioned at√ the end of Section 3.3.3, computing
discrete logarithms in such groups is faster by a factor 2n than the standard general discrete
logarithm algorithms. Nevertheless all Koblitz groups respect the requirements (E1), (E2),18

Generation Methodsand (E3). They may thus be regarded as cryptographically secure from a current point ofview.

Chapter 4

Implementation Issues
The most important operation in the framework of elliptic curve cryptography is the scalarmultiplication. The scalar multiplication is the problem of computing the point s · P , if an
integer s and a rational point P ∈ E(Fq ) are given for some elliptic curve E defined over Fq .
Before actually discussing algorithms to perform a scalar multiplication, Section 4.1 deals
with the problem of how to implement the arithmetic in a finite field. First, in Section 4.1.1
we describe methods to efficiently implement the arithmetic in Fp . In addition, we present aclass of primes p for this purpose. The problem of how to efficiently implement arithmetic infinite fields of characteristic 2 is addressed in Section 4.1.2.
There are a lot of publications dealing with proposals of speeding up the scalar multiplication
on a certain class of elliptic curves. It is out of the scope of the evaluation report at hand to
discuss all investigations in detail. Instead we give an overview of the currently methods inuse. A survey of fast algorithms for implementing the scalar multiplication in a general groupis given in [Gor98]. We discuss in detail methods for a scalar multiplication in Section 4.2.
Then Section 4.3 discusses the problem if a special choice of curve parameters can significantly
decrease the number of bits to represent elliptic curve points. We close this chapter with a
discussion of special parameters for smart card implementations in Section 4.4.

4.1

Arithmetic in Finite Fields

In this section we review how to efficiently implement the arithmetic in a finite field Fq . First,
in Section 4.1.1 we show how to efficiently implement the arithmetic in Fp . In addition, we
present primes of a special form as proposed in [NIST]. Next, in Section 4.1.2 we discuss thetwo common ways to represent a finite field of characteristic 2.

4.1.1

Arithmetic in Finite Prime Fields

In this section we show how to speed up the multiplication operation in a finite prime field.
As usual we denote by p the cardinality of the prime field. We remark that the generation
process of the elliptic curve may be performed more efficiently, too, when using the methodsof this section.

20

Implementation Issues

In Section 4.2.4 we will see that the multiplication of elements in Fp is by far the mostimportant field operation to implement arithmetic in elliptic curve groups. As usual we
assume that elements in Fp are represented as non-negative integers less than p. If we have tocompute a product of elements e1 and e2 in Fp , a naive approach would be to first computethe integer e1 ·e2 in Z. Thus in this intermediate state we get an integer of order of magnitude
p2 . The result of the multiplication is the unique integer in [0, . . . , p − 1] which is congruent
e1 · e2 modulo p. Thus we would have to perform a reduction operation modulo p.

However, there are representations of the field elements of Fp to speed up this elementary
method. The most famous and in general most efficient one is due to Montgomery ([Mon85]).
We refer to his paper or to [BSS99] for details.
In addition, we mention primes of a special form as proposed in [NIST]. The fundamental
idea is to use prime numbers p of a special form, that is their binary expansion is very sparse.
The primes are called generalized Mersenne numbers. The main speed up is due to the factthat the reduction of e1 · e2 modulo p may be performed by means of integers of order ofmagnitude less than p. Furthermore, if we choose the non-vanishing 2-powers in the binary
expansion of p with care, the representation of integers may be adapted to the hardware inuse.
For instance, assume that the processor uses words of 64 bits. The prime p = 2192 − 264 − 1
is very attractive for this platform, as we now see. The product e1 · e2 in Z may be written
in the form
A5 · 2320 + A4 · 2256 + A3 · 2192 + A2 · 2128 + A1 · 264 + A0 ,(4.1)
where each Ai is of bitlength 64 and hence fits in a word.
Furthermore, the sparse binary expansion of p shows 2192 ≡ 264 + 1 mod p. This obviously
yieldse1 · e2 ≡ (A5 + A4 + A2 ) · 2128 + (A5 + A4 + A3 + A1 ) · 264 + A5 + A3 + A0 .

(4.2)

It is possible that (A5 +A4 +A2 )·2128 has to be reduced modulo p. However, the computationin Equation (4.2) mostly consists of additions of integers which fit in word.
More generalized Mersenne numbers for fields of different bitlengths may be found in [NIST].
In addition, a further discussion of moduli of a special form may be found in [MOV97].

4.1.2

Arithmetic in Finite Fields of Characteristic 2

In this section we shortly review the common representations of fields with 2n elements.
First, we discuss the representation of F2n with respect to a polynomial basis. Then we turnto the notion of a normal basis. We remark that the implementation of the efficient point
counting algorithm described in Section 3.3 uses a polynomial basis to represent the field F2n .
However, as efficient algorithms to change the basis are known (see for instance Appendix
D.2.3 of [X9.62]), this constitutes no restriction for use of these parameters with respect to anormal basis.
Polynomial Basis Representation
Let f be an irreducible polynomial with coefficients in F2 of degree n. It is well known thatF2n = F2 [X]/(f ), where we write (f ) for the principal ideal in the ring F2 [X] generated by4.1 Arithmetic in Finite Fields

21

the polynomial f . Such a representation of F2n is called a polynomial representation. The
elements 1, X, . . . , X n−1 form a basis, which we call a polynomial basis. A polynomial basis
is mostly used to implement the arithmetic in F2n in software.
In order to decrease the computational complexity, f should be as sparse as possible. It is easy
to see that at least 3 coefficients of f are non-zero. If f actually is of the form X n + X κ + 1,
1 ≤ κ ≤ n − 1, f is called a trinomial . The polynomial basis with respect to f is said to bea trinomial polynomial basis, which commonly is abbreviated by TPB. If a TPB exists, thesmallest possible value κ should be used for interoperability reasons, as proposed in [X9.62]
or [P1363]. A table of fields F2n , 160 ≤ n ≤ 2000, for which a TPB exists may be found in
Annex C.2 of [X9.62].
However, if a TPB does not exist for the field F2n , a polynomial f of the form X n + X κ3 +X κ2 + X κ1 + 1, 1 ≤ κ1 < κ2 < κ3 ≤ n − 1, may be chosen (it is obvious that a polynomial
X n + X κ2 + X κ1 + 1, 1 ≤ κ1 < κ2 ≤ n − 1 is not irreducible in F2 [X]). The polynomial f
is called a pentanomial in this case, and the corresponding basis is said to be a pentanomial
polynomial basis, which commonly is abbreviated by PPB. If n ≥ 4, the existence of a PPB
is known. Again, for interoperability reasons, a PPB should be used where κ1 is as small as
possible, κ2 is as small as possible for this particular κ1 , and finally κ3 is as small as possible
for these particular chosen κ1 and κ2 . A table of fields F2n , 160 ≤ n ≤ 2000, for which a
PPB, but no TPB exists, may be found in Annex C.3 of [X9.62].
Normal Basis Representation
In this section we discuss normal basis representations. A normal basis is a basis of the2
n−1
form α, α2 , α2 , . . . , α2 , where α ∈ F2n . A normal basis is attractive for implementing
arithmetic in F2n in hardware, as squaring an element in F2n is simply a cyclic shift. However,multiplying elements of F2n with respect to a normal basis is in general a non-trivial andcumbersome task. It is therefore common to use a Gaussian normal basis, abbreviated by
GNB. It is well known that if 8 - n, a GNB exists. However, as our requirement (E3) ofSection 2.2 assumes n to be prime, this is no restriction for cryptographic purposes.
The complexity of arithmetic with respect to a GNB is measured in terms of the type of
the GNB in use. The type is a positive integer, and as in [X9.62] we denote the type by T .
Roughly speaking, the smaller the type T is, the more efficiently the arithmetic in F2n may
be implemented. A necessary condition for a positive integer T 0 to be the type of a GNB is
that T 0 n + 1 is prime. Thus in this report a GNB of type 1 is not possible.
Recommended Fields of Characteristic 2
In this section we list finite fields of characteristic 2, which we propose for use in cryptography.
The results may be found in Table 4.1. The table bases on Annex C of [X9.62]. In addition,for each chosen n we show if a TPB exists or not. In Table 4.1 we plot a star in the columnof n if a TPB for the field F2n exists. Otherwise, we set a star in the corresponding row of
PPB. Finally, we give the type T of the GNB. We remark that in Table C-1.a of [X9.62], novalue T is given for n = 179, although a GNB of type 2 exists for this field. We therefore
checked the relevant data of Annex C.1 in [X9.62] using the computer algebra system LiDIA([LiDIA]). Besides n = 179 we got the same results as presented in [X9.62]. Furthermore, ourtable is in conformance with the data of Annex A.8 in [P1363].

22

Implementation Issues
n
TPB
PPB
T
n
TPB
PPB
T
n
TPB
PPB
T
n
TPB
PPB
T
n
TPB
PPB
T

163

167
*

*
4
239
*

14
241
*

2
317

6
331

*
26
409
*

*
6
419

4
491

*
2
499

*
2

*
4

173

179

181

*
2
251

*
2
257
*

*
2
337
*
10
421
*
10

191
*

193
*

*
6
263
*

2
269

4
271
*

6
347

6
349

*
8
353
*

*
6
431
*

*
10
433
*

14
439
*

2

4

10

6
359
*
2
443
*
2

197
*
18
277
*
4
367
*

199
*
4
281
*
2
373

6
449
*

*
4
457
*

8

30

211
*
10
283
*
6
379
*
12
461
*
6

223
*
12
293
*
2
383
*
12
463
*
12

227

229

*
24
307

*
12
311

*
4
389

*
6
397

*
24
467

*
6
479
*

8
487
*

8

4

*
6

233
*
2
313
*
6
401
*

Table 4.1: Recommended finite fields F2n , 160 ≤ n ≤ 500, for use in elliptic curve cryptography. The star in the corresponding row of TPB and PPB indicates, which polynomial
representation should be used. In addition, we list the type T of the GNB to choose.

4.2

Scalar Multiplication

In this section we review methods for efficiently performing a scalar multiplication. An
important issue in this context is the addition of two rational points. We address this subject
in Section 4.2.1 and Section 4.2.2 for finite prime fields and finite fields of characteristic 2,
respectively.
We then present in Section 4.2.3 a method, which is only applicable for Koblitz curves. Finally,in Section 4.2.4 we turn to general methods for efficiently performing the scalar multiplication.

4.2.1

Point Addition for Elliptic Curves over Fp

We describe a method for efficiently adding two rational points in a group E(Fp ). We follow
the discussion in [P1363] and [BSS99]. We remark that this method is independent of theprime field Fp .

As of today it is common to implement arithmetic in a group E(Fp ) with respect to weighted
projective coordinates as proposed in [CC87] or [CMO98]. The curve equation is then of theform Y 2 = X 3 + aXZ 4 + bZ 6 , and if (X, Y, Z) is a point on the curve, its affine coordinatesare (X/Z 2 , Y /Z 3 ), provided that Z 6= 0. A point with Z = 0 corresponds to the point at
infinity O.
The main advantage when using weighted projective coordinates is that we do not have to
do a field inversion in Fp when adding points. However, the number of multiplications in Fp

4.2 Scalar Multiplication

23

increases. Often the use of projective coordinates is then superior to an implementation withrespect to affine coordinates.
More precisely, let P1 = (X1 , Y1 , Z1 ) and P2 = (X2 , Y2 , Z2 ) be points in E(Fp ). We skip thetrivial cases P1 = O, P2 = O, and P1 = ±P2 . Then according to [P1363] and [BSS99] ageneral addition of P1 and P2 requires 16 multiplications in Fp . If in addition one point isgiven in affine coordinates, that is Z1 = 1 or Z2 = 1 the number of multiplications decreases
to 11. This case is denoted by mixed coordinates. If we add two points represented inaffine coordinates we have to do 1 inversion and 3 multiplications in Fp . Thus in the generalcase the use of weighted coordinates is superior to an implementation with respect to affine
coordinates, if an inversion costs more than 13 multiplications. If one of the Z-coordinates isequal to 1, this number decreases to 8.
If we double the point (X1 , Y1 , Z1 ), the number of multiplications is in general 10. If wehave a = −3, this number decreases to 8. The affine doubling requires 1 inversion and4 multiplications in Fp . Thus weighted projective coordinates are faster in practice, if an
inversion in Fp is slower than 6 or 4 multiplications, respectively. We remark that choosing
elliptic curves verifiably at random with a = −3 is proposed as an extension to the generalalgorithm in [P1363] (see Annex A.12.4). Furthermore, the implementation of the CM-method
as described in [Bai02a] yields elliptic curves with a = −3, too.
Table 4.2 summarizes the above discussion.
Operation
General Addition
General Doubling
Doubling (a = −3)

Affine Coord.
1I + 3M
1I + 4M
1I + 4M

Mixed Coord.
11M
n/a
n/a

Weighted Proj. Coord.
16M
10M
8M

Table 4.2: Cost of a point addition in a group E(Fp ). A field inversion is abbreviated by I,a multiplication in Fp by M .

4.2.2

Point Addition for Elliptic Curves over F2n

The method presented in this section is very similar to the ideas of the previous section. We
therefore summarize the results. Again we follow the discussion in [P1363] and [BSS99].
An elliptic curve over F2n in weighted projective coordinates is given by the equation Y 2 +XY Z = X 3 + aX 2 Z 2 + bZ 6 . Let P1 = (X1 , Y1 , Z1 ) and P2 = (X2 , Y2 , Z2 ) be points inE(F2n ). As above we leave out the trivial cases P1 = O, P2 = O, and P1 = ±P2 . Then
according to [P1363] and [BSS99] a general addition of P1 and P2 requires 15 multiplications
and 5 squarings in F2n . As the complexity of a squaring depends on the representation of the
field F2n , it is common to enumerate it separately. If in addition one point is given in affine
coordinates the number of multiplications and squarings decrease to 11 and 4, respectively.
We remark that it is attractive to use a = 0 from an implementation point of view of thepoint addition, as the number of multiplications and squarings is less than above. However,on the other hand we have k = 4 in this case, yielding an additional bit compared to an
elliptic curve group with the same security level, but k = 2.

24

Implementation Issues

The corresponding complexity assertions for a point doubling and a comparison with an
implementation with respect to affine coordinates may be seen from Table 4.3.
Operation
General Addition
Addition (a = 0)
Doubling

Affine Coord.
1I + 2M + 1S
1I + 2M + 1S
1I + 2M + 1S

Mixed Coord.
11M + 4S
10M + 3Sn/aWeighted Proj. Coord.
15M + 5S
14M + 4S
5M + 5S

Table 4.3: Cost of a point addition in a group E(F2n ). A field inversion is abbreviated by
I, a multiplication in F2n by M , and a squaring in F2n by S.

4.2.3

Scalar Multiplication on Koblitz Curves

In this section we describe a method for performing the scalar multiplication in the groups
K1 (F2n ) and K2 (F2n ) as introduced in Section 3.3.3. The most significant improvement isdue to Solinas ([Sol97], [Sol00]). Solinas proposes to represent the integer s with respect to
the Frobenius map. According to his paper [Sol97] his method yields a speed up by a factor 2
compared to the previous best known algorithms for scalar multiplications on Koblitz curves.
Thus Koblitz curves are very attractive if fast arithmetic is important (e.g. in smart cards).
We remark that the method of Solinas was extended to a larger class of elliptic curves by
Gallant, Lambert, and Vanstone ([GLV01]). Their method even comprises elliptic curves overfinite prime fields.

4.2.4

Scalar Multiplication on a General Elliptic Curve

This section deals with methods for computing a scalar multiple of an elliptic curve point. We
focus our discussion with respect to the following two requisites. First, we present methods
for efficiently performing the scalar multiplication if the point P is not known in advance.
Nevertheless in cryptographic schemes we may assume that P is in the subgroup generatedby G. Second, we turn to the case that P is a previously known, fixed point. An applicationof such a method is, for instance, the scalar multiplication for the cryptographic base point
G. The discussion in this section is valid for both a field Fp and F2n .
We first assume that P is not fixed. A fundamental algorithm to determine the point sP is
to implement fast exponentiation. Its underlying idea is to write s as its binary expansion
and compute sP by the double and add algorithms of the previous sections (see for instance
Algorithm IV.1 in [BSS99]). However, most of the standards (e.g. [P1363], [X9.62]) propose to
implement a variant which uses a signed representation of the scalar s. Often this expansion
is referred to as a NAF, where NAF stands for non-adjacent form of the scalar s. A signed
representation of s works fine, as inversion in the group E(Fq ) is for free. We present a variantof the algorithms in [P1363] or [X9.62] as our algorithm NAF(s, P ). The algorithm requires
an integer s and a point P . It returns the point sP . We make use of the fact that we know
the order of P .
We turn to the second case. We assume that we have to compute a scalar multiplication fora fixed point G. Then it is often advantageous to initially do some precomputations and then4.2 Scalar Multiplication

25

Algorithm 4.1: NAF(s, P )Input: An integer s and a point P of order r.
Output: The point sP .
1: s ← s mod r; //s ∈ {0, . . . , r − 1}
2: if s = 0 OR P = O then3:
return( O );4: if s > r/2 then5:s ←Pr − s; P ← −PP; ll
6: 3s = i=0 hi 2i ; s = i=0 si 2i ; //find binary expansions of 3s and s with hl = 1
7: R ← P ; i ← l − 1; //initialize the result point and counting variable
8: while i ≥ 1 do
9:R ← 2R;10:
if hi = 1 AND si = 0 then11:
R ← R + P;
12:
if hi = 0 AND si = 1 then13:
R ← R − P;14:i ← i − 1;
15: return( R );determine the point sG. The initial step has only to be performed once. The precomputed
points have to be stored.
The most common method is the sliding window method (see for instance [BSS99], AlgorithmIV.4). Additionally we point to a method of Lim and Lee [LL94]. Their method may be very
fast, if a lot of precomputations are performed. However, as we then have to store quite a lotof points, this may cause memory problems.
A survey of the cost of the different methods to compute a scalar multiple may be found in[BSS99], Table IV.3 .

4.2.5

Scalar Multiplication on Special Elliptic Curves

In this section we mention two representations of elliptic curves for speeding up the scalarmultiplication. The first one is called the Hesse form, the second one is called the Montgomeryform.
We first discuss the Hesse form and follow Smart ([Sma01]. He shows how to speed up
the scalar multiplication by parallelizing computational steps if the elliptic curve is given in
Hesse form. Let E denote this curve. We assume that E is given by an equation as defined in
Chapter 2. In his paper, Smart shows that if q ≡ 2 mod 3 and 3 | |E(Fq )|, then the defining
equation of E may be transformed to a representation in Hesse form. This representation
allows efficient implementation of the group law in E(Fq ). We refer to Smart’s paper for
details.
The requirement 3 | |E(Fq )| implies in our context, that we can apply Smart’s method if andonly if q = p (if q = 2n , the group order is divisible by 6 in this case). Thus let q = p. We
then search for an elliptic curve group E(Fp ) of order 3r. We remark that both generation
methods of Section 3.2 seem to be appropriate in this case. As far as the CM-method isconcerned this is obvious from the fact that we can verify this requirement once we know

26Implementation Issues

the group orders of Equation (3.2). If the random approach is used, the early-abort-strategy
shows at a very early stage of the SEA-algorithm, if the group order is divisible by 3. Thus
we expect that the assertions of Section 3.2.4 are valid in this case, too.
We now discuss the Montgomery form. Initially it was proposed by Montgomery to accellerate
the elliptic curve factoring method ([Mon87]). Montgomery shows how to reduce the numberof multiplications in Fq to compute the x-coordinate of a scalar multiple of a rational point,
if an elliptic curve in a special representation is used.
However, as in the case of the Hesse form, we have to impose a restriction on the group orderof the elliptic curve group. If as above q = p is the cardinality of the prime field, Izu showsthat if p ≡ 1 mod 4 then the defining equation of E may be transformed to a Montgomery
representation if and only if 4 | |E(Fq )| ([Izu99]). If, however, p ≡ 3 mod 4, then only if
8 | |E(Fq )| we know that a Montgomery representation of E exists. Thus we propose touse primes p ≡ 1 mod 4 if a Montgomery representation shall be used. Again as above bothgeneration methods seem to be appropriate to find such elliptic curves.

4.3

Point Compression

In this section we address the problem of point compression. We answer the question if thegeneration of special curve parameters decreases significantly the number of bits to represent
a point. We show that the answer actually is ’no’.
In some situations it is desirable to represent a point with as few bits as possible. Such asituation occurs if storage or bandwidth are at a premium. We refer to such a notation as
point compression.
Most of our discussion is independent of the characteristic of the field. Thus let E be an elliptic
curve defined over some finite field Fq . We denote the bitlength of q by n. In the frameworkof elliptic curve cryptography a non-trivial point P is represented in (affine) coordinates by(x, y), where both x and y are elements of Fq . Thus we need at most 2n bits to represent
such a point. However, the coordinates of P satisfy a quadratic equation in y. Thus it is easy
to see how to recover y, once x and some additional bit related to y are given. Hence thetransmission of n + 1 bits is sufficient to uniquely identify P (the methods to compress therepresentation may be found for example in [P1363] or [X9.62]).
The boundary condition in our context is as follows. Let E(Fq ) be a cryptographically strong
elliptic curve group, and let P be a point of order r. Then we have√√q+1−2 q|E(Fq )|
2n−1 + 1 − 2 2nr≥≥≥
> 2n−4 .
4
4
4

(4.3)

Thus n − 3 is a lower bound of the bitlength of r. We therefore need at least n − 3 bits torepresent an elliptic curve point in our context. The saving of at most 4 bits seems to us notto justify the search for a curve with special parameters.
We finally mention a minor improvement. If q = 2n and the order of P is odd, we only needn bits to represent P (see [Ser98], [BSS99]).

4.4 Implementation on Smart Cards

4.4

27

Implementation on Smart Cards

In this closing section we discuss elliptic curve parameters for use in a constraint environment
such as a smart card. There is no general answer to this problem. Nevertheless, we point tosome characteristics of a smart card implementation.
As of today most of the smart cards for cryptographic use come with a cryptographic coprocessor. Thus we only discuss this type of smart cards. The first important point froma performance point of view is the information sharing between the main processor and thecryptographic coprocessor. In general the bandwidth is at a premium. Thus there should be
as few transmissions as possible. For instance, if an elliptic curve over Fp should be used,the developer of such a system could skip the transmission of the elliptic curve parameter aby always setting a = −3. As mentioned in Section 4.2.1 this yields a performance speed up,
too.
In addition, the use of NIST primes as explained in Section 4.1.1 seem to be a good choice.
Again we can decrease the number of bits to be transferred, if only the non-trivial bit positions of the binary expansion of p are exchanged. Furthermore, the implementation of thearithmetic in Fp is very fast in this case.

28

Implementation Issues

Bibliography[AKS02]

M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. available via WWW
from http://www.cse.iitk.ac.in/primality.pdf, August 2002.

[AM93]

A.O.L. Atkin and F. Morain. Elliptic curves and primality proving. Mathematics of Computation, 61:29–67, 1993.

[Bai02a]

H. Baier. Efficient Algorithms for Generating Elliptic Curves over Finite Fields
Suitable for Use in Cryptography. PhD thesis, Darmstadt University of Technology,
2002.

[Bai02b]

H. Baier. How to find Elliptic Curve Groups of Prime Order. Technical Report,
Darmstadt University of Technology, 2002. Technical Report TI-6/02.

[BK98]

R. Balasubramanian and N. Koblitz. The Improbability that an Elliptic
Curve has Subexponential Discrete Log Problem under the Menezes Okamoto Vanstone Algorithm. Journal of Cryptology, 11:141–145, 1998.

[BSS99]I. Blake, G. Seroussi, and N. Smart. Elliptic Curves in Cryptography. Cambridge University Press, 1999.

[CC87]

D.V. Chudnovsky and G.V. Chudnovsky. Sequences of numbers generated
by addition in formal groups and new primality and factorization tests. Adv. in
Appl. Math., 7:385–434, 1987.

[CMO98] H. Cohen, A. Miyaji, and T. Ono. Efficient Elliptic Curve Exponentiation
using mixed coordinates. In Proceedings of ASIACRYPT ’98, LNCS 1514, pages
51–65, Berlin, 1998. Springer-Verlag.
[Coh95]

H. Cohen. A Course in Computational Algebraic Number Theory. SpringerVerlag, 1995.

[EM02]

A. Enge and F. Morain. Comparing Invariants for Class Fields of Imaginary
Quadratic Fields. In Proceedings of ANTS-V, LNCS 2369, pages 252–266, Berlin,
2002. Springer-Verlag.

[FGH00] M. Fouquet, P. Gaudry, and R. Harley. An extension of Satoh’s algorithm
and its implementation. J. Ramanujan Math. Soc., 15:281–318, 2000.
[FGH01] M. Fouquet, P. Gaudry, and R. Harley. Finding Secure Curves with the
Satoh-FGH Algorithm and an Early-Abort Strategy. In Proceedings of Eurocrypt
2001, LNCS 2045, pages 14–29, Berlin, 2001. Springer-Verlag.

30

Bibliography[FIPS186] FIPS186 Digital Signature Standard. Federal Information Processing Standards
Publication 186, 1994.
[FR94]

G. Frey and H.-G. Rück. A remark concerning m-divisibility and the discrete
logarithm problem in the divisor class group of curves. Mathematics of Computation, 62:865–874, 1994.

[GHS02a] S. Galbraith, F. Hess, and N.P. Smart. Extending the GHS Weil Descent
Attack. In Proceedings of Eurocrypt 2002, LNCS 2332, pages 29–44, Berlin, 2002.
Springer-Verlag.
[GHS02b] P. Gaudry, F. Hess, and N.P. Smart. Constructive and Descructive Facets ofWeil Descent on Elliptic Curves. Journal of Cryptology, 15:19–46, 2002.
[GIS01]

Geeignete Kryptoalgorithmen, In Erfüllung der Anforderungen nach §17(1) SigG
vom 16. Mai 2001 in Verbindung mit §17(2) SigV vom 22. Oktober 1997, July
2001. Bundesanzeiger Nr. 158 - Seite 18 562 vom 24. August 2001.

[GLV00]R. Gallant, R. Lambert, and S. Vanstone. Improving the Parallelized Pollard Lambda Search on Anomalous Binary Curves. Mathematics of Computation,
69(232):1699–1705, 2000.

[GLV01]

R. Gallant, R. Lambert, and S. Vanstone. Faster Point Multiplication on
Elliptic Curves with Efficient Endomorphisms. In Proceedings of CRYPTO 2001,
LNCS 2139, pages 190–200, Berlin, 2001. Springer-Verlag.

[Gor98]

D. Gordon. A survey of fast exponentiation methods. Journal of Algorithms,
pages 129–146, 1998.

[Har02]R.
Harley.
Elliptic Curve Point Counting:
Posted at the Number Theory Web, available via
http://listserv.nodak.edu/archives/nmbrthry.html, August 2002.

[Izu99]T. Izu. On the Computation of Elliptic Curve Cryptosystems. In SCIS’99, W4-1-1,
1999.

[Kob92]

N. Koblitz. CM-Curves with Good Cryptographic Properties. In Advances in
Cryptology-CRYPTO ’91, LNCS 576, pages 279–287, 1992.

[LiDIA]

LiDIA. A library for computational number theory. Darmstadt University of Technology. URL: http://www.informatik.tu-darmstadt.de/TI/LiDIA/Welcome.html.

[LL94]

C. Lim and P. Lee. More Flexible Exponentiation with Precomputation. In
Advances in Cryptology - CRYPTO’94, LNCS 839, pages 95–107, Berlin, 1994.
Springer-Verlag.

[LV01]

A. Lenstra and E. Verheul. Selecting Cryptographic Key Sizes. Journal of
Cryptology, 14:255–293, 2001.

[LZ94]

G.-J. Lay and H.G. Zimmer. Constructing elliptic curves with given group order
over large finite fields. In Proceedings of ANTS I, LNCS 877, pages 250–263, 1994.

32003
WWW

bits.
from

Bibliography

31[Mül95]

V. Müller. Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven über endlichen Körpern der Charakteristik größer drei. PhD thesis, Universityof Saarbrücken, 1995.

[Mon85]

P.L. Montgomery. Modular multiplication without trial division. Math. of.
Comp., 44:519–521, 1985.

[Mon87]

P.L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Math. of. Comp., 48:243–264, 1987.

[MOV91] A. Menezes, T. Okamoto, and S. Vanstone. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. In Proceedings of the 23rd Annual ACM
Symposium on the Theory of Computing, pages 80–89, 1991.
[MOV97] A. Menezes, P.v. Oorschot, and S. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.
[NIST]NIST Recommended Elliptic Curves for Federal Government Use. National Institute of Standards and Technology, 1999.

[P1363]

P1363 Standard Specifications for Public Key Cryptography. IEEE, 2000.

[SA98]

T. Satoh and K. Araki. Fermat quotients and the polynomial time discrete
log algorithm for anomalous elliptic curves. Comm. Math. Univ. Sancti Pauli,
47:81–92, 1998.

[Sat99]

T. Satoh. The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field
and its Point Counting. http://www.rimath.saitama-u.ac.jp/lab.en/TkkzSatoh/,1999.

[Sem98]

I. Semaev. Evaluation of discrete logarithms in a group of p-torsion points of anelliptic curve in characteristic p. Mathematics of Computation, 67:353–356, 1998.

[Ser98]G. Seroussi. Compact representation of elliptic curve points over F2n . Technical Report, Hewlett Packard Laboratories Technical Report No. HPL-98-94R1,
September 1998.

[Sma99]N.P. Smart. The Discrete Logarithm Problem on Elliptic Curves of Trace One.
Journal of Cryptology, 12/3:193–196, 1999.

[Sma01]

N.P. Smart. The Hessian form of an elliptic curve. In Proceedings of CHES 2001,
LNCS 2162, pages 118–128, Berlin, 2001. Springer-Verlag.

[Sol97]

J. Solinas. An Improved Algorithm for Arithmetic on a Family of Elliptic Curves.
In Advances in Cryptology - CRYPTO ’97, LNCS 1294, pages 357–371, Berlin,
1997. Springer-Verlag.

[Sol00]J. Solinas. Efficient arithmetic on Koblitz curves. Designs, Codes and Cryptography, 19:195–249, 2000.

[SEC1]

SEC1 Standards for Efficient Cryptography: Elliptic Curve Cryptography. Version
1.0, 2000.

32

Bibliography[vOW99] P.C. van Oorschot and M.J. Wiener. Parallel Collision Search with Cryptanalytic Applications. Journal of Cryptology, 12/1:1–28, 1999.
[X9.62]

X9.62 Public Key Cryptography For The Financial Services Industry: The Elliptic
Curve Digital Signature Algorithm (ECDSA). ANSI, 1998.

[X9.63]

X9.63 Public Key Cryptography For The Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography. ANSI, 2002.

Indexalgorithm
cryptoCurve, 11
getParameters2, 14
getParametersP, 9
getPrime, 9
isPrime, 7
isStrong2, 13
isStrongP, 8
NAF, 25
randomApproach2, 14
randomApproachP, 10
SEA, 9
SFGH, 14

Miller-Rabin test, 7
Montgomery form, 25

basis
normal basis, 21
Gaussian normal basis, 21
polynomial basis, 21
pentanomial polynomial basis, 21
trinomial polynomial basis, 21
bit-complexity, 2scalar multiplication, 19class number, 10
cofactor, 4crossover class number, 12
cryptographically strong, 4
discriminant, see imaginary quadratic discriminant
early-abort-strategy, 9Gaussian normal basis, see basis
group of rational points, 3Hesse form, 25
imaginary quadratic discriminant, 10
imaginary quadratic order, 10
Koblitz curves, 16

NAF, 24
norm, 10normal basis, see basis
order, see imaginary quadratic orderpentanomial, 21
point compression, 26
polynomial basis, see basis
polynomial representation, 21
primality test, 7

trace, 9trinomial, 21
twisted elliptic curves over Fp , 11
twisted elliptic curves over F2n , 15