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

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM 21

Table 3.Reduction in Security for Koblitz in Characteristic Two Curve

Field Size Cofactor General Curve Koblitz Curve Security Security sect163k1

21632281277sect233k1

2233421162111sect239k1

2239421192114sect283k1

2283421412136sect409k1

2409422042198sect571k12571422852279

4.2.Koblitz curves in characteristic p.Gallant,Lambert and Vanstone [14]point out in characteristic p one can also use endomorphisms to speed up the point multiplication,as long as the curve is chosen with the correct properties.In [2]there are 15predefined curves over fields of large prime characteristic.Of these four are not chosen at random,but are chosen to have efficiently computable endomorphisms.The curve names of these four curves are secp160k1,secp192k1,secp224k1,secp256k1.

These curves all have the form

Y 2=X 3+b

and possess the endomorphism

φ:(x,y )−→(βx,y ),

where βis a cube root of one in F p .The characteristic p of the base field needs to be chosen so that p ≡1(mod 3),unlike the other curves in the standard the field of definition of these curves is not chosen to be a generalised Mersenne prime.

Note that the performance improvement with using these curves is not as marked as the performance improvement one obtains by using anomalous binary curves.But the corresponding reduction in security is also not as marked,since the endo-morphism is of order 3.

The endomorphism ring of these curves is contained in the ring of integers of the quadratic field Q (√−3).We discuss whether this is could pose a security threat in Section 5.

The Pollard methods utilising equivalence classes as discussed in Sections 2.4and

3.1apply in this case.The equivalence classes have size 6.Table 4demonstrates this by showing the difference between the security of a general curve and a Koblitz curve for the field sizes in the above mentioned standard.Unlike the case of characteristic two,in the standards the Koblitz curves for large prime characteristic always have minimal cofactor,i.e.h =1.

Implication 9.The only known security reduction for Koblitz curves,compared with random curves,is the use of equivalence classes to speed up the Pollard methods.

5.Possible special attacks

In this section we indicate some mathematical structures which are present with elliptic curves but which have not yielded attacks on the ECDLP.