EVALUATION REPORT FOR CRYPTREC SECURITY LEVEL OF CRYPTOGRAPH(4)

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

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

To explain the Pohlig-Hellman algorithm,suppose we have afinite cyclic abelian group G whose order is given by

N=#G=

t i=1

p e i

i

.

The case of non-cyclic groups may be handled analogously.We assume that the number N can be factored(this assumption is valid for the ECDLP since group orders for elliptic curve cryptography are rather small compared to current factoring records).

Now suppose we are given two points P,Q∈G such that there exists an integer λsuch that

Q=[λ]P

Our aim is tofindλbyfirstfinding it modulo p e i

i and then using the Chinese

Remainder Theorem to recover it modulo N.

From basic group theory we know that there is a group isomorphism

φ:G→C p e1

1×···×C p e t

t

,

where C p e is a cyclic subgroup of G of prime power order p e.The projection ofφto the component C p e is given by

φp: G→C p e

R−→[N/p e]R

The mapφp is a group homomorphism so if we have Q=[λ]P in P then we will haveφp(Q)=[λ]φp(P)in C p e.But the discrete logarithm in C p e would only be determined modulo p e.Therefore,solving the discrete logarithm problem in C p e determinesλmodulo p e.Doing this for all primes p dividing N would allow us to solve forλusing the Chinese Remainder Theorem.

The only problem is that we have not shown how to solve the discrete logarithm problem in C p e.We shall now show how this is done,by reducing to solving e discrete logarithm problems in the group C p.

Suppose P,Q∈C p e and that there is anλsuch that

Q=[λ]P.

Clearlyλis only defined modulo p e and we can write

λ=λ0+λ1p+···+λe−1p e−1.

Wefindλ0,λ1,...in turn,using the following inductive procedure.Suppose we knowλ ,the value ofλmodulo p t,i.e.

λ =λ0+···+λt−1p t−1.

We now wish to determineλt and so computeλmodulo p t+1.We write

λ=λ +p tλ ,

and we have that

Q=[λ ]P+[λ ] [p t]P .

So if we set

Q =Q−[λ ]P and P =[p t]P,

then

Q =[λ ]P .