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 5

Now P is an element of order p e −t so to obtain an element of order p ,and hence a discrete logarithm problem in C p we need to multiply the above equation by s =p e −t −1.So setting

Q =[s ]Q and P =[s ]P

we obtain the discrete logarithm problem in C p given by

Q =[λt ]P .

So assuming we can solve discrete logarithms in C p we can find λt and so find x .

Since the intermediate steps in the Pohlig-Hellman algorithm are quite simple,the difficulty of solving a general discrete logarithm problem will be dominated by the time required to solve the discrete logarithm problem in the cyclic subgroups of prime order.

For elliptic curve cryptography it follows that the security depends on the largest prime factor of the order of the group,say l .For efficiency we prefer that the subgroup contain a large proportion of all the points on the curve.Implication 1.For elliptic curve cryptography we select an elliptic curve such that

#E (K )=N =h ·l

where l is a large prime and h is very ually one chooses h =1,2or 4.

2.3.Baby-Step/Giant-Step.In our above discussion of the Pohlig-Hellman al-gorithm we assumed we had an algorithm to solve the discrete logarithm problem in cyclic groups of prime order.We shall now describe a general method of solving such problems which is more efficient than exhaustive search.This method is due to Shanks and is called the Baby-Step/Giant-Step method.Once again this is a generic method which applies to any cyclic finite abelian group.

Again we fix notation as follows.We have a public cyclic subgroup G = P of some elliptic curve group E (K ),which we can now assume to have prime order l .We are also given a point Q ∈G and are asked to find the value of λmodulo l such that

Q =[λ]P.

We assume there is some fixed encoding of the elements of G ,so in particular it is easy to store,sort and search a list of elements of G .

The principle behind the Baby-Step/Giant-Step method is a standard divide and conquer approach found in many areas of computer science.We first write λ=λ0+λ1 √l .

Since λ≤l we have that 0≤λ0,λ1< √l .

We now compute the list of Baby-Steps P i =[i ]P for 0≤i < √l .

The pairs

(P i ,i )

are stored in a table so that one can easily search for items indexed by the first entry in the pair.This can be accomplished by sorting the table on the first entry