Abstract. This report discusses the elliptic curve discrete logarithm problem and the known methods to solve it. We consider the implications of these methods for choosing the domain parameters in elliptic curve based cryptographic schemes. We also study s

20S.D.GALBRAITH AND N.P.SMART

One is not constrained to using elliptic curves over F2but can use curves over anyfield of small characteristic(such as F22or F3).These curves are sometimes known as‘Koblitz curves’and sometimes as‘subfield curves’.Nevertheless,the case of curves over F2remains the most important in applications.

More recently the definition of Koblitz curves has been extended by Gallant, Lambert and Vanstone[14]to the case of elliptic curves over primefields F p which have convenient endomorphisms.The speedup for curves over F2can be realised in this case too by using endomorphisms.

We will now discuss Koblitz curves in more detail.We separate the discussion into two parts.First we discuss the more traditional Koblitz curves(those over smallfields,and in particular F2)and second we discuss Koblitz curves over large primefields.

4.1.Koblitz curves in characteristic2.The SEC standard[2]gives20prede-fined curves in characteristic two,a number of which appear in other standards such as ANSI X9.62,WAP WTLS or NIST FIPS186.2.Of these20predefined curves six are of Koblitz form in that they possess a convenient endomorphism which can be used to speed up the group law.

The curves,labelled sect163k1,sect233k1,sect239k1,sect283k1,sect409k1and sect571k1are all anomalous binary curves of the form

Y2+XY=X3+aX2+1

where a∈{0,1}.These curves possess the endomorphism given by the action of the Frobenius map

(x,y)−→(x2,y2).

Using techniques of Solinas[39]one can improve the algorithms for point mul-tiplication considerably,and hence obtain very efficient implementations both in hardware and software.

However,the existence of the Frobenius endomorphism of order n combined with the techniques of Section3.1mean that the curves are not as secure as a general curve over the samefinitefield.However,the effect of this reduction in security is modest.For example with the curve sect163k1one would expect to require

qπ

≈281

2·h

operations to break a general elliptic curve over F2163while the Koblitz curve only requires qπ

≈277

4·163·h

operations.For largerfinitefields the effect of choosing a Koblitz curve is similar. Table3demonstrates this by showing the difference between the security of a general curve and a Koblitz curve for thefield sizes in the above mentioned standard, with the specified cofactor.For the security of general curves in the table we assume the cofactor is two,as this is the most common case for randomly chosen curves.

To summarise the results of this section.Despite being anomalous,Koblitz curves are not susceptible to the anomalous curves attack(since p=2).Despite being over afield of the form F2m,Koblitz curves are not at risk from Weil descent since the extension degree m is prime.Nevertheless,there is a slight loss of security from the use of equivalence classes in the parallel Pollard methods.