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 PROBLEM9 which means that the size of thefield has a strong influence on the difficulty of the ECDLP.

The parallel Pollard method with distinguished points is the method of choice to solve the generic ECDLP.In1997Certicom announced a series of elliptic curve challenges,and the ones which have been successfully solved have all been done using the parallel Pollard method with distinguished points.Currently the record stands at an elliptic curve over a97bitfinitefield for a general curve and a Koblitz curve over a109bit characteristic2finitefield.We will see in Section3.1why the parallel Pollard method can be made more efficient for Koblitz curves.

The amount of computing time needed to solve the97bit or109bit ECDLP problems in the challenges is about comparable with,or even greater than,the computing time needed to factor a512bit RSA modulus.

To get some idea of the size of resources deployed in these challenges,one typ-ically would use m=9500machines and taking the proportion of distinguished points at about1/232,i.e.taking t=32.Hence,for the97bit challenge we would expect to need storage of around116159points.The elapsed time needed tofind the solution would be be on average equivalent to the time needed to perform

235

group operations.Hence,if each group operation could be performed in one tenth of a micro second,which is actually quite slow,one would expect an average elapsed time of60days.Assuming that is all9500machines operated on this problem for that length of time.

The MIPS estimates in Tables1and2for the ECDLP and the FACTORING problem are taken from the paper[23]and allow one to compare comparable key sizes for ECC and RSA keys.A similar comparison is given in[24]where similar conclusions are reached

Table 1.MIPS years to solve a generic ECDLP using parallel

Pollard methods

q πq/2MIPS Years

1602808.5×1011

1862937.0×1015

23421171.2×1023

35421771.3×1041

42622139.2×1051

Table2.MIPS years to factor an RSA modulus using NFS

RSA Size MIPS Years

5123×104

7682×108

10243×1011

12801×1014

15363×1016

20483×1020