EVALUATION REPORT FOR CRYPTREC SECURITY LEVEL OF CRYPTOGRAPHY – ECDLP MATHEMATICAL PROBLEM

更新时间：2023-07-17 19:39:01 阅读量：实用文档文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

evaluation推荐度：
相关推荐

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

EV ALUATION REPORT FOR CRYPTREC:

SECURITY LEVEL OF CRYPTOGRAPHY–ECDLP

MATHEMATICAL PROBLEM

S.D.GALBRAITH AND N.P.SMART

Abstract.This report discusses the elliptic curve discrete logarithm prob-

lem and the known methods to solve it.We consider the implications of these

methods for choosing the domain parameters in elliptic curve based crypto-

graphic schemes.We also study special classes of elliptic curves.In particular,

we discuss the security of Koblitz curves.

Contents

1.Introduction2

2.Known generic attacks3 2.1.Exhaustive search3 2.2.Pohlig-Hellman3 2.

3.Baby-Step/Giant-Step5 2.

4.Pollard methods6

2.5.Practical considerations8

3.Known special attacks10 3.1.Equivalence classes10 3.2.Weil pairing and Tate pairing attacks13 3.3.Determining whether the ECDLP has a solution14 3.

4.The anomalous curves attack15 3.

5.Weil descent16

3.6.Special?nite?elds19

4.Koblitz curves versus general curves19 4.1.Koblitz curves in characteristic220

4.2.Koblitz curves in characteristic p21

5.Possible special attacks21 5.1.Endomorphisms and complex multiplication22 5.2.Imagined attacks23 5.3.Koblitz curves revisited23

5.4.Trace three curves23

6.Conclusion23 References24

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

1.Introduction

The Elliptic Curve Discrete Logarithm Problem(ECDLP)is the foundation of a number of cryptographic protocols,for example EC-DSA,EC-DH,EC-MQV, EC-IES etc.In this report we discuss the current state of knowledge about the di?culty of the ECDLP.Before doing so we set up some notation which will be used throughout.

Let K=F q denote a?nite?eld.In practical systems one always either chooses q to be a large prime or one chooses q to be a power of two,these correspond to the cases of odd and even characteristic respectively.An elliptic curve over K is usually given in one of two forms

E:Y2=X3+aX+b

in the odd case,or

E:Y2+XY=X3+aX2+b

in the even case.In both cases we assume a,b∈K are chosen to make the curve non-singular.

The set of points on an elliptic curve E over K,including the point at in?nity which we write as O E,forms a?nite abelian group denoted by E(K).We write the group operation on points of E(K)additively.For positive integers n we write

[n]P=P+P+···+P

n times

We sometimes also write this as nP.This is extended to all integers n∈Z using the inverse?P of a point.

We write the order of this group as

#E(K)=N.

We will always assume(see Section2.2for the reason)that N=h·l where l is a large prime number and h is small and called the cofactor.

Let P=(x,y)be a point on an elliptic curve E over K.We write

P ={[n]P:n∈Z}.

This is the subgroup of E(K)generated by the point P.The main problem which motivates elliptic curve cryptography is the following.

Elliptic Curve Discrete Logarithm Problem(ECDLP):Given P,Q∈E(K)?nd the value ofλ,if it exists,such that

Q=[λ]P.

For suitably chosen?elds,curves and points this problem is believed to be com-putationally infeasible to solve.

Most cryptographic protocols in ECC actually rely for their security on weaker problems such as the elliptic curve Di?e-Hellman problem(EC-DHP)or the elliptic curve Decision Di?e-Hellman problem(EC-DDH).The cryptographic technique which we have been asked to study is the ECDLP,and so it will be the main focus of the present report.In order to accurately determine the security of cryptographic systems it is essential to also study the EC-DHP and EC-DDH.We recommend that the CRYPTREC organisation make further studies on these problems.In most

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM3

instances it is conjectured that all three problems are polynomial time equivalent. One should however be aware that there are some elliptic curves for which there is strong evidence for a separation between these problems(see Joux and Nguyen [20]).

There is a certain family of curves which occurs quite frequently in elliptic curve cryptography and they are called the‘Koblitz curves’.Originally this term was used for curves de?ned over a sub?eld k of K,where we consider the group of points over the larger?eld for cryptographic purposes.The reason for considering these curves was that they possess an endomorphism structure which allows an e?cient implementation of the various protocols.Nowadays,especially in standards such as SEC[1][2],the name‘Koblitz curve’is used for any elliptic curve which possesses a special endomorphism structure which enables e?cient implementation.

There are two common classes of Koblitz curves:

?The classical case of curves over F2(sometimes called anomalous binary curves or ABC curves)which are given by

Y2+XY=X3+aX2+1

where a∈{0,1}.These curves are de?ned over F2but we work in the group of points de?ned over the?eld F2n.

?The more recent case of Koblitz curves over a large prime?eld which have

a suitable endomorphism.

Further details of these cases are given in Section4.

2.Known generic attacks

In this section we consider a number of generic attacks against the ECDLP.The name‘generic’refers to the fact that such attacks will apply in any group and not just an elliptic curve group.What makes elliptic curves particularly attractive is that for well chosen parameter sets the following generic attacks are the best possible with current knowledge.

We always assume we have a discrete logarithm problem given by

Q=[λ]P,

where P and Q are given and the goal is to?ndλ.

2.1.Exhaustive search.This is the most elementary attack.One simply com-putes

R=[µ]P

forµ=1,2,3,...,and checks whether R=Q.When equality is reached we concludeµ=λ.

This algorithm requires O(1)storage,but requires O(N)time in both the worst and average case.

2.2.Pohlig-Hellman.The discrete logarithm problem in a group G(for instance, G=E(K))is only as hard as the discrete logarithm problem in the largest subgroup of prime order in G.This observation is due to Pohlig and Hellman[31],and their method works in an arbitrary?nite abelian group.

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

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

N=#G=

t i=1

p e 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 to?ndλby?rst?nding 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

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 de?ned modulo p e and we can write

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

We?ndλ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 .

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 ?nd λt and so ?nd x .

Since the intermediate steps in the Pohlig-Hellman algorithm are quite simple,the di?culty 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 e?ciency 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 e?cient 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 ?nite abelian group.

Again we ?x 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 ?nd the value of λmodulo l such that

Q =[λ]P.

We assume there is some ?xed 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 ?rst 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 ?rst entry in the pair.This can be accomplished by sorting the table on the ?rst entry

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

or,more e?ciently,by the use of hash-tables.To compute and store the Baby-Steps clearly requires O ( √l )

time,and a similar amount of storage.We now compute the Giant-Steps.Let P =[ √ ]P and compute Q j =Q ?[j ]P for 0≤j < √ .

We then try to ?nd a match in the table of Baby-Steps,i.e.we try to ?nd a value P i such that P i =Q j .If such a match occurs we have

λ0=i and λ1=j

since,in that case,

[i ]P =Q ?[j √]P,

and so [i +j √l ]P =Q.

Notice that the time to compute the Giant-Steps is at most O ( √ ).

Hence,the overall time and space complexity of the Baby-Step/Giant-Step method is O (√l ).

This complexity is for both the worst and average cases of running the algorithm.

It is known (see Shoup [36])that the Baby-Step/Giant-Step method is the fastest possible method for solving the discrete logarithm problem in a ‘black box group’.Black box groups are a theoretical tool which allow the analysis of algorithms in an idealised setting.A black box group is a group modelled in such a way that the representations of ?eld elements provides no structure.Of course in any particular group there may be a special purpose algorithm which works faster,but in general the Baby-Step/Giant-Step method is the best possible.

In conclusion,combining the Baby-Step/Giant-Step method with the Pohlig-Hellman algorithm,if we wish a discrete logarithm problem in a group G to be as di?cult as a work e?ort of 280operations,then we need the group G to have a prime order subgroup of order at least 2160.Implication 2.This means that for elliptic curve cryptography we select a curve such that

#E (K )=N =h ·l

where

l >2160.

2.4.Pollard methods.The trouble with the Baby-Step/Giant-Step method is that,although its run time is bounded by O (√l ),it also requires O (√l )space.This space requirement makes the algorithm infeasible in practice.Hence,it is desirable to reduce the large space requirement while still obtaining a time complexity of O (√Pollard achieved this [32],but the method only has an expected running time rather than an absolute bound on the running time.The resulting algorithm is therefore of the “Las Vegas”type.

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM 7

The methods for reducing the space complexity all make use of random walks,and a number of techniques exist in the literature almost all of which are due to Pollard (such as the rho and lambda and kangaroo methods).

These algorithms were all developed for serial computers.In real life when one uses random walk based techniques to solve discrete logarithm problems one uses a parallel version due to van Oorschot and Wiener [30].The parallel methods are easily distributed over the internet.We now describe the parallel Pollard method as it is used in practice.

Suppose we are given the discrete logarithm problem

Q =[λ]P

in a subgroup G = P of an elliptic curve.The order of P is assumed to be a prime l .We ?rst construct an easily computable function

h :G →{1,...,k },

where k is usually around 16.For example,such a function can be obtained by selecting a suitable window of 4bits in the binary representation of elements of G ,and mapping to an integer obtained from these bits in the natural way.

Then we de?ne a set of “multipliers”M i ,these are produced by generating random integers a i ,b i ∈[0,...,l ?1]and then setting

M i =[a i ]P +[b i ]Q.

(In fact,when working in a cyclic group such as P it is possible to set the b i =0as long as the t 0below are always taken to be distinct).

To start a random walk we pick random s 0,t 0∈[0,...,l ?1]and compute

P 0=[s 0]P +[t 0]Q,

the random walk is then de?ned on the triples (P i ,s i ,t i )where

P i +1

=P i +M h (P i ),s i +1

=s i +a h (P i )(mod l ),t i +1=t i +b h (P i )(mod l ).

Hence,for every P i we record the values of s i and t i such that

P i =[s i ]P +[t i ]Q.

Suppose we have m processors,each processor starts a from a di?erent starting position using the same process to determine the next element in the deterministic ‘random’walk.When two processors,or even the same processor,meet an element of the group that has been seen before then we obtain an equation

[s i ]P +[t i ]Q =[s j ]P +[t j ]Q,

from which we can solve for the discrete logarithm λwith high probability (the algorithm succeeds unless t i ≡t j (mod l )).It can be shown [30]that we expect that after roughly πl/2/m iterations of these parallel walks that we will ?nd a collision and so solve the discrete logarithm problem.Hence the method requires O (√l/m )computation time.

However,as described above,each processor needs to return every element in its computed random walk to a central server who then stores all the computed elements.This is highly ine?cient as the storage requirements will be very large,namely O (√l ).We can reduce the storage requirements to any value as follows.

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

We de?ne a function d on the group

d :G →{0,1}

such that d (g )=1around 1/2t of the time.For example,the function d is often de?ned by returning d (g )=1if a certain subset of t of the bits representing a group element R are set to zero.The elements in G for which d (g )=1will be called distinguished .

Now it is only the distinguished group elements which are transmitted back to the central server.In other words,only 1in 2t points in the random walk are sent to the server.This means that one expects the random walks to need to continue another 2t steps in the worst case before a collision occurs between two random walks.Hence,the computing time now becomes O √+2

t ?1 in the average case,whilst the storage becomes O √l/2t .

Both these complexity estimates are for the average case running time and storage requirements.Since the algorithms are Las Vegas in nature there is the possibil-ity that they never terminate (although this is highly unlikely).In addition the distribution of the running time can have quite a large variance.

One might be tempted to balance the above two equations by choosing 2

t ?1≈ πl/2/m so that the time requirement is O (√l/m )while the space requirement is O (m ).In practice this is not what is done,since any single processor probably

cannot execute 2t =O (√l/m )operations.Instead,the space requirement is chosen

in such a way that the central server has enough memory,and that single processors can produce distinguished points at an convenient rate (for instance,one or two distinguished points each day).

It must be remembered that all the distinguished points are sent to a central server where they are stored.This leads to practical memory and network consid-erations which are an obstacle to performing this method in very large groups.

Finally,we note that a parallel random walk attack similar to the one mentioned above is known for ?nding collisions in cryptographic hash functions.This means that elliptic curve cryptosystems should have parameter sizes chosen according to the same security criteria as hash function output sizes.Implication 3.When choosing elliptic curve parameter sizes it must be remem-bered that the work e?ort required is essentially reduced by a linear factor in terms of the number of processors available to an attacker.

Elliptic curve parameter sizes should be chosen to be at least as large as recom-mended hash function output sizes.

2.5.Practical considerations.As already remarked it is usual to choose

l ≈N,

and general theory implies that N ≈q .So in most ?elded elliptic curve cryptosys-tems we have

l ≈q

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM9 which means that the size of the?eld has a strong in?uence on the di?culty 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 a97bit?nite?eld for a general curve and a Koblitz curve over a109bit characteristic2?nite?eld.We will see in Section3.1why the parallel Pollard method can be made more e?cient 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 to?nd 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

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

3.Known special attacks

We now consider attacks which apply to certain special classes of elliptic curves.

3.1.Equivalence classes.The use of equivalence classes to accelerate the Pollard methods was?rst noticed by Gallant,Lambert and Vanstone[13]and Wiener and Zuccherato[43].

The principle behind the Pollard methods is that two random walks on a set of size l are likely to have a collision after approximately πl/2steps.Hence,if the size of the set can be reduced then the time required to?nd collisions is also reduced.The principle behind the equivalence classes method is that,if there is a convenient equivalence relation on the set,then one can consider a random walk on the set of equivalence classes rather than the whole set.The only di?culty is that it must be easy to construct a random walk which is well-de?ned on equivalence classes.

A basic example which works for all elliptic curves is the following,which is based on inverses of a point.If P=(x,y)then?P is either(x,?y)in the odd case or(x,y+x)in the even case.In both cases it is computationally trivial to pass from P to?P(this is quite unlike the case of?nite?elds,where computing g?1from g is a complicated arithmetic operation).De?ne the equivalence relation P～Q if Q=±P and consider the set of equivalence classes S=E(K)/～.Note that#S≈#E(K)/2.

We want to de?ne a random walk on the set S as we did in Section2.4but we have

to take care of the following:when we have P i being mapped to P i+1=P i+M h(P

i )

we must also have?P i mapped to±P i+1.This means that we must be very careful in evaluating the function h which determines the choice of multiplier.A way to de?ne h on equivalence classes is to impose an ordering on the?nite?eld elements.Then,for a given point P=(x,y)one may compute?P=(x,y )and then determine whether y≤y or not.Finally one de?nes the function h as before, but in terms of the uniquely speci?ed point whose y-coordinate has the minimal value.

Now that h is uniquely de?ned on equivalence classes it remains to construct the random walk on equivalence classes.One way to do this is to de?ne P i+1=

P i+M h(P

i )

if y is the minimal value,and to de?ne P i+1=P i?M h(P

)

if y is

the minimum value.The corresponding values of s i and t i are updated as s i+1=

s i±a h(P

i )

accordingly.Note that if P i=(x,y)is the point with minimal y-

coordinate and?P i=(x,y )is the other point,then?P i+1=?(P i+M h(P

i )

(?P i)?M h(?P

i )

which shows that the map is well-de?ned on equivalence classes.

Note that,in the notation of Section2.4,we have P i=[s i]P+[t i]Q and?P i=

[?s i]P+[?t i]Q.

Finally,we must consider the distinguished points.We can use the same def-

inition as before for distinguished points of E(K)and now de?ne an equivalence

{±P}of S to be distinguished if either P or?P is distinguished.The central server stores distinguished points and the values s i,t i.When two processors?nd

the same distinguished equivalence class then we have

[s i]P+[t i]Q=±([s j]P+[t j]Q).

The discrete logarithm problem can then be solved with high probability.

This trick of using the equivalence classes{±P}can be applied to all elliptic

curves.The way to abstract this method is to think of the process±as being an

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM11 easily computed endomorphism of the elliptic curve.Therefore,whenever we have an easily computed endomorphism of a curve then we are able to perform a similar method to speed up the Pollard methods.We now give further examples.

Consider the case of an elliptic curve E de?ned over F2but considered as a group over an extension?eld F2m.In this case there is the Frobenius endomorphism

π:(x,y)→(x2,y2)

on the curve E.On points P=(x,y)∈E(F2m)we haveπm(P)=(x2m,y2m)=P. In fact,there is an integerλsuch thatπ(P)=[λ]P for every point P=(x,y)∈E(F2m).Note that computingπ(P)from its de?nition as the Frobenius map is much faster than computing[λ]P using elliptic curve point multiplication algorithms,and this is the key to the speed-ups using Frobenius expansions.

We can de?ne an equivalence relation P～Q if P=±πn(Q)for some n.We want to construct a random walk on the set of equivalence classes S=E(F2m)/～.

Given a point P i=[s i]P+[t i]Q we must obtain a new point in the random walk.We need a function h which maps all points in the same equivalence class to a number in{1,...,16}or so.This is done by searching through the equivalence class to?nd a point which has a certain property(e.g.,the y-coordinated is minimal subject to an ordering condition).Once such a function h is provided there are two ways to proceed.

The?rst approach makes use of the fact that we found a unique representative of the equivalence class while computing h.If the input point is P i=[s i]P+[t i]Q and if the unique representative is P i=(?1)jπk(P i)then we obtain the corresponding s i and t i via

s i=(?1)jλk s i(mod l)and t i=(?1)jλk t i(mod l).

One can then de?ne a random walk using multipliers as before,and compute the s i+1and t i+1accordingly.

Another approach is to use a“next step”function which is well-de?ned on equiv-alence classes(instead of using?xed multipliers M i).Such a process(which is used in[13])is to de?ne the walks as

P i+1=P i+πh(P i)(P i)

so that s i+1=(1+λh(P i)s i)etc.

Either method can be used.In both cases we are using equivalence classes of size2m and so the expected running time of the algorithm is improved from approximately πl/2steps to approximately πl/(4m)steps.

The Frobenius endomorphism is particularly useful but it only occurs for elliptic curves de?ned over sub?elds.However,even with elliptic curves de?ned over prime ?elds there are sometimes endomorphisms available.An example of this occurs with the elliptic curve

E:y2=x3+A.

This elliptic curve has j-invariant j(E)=1728and it has the endomorphism

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

whereβ3=1.As with the±and Frobenius maps,this is actually an automorphism (in other words,it has no kernel).Also,it is clear that this map has order three.

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

Hence we can obtain an equivalence relation as P～Q if P=±φj(Q)for some j.The equivalence classes have size6.All the techniques developed above can be applied in this case and the algorithm runs faster by a factor of

√Similarly,the elliptic curve

E:y2=x3+x

(which has j-invariant j(E)=0)has the automorphism

(x,y)?→(?x,iy)

of order4,where i2=?1.This can also be used to speed up the Pollard methods by a factor of2.

With all of these methods there is a risk of getting trapped in small cycles.In practice these are easily eliminated and we refer to[13,43]for details.

The computational time of the equivalence classes method is the following:If the equivalence classes have size m and the group is of size l then the expected running time of the method is

c πl/2m

where the constant c depends on the cost of computing a?xed representative for each equivalence class.Of course,from the point of view of computational complex-ity,the constant c is O(m)and so the equivalence classes method is asymptotically slower!But in practice it gives a very signi?cant improvement to the running time, as the constant c is rather small.

We now discuss how this method e?ects the choice of parameters for elliptic curve cryptosystems.Suppose we want to develop a cryptosystem which requires a work e?ort(for a single processor)of280to be broken.Then we could take an elliptic curve over a?nite?eld which has a subgroup of prime order l where l>2160.Now suppose we would like to take advantage of the e?ciency bene?ts enabled by the Frobenius endomorphism,and so we take an elliptic curve E over F2and consider the group E(F2m).One might expect that taking m=163gives the desired level of security.In fact,with m=163one obtains an elliptic curve with a subgroup of order l<2163(there is always some co-factor).The work e?ort to solve the ECDLP on such a curve using the Pollard method with equivalence classes is at most

c πl/2m<c π2163/(2·2·163)≤c281/10.2<c278.

In fact,to obtain280security it is necessary to take the extension degree m to be at least168.

Every elliptic curve over F q has some non-trivial endomorphisms.So why can’t they be used to improve the Pollard methods?The reason why they can’t be used is that it is not usually e?cient to?nd a canonical representative of an equivalence class.For instance,consider an elliptic curve E(F q)with l points and consider an integer n which is coprime to l.Inspired by the above methods we might impose the equivalence relation on E(F q)that P～Q if and only if P=±[n]j Q for some j.The

?rst observation is that the powers n j may generate a large subgroup of Z?

l and so

the equivalence classes may be very large.More importantly,to de?ne the mapping h on equivalence classes it is necessary to have some canonical representative.The task of searching through the equivalence class is very expensive since each step is an elliptic curve point multiplication.In the notation above,the“constant”c is a signi?cant multiple of m and so the complexity is not reduced.In general,the equivalence classes method is a slower algorithm than the usual Pollard method.

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM13 Implication4.Koblitz curves are slightly less secure then random curves over the same?eld.

In particular,Koblitz curves over F2163only require a work e?ort of approximately 278to break the ECDLP,rather than approximately281.

3.2.Weil pairing and Tate pairing attacks.Menezes,Okamoto and Vanstone [27]were the?rst to show that the ECDLP may be transformed into a discrete logarithm problem in a?nite?eld.Their method used the Weil pairing.This method was generalised by Frey and R¨u ck[9]using the Tate pairing.We recall the Frey-R¨u ck attack here.

Let K=F q and let P and Q be points in E(K)of order l.Suppose that l is coprime to q(see Section3.4for the case where l|q).

Let k be a positive integer such that the?eld F q k contains the l th roots of unity (in other words,l|(q k?1)and k is the order of q in Z?l).Let G=E(F q k)and write G[l]for the subgroup of points of order l.Write lG={[l]P:P∈G}and write

G/lG for the quotient group.Similarly,write(F?

q k )l={αl:α∈F?

q k

}and write

F?q k /(F?

q k

)l for the quotient group.The groups G[l],G/lG and F?

q k

/(F?

q k

)l all have

exponent l(i.e.,they are a product of cyclic groups of order l).

The Tate pairing is a mapping

(1) ·,· :G[l]×G/lG→F?

q k /(F?

q k

)l.

The Tate pairing satis?es the following properties[9]:

(1)(Well-de?ned) 0,Q ∈(F?

q k )l for all Q∈G and P,Q ∈(F?

q k

)l for all

P∈G[l]and all Q∈lG.

(2)(Non-degeneracy)For each point P∈G[l]?{0}there is some point Q∈G

such that P,Q ∈(F?

q k )l.

(3)(Bilinearity)For any integer n, [n]P,Q ≡ P,[n]Q ≡ P,Q n modulo l th

powers in F?

q k

There are more properties,but these are the ones which are used for the attack.

The Weil pairing is a similar function,but in general there is no relationship between the Tate pairing and the Weil pairing,as they are de?ned on di?erent sets.However,when E is an elliptic curve such that l2 #E(F q k)and P,Q are independent points in E(F q k)[l]then we have that the Weil pairing is

e l(P,Q)= P,Q / Q,P .

A consequence of the non-degeneracy property of the Weil pairing is that the Tate pairing is not symmetric.The Weil pairing requires working over the?eld F q(E[l]) generated by the coordinates of all the l-division points.In general,one would expect the Weil pairing to require a larger?eld than that used for the Tate pairing. One observation is that for elliptic curves these?elds are usually the same. Theorem1.(Koblitz)Let E be an elliptic curve over F q and let l be a prime dividing#E(F q).Suppose that l|(q?1).The E[l]?E(F q k)if and only if l|(q k?1).

The Tate pairing may be computed using the following process:Since[l]P=0 there is some function f on the curve E such that the divisor of the function f, which is denoted(f),is equal to l(P)?l(O E).Then P,Q =f(Q )where Q is a divisor in the same class as Q such that the support of Q is disjoint with the support of(f).This computation is easily and e?ciently implemented in practice by using

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

the double-and-add algorithm and evaluating all the intermediate functions at Q (see [9],[10]for details).

The value f (Q )lies in F q k and is only determined up to a multiple of an l th power.By raising it to the power (q k ?1)/l we obtain a precise l th root of unity.One subtlety when implementing the Tate pairing is ?nding a divisor class Q with support disjoint from the partial terms in the addition chain for lP .In the elliptic curve case this is done by taking Q =(Q +S )?(S )where Q is the target point and where S is an arbitrary point (not necessarily of order l ).

We now recall how the Tate pairing is used to attack the ECDLP.The method proceeds as follows:

(1)Choose random points R ∈E (F q k )until P,R ∈(F ?q k )l .

(2)Compute ζ1= P,R ,ζ2= Q,R ∈F ?q k .

(3)Map the ζi to l th roots of unity (by raising to the power (q k ?1)/l ).This step is actually optional since the linear algebra in the index calculus

method should be performed modulo l .

(4)Solve the discrete logarithm problem ζ2=ζλ1in the subgroup of order l of

the ?nite ?eld F ?q k using an index calculus method.

Note that the index calculus algorithms for solving the discrete logarithm prob-

lem in F ?q k have subexponential complexity in terms of the ?eld size q k (their per-

formance is comparable with integer factorisation algorithms).Since the original problem is in a group of size q it is necessary that the subexponential complexity in terms of q k be smaller than the complexity O (√q )of the Pollard methods.Hence,this strategy is only practical when k is relatively small.

It is known that supersingular curves are vulnerable to the Frey-R¨u ck attack (since the value k is always less than or equal to 6).There are also non-supersingular curves which are vulnerable to this attack (e.g.,curves of trace two over F q ).How-ever,if one chooses non-supersingular curves at random then the probability of ?nding a curve which is vulnerable to the Frey-R¨u ck attack is negligible (more precisely,the probability is O (1/√q )).Even more is true (as was shown by Bal-asubramanian and Koblitz [5]),if one chooses non-supersingular elliptic curves at random so that the number of points is a prime ,then the probability of ?nding a curve which is vulnerable to the Frey-R¨u ck attack is incredibly small (much smaller than 1/√q ).Implication 5.One should choose a curve such that

l |q k ?1

for all “small”values of k ,e.g.,k ≤30.

This test will eliminate all supersingular curves and curves of trace two,plus a few others.

We emphasise that this test is trivial to perform and that the probability of a random non-supersingular curve failing this test is negligible.

3.3.Determining whether the ECDLP has a solution.The de?nition of the ECDLP often includes the task of deciding whether Q lies in the subgroup generated by P or not.

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM 15

In elliptic curve systems the point P usually has prime order l and the order N of the group E (K )is known to all users.

If N =l (i.e.,the subgroup generated by P is the full set of points on the curve)then it is su?cient simply to test whether the point Q lies on the curve (i.e.,whether it satis?es the curve equation).If so,then Q ∈ P .

More generally there is some non-trivial cofactor h =N/l .Usually l 2does not divide N (and this can be checked by all users of the system).This means that there is a unique subgroup of E (K )of order l and it is the subgroup generated by P .Hence,if Q has order l then Q must lie in P and the ECDLP does have some solution λ.Hence,the simplest test is to simply check whether [l ]Q =O E .

If the subgroup of points of order l in E (K )is not cyclic then l 2|N and the problem of checking whether the ECDLP has a solution is more di?cult.Of course,this case usually does not arise in cryptography since,in that case,l ≤√N which means the system has poor e?ciency.Nevertheless,the Weil pairing may be used to determine whether Q ∈ P or not (no ?eld extension is necessary in this case,since the theory implies that l |(q ?1)).Brie?y,if the pairing of P and Q is one then Q ∈ P while if the pairing is not one then Q ∈ P and so the ECDLP does not have a solution.Implication 6.Deciding whether the ECDLP has a solution or not is rather easy in practice.

3.4.The anomalous curves attack.An elliptic curve E de?ned over a prime ?eld F p is said to be anomalous if it has exactly p points.

In 1997several researchers independently announced related methods to reduce the discrete logarithm problem on an anomalous elliptic curve E/F p to the discrete logarithm problem in the additive group Z /p Z of the integers modulo p .Nigel Smart [40]posted an announcement on the internet brie?y describing a method to solve this problem.At the same time a preprint appeared by Satoh and Araki [4],which used identical methods.It then became known that Semaev [35]had already submitted a paper on this topic,and that R¨u ck [33]had generalised this method to deal with Abelian varieties.In this section we will discuss the method of Semaev and R¨u ck,restricted to the case of elliptic curves.This method is computationally more e?cient than the methods proposed by Smart and Satoh–Araki.The papers [4],

[40]give a very readable description of the alternative (p -adic logarithm)method.The paper by Voloch [42]puts the method into a more theoretical framework which demonstrates the analogy between these methods and the Tate pairing.

We note that anomalous curves E/F p are very rare.There is approximately 1/(4√p )chance of a random curve being anomalous.Also,this phenomenon has no impact for the case of elliptic curves over ?elds of small characteristic.

Suppose E/F p is an elliptic curve such that #E (F p )=p .In this section we will describe the mapping

(2)E [p ]?→Z /p Z

which is the key element of the attack on anomalous elliptic curves.

We will describe the map (2)in two stages.

The ?rst stage is a mapping described by Serre from E [p ]into ?1(E )(the space of holomorphic di?erentials on E ).Given P ∈E [p ]we know that there is some

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

function f which has divisor(f)=p(P)?p(O E).De?ne?(P)to be the di?erential

ωP:=1d f.Then one can show that the map?:P→ωP is a well-de?ned homomorphism into?1(E).

To complete the description of(2)we need the homomorphism?1(E)→Z/p Z.

We may expand any di?erentialω∈?1(E)in terms of a uniformizer t at a point

P0.In other words,we may writeω= j a j t j dt.The Riemann-Roch theorem shows that a0cannot be zero sinceωis holomorphic(so it has no poles)and also

the divisor ofωhas degree2g?2=0(and so it cannot have any zeroes either).

The map?1(E)→Z/p Z is simplyω= j a j t j dt→a0.That this is a homo-morphism follows from the fact that one may add the power series j a j t j in a termwise manner.

We now show how this map is used to solve the ECDLP on anomalous curves.

The attack is very simple,we merely evaluate the map?from the previous section

on both P and Q.Note that this map can be e?ciently computed using a version

of the double-and-add method like that used to compute the Tate pairing.Since

this is a homomorphism into the additive group Z/p Z,the discrete logarithm is

simplyλ≡?(Q)/?(P)(mod p).This can be solved e?ciently using the Euclidean

algorithm.

Implication7.In the case of large odd characteristic one should always have

l=q.

We emphasise that this test is trivial to perform and that the probability of a

random non-supersingular curve failing this test is negligible.

3.5.Weil descent.This method applies to elliptic curves over?eld extensions of

the form F q n where q is a prime or prime power and where n>1.The principle

is to transform the ECDLP from E(F q n)to a discrete logarithm problem on the

Jacobian of a curve C over F q.Since subexponential algorithms exist for the discrete

logarithm problem in high genus curves,this gives a possible method of attack

against the ECDLP.

The technique of Weil descent to solve the elliptic curve discrete logarithm prob-

lem(ECDLP)was?rst proposed by Frey[8].This strategy was detailed further by

Galbraith and Smart[11].These papers were rather general in their scope,but were

not detailed enough to give precise and e?cient algorithms to solve the ECDLP for

speci?c curves.

The work of Gaudry,Hess and Smart[16]was less general than the earlier works

but gave much more powerful and e?cient techniques.In particular,they gave

a very e?cient algorithm to reduce the ECDLP to the discrete logarithm in a

Jacobian of a hyperelliptic curve over F q.We refer to the method of[16]as the

GHS attack.

Menezes and Qu[28]analysed the GHS attack in some detail and demonstrated

that it did not apply to the case when q=2and n is prime.Since this is the

common case in real world applications,the work of Menezes and Qu means that

the GHS attack does not apply to most deployed systems.However,there are a

few?elded elliptic curve systems which use the?elds F2155and F2185,in the IPSEC

standards.Hence there is considerable interest as to whether the GHS attack makes

all curves over these?elds vulnerable.

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM17 In[41]Smart examined the GHS attack for elliptic curves with respect to the ?eld extension F2155/F231and concluded that such a technique was unlikely to work for any curve de?ned over F2155.Jacobson,Menezes and Stein[19]also examined the?eld F2155,this time using the GHS attack down to the sub?eld F25.They concluded that such a strategy could be used in practice to attack around233 isomorphism classes of elliptic curves de?ned over F2155.Since there are about2156 isomorphism classes of elliptic curves de?ned over F2155,the probability of?nding one where the GHS attack is applicable is negligible.Further analysis of the GHS attack has been given by Maurer,Menezes and Teske[26].

We now give some details of the GHS attack.

Let us?rst set up some notation.Throughout this section we let E denote an elliptic curve over the?eld K=F q n where q=2r.Let k denote the sub?eld F q. To simplify the discussion,and since those cases are the most important,we always assume that r and n are odd.We also assume that n is a prime.We stress that it is easy to obtain analogous results in the more general case.

We assume the curve is given by an equation of the form

E:Y2+XY=X3+aX2+b where a∈{0,1},b∈K.

We may assume that a∈{0,1}since r and n are odd.We have points P,Q∈E(K) of large prime order l(we may assume that l≈q n)and we aim to solve the discrete logarithm problem.

De?neσ:K→K to be the q-power Frobenius automorphism,and letπ:K→K denote the absolute Frobenius automorphismπ:α→α2.Therefore,σ=πr.

The?rst step is to construct the Weil restriction of scalars W E/k of E over k,this is an n-dimensional abelian variety over k with the property that W E/k(k)～=E(K). The variety W E/k is then intersected with n?1carefully chosen hyperplanes so as to obtain a hyperelliptic curve C over the?eld k.Let g denote the genus of C.

In addition,the GHS attack gives an explicit and e?cient group homomorphism from E(K)to the Jacobian J C(k)of the curve C.Assuming some mild conditions, the Jacobian of C will contain a subgroup of order l and the image of the subgroup of order l in E(K)will be a non-trivial subgroup of order l in J C(k).

One can then translate the original ECDLP into a discrete logarithm problem on the Jacobian of the curve C over k=F q.The available algorithms have complexity depending on q g where g is the genus of the curve C.Hence the method is only successful when g is not too large.

One of the key results of[16]is the following.

Theorem2(Gaudry,Hess and Smart[16]).The genus of C is equal to either 2m?1or2m?1?1,where m is determined as follows.Let b i=σi(b),then m is

given by

m=m(b)=dim F

2 Span F2 (1,b1/20),...,(1,b1/2n?1) .

In particular we have1≤m≤n.If m is too small then the size of J C(k), which is≈q g,will be too small to contain a subgroup of size l.If m is too large then,although we can translate discrete logarithm problems to the hyperelliptic setting,the genus of the resulting curve is high and so the algorithms for solving the discrete logarithm problem are not e?ective.Hence,this case does not help us to solve the original ECDLP in practice.

Menezes and Qu proved the following theorem which characterises the smallest value of m>1and the elliptic curves which give rise to such m.

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

Theorem3(Menezes and Qu[28]).Keeping the notation as above,and considering the GHS technique for Weil restriction of E from K down to k.Let n denote an odd prime,let t denote the multiplicative order of two modulo n and let s=(n?1)/t. Then

(1)The polynomial x n?1factors over F2as(x?1)f1f2···f s where the f i’s

are distinct irreducible polynomials of degree t.For1≤i≤s de?ne

B i={b∈F q n:(σ?1)f i(σ)b=0}.

(2)For all1≤i≤s and all b∈B i the elliptic curves

Y2+XY=X3+b,

Y2+XY=X3+αX2+b

have m(b)≤t+1,whereαis a?xed element of K of trace one.

(3)If m(b)=t+1then E must be one of the previous curves for some i and

some b∈B i.

(4)The cardinality of the set∪s i=1B i is qs(q t?1)+q.

In particular m(b)=t+1is the smallest attainable value of m(b),which is greater than one,for the?eld F q n using the GHS technique for Weil restriction down to F q.

Menezes and Qu use the above theorem to show that if n is a prime in the range 160≤n≤600and if q=2then the GHS attack will be infeasible.These results are analysed in further detail by Jacobsson,Menezes and Stein[19]and Maurer, Menezes and Teske[26].

A new approach to Weil descent was very recently developed by Galbraith,Hess and Smart in[12].They show that one can sometimes apply the GHS attack to a curve which has a large value of m(b).The idea is to?nd an isogenous curve E (K) which has a small value of m(b )and an isogeny

E(K)?→E (K).

The discrete logarithm problem in E(K)can then be mapped in to the discrete logarithm problem in E (K)and then this can be mapped using the GHS method to the discrete logarithm problem in the Jacobian of a hyperelliptic curve of low genus.E?cient methods to?nd the isogenous curve and the isogeny are given in the paper[12],as well as a study as to how e?ective this extension to the GHS method is in practice.

While the work of Menezes and Qu shows that the GHS attack is not generally applicable to elliptic curve discrete logarithm problems over F2p where p is prime, it shows that there are some choices for p which are more dangerous than others (for instance,the case p=127).The danger of these special primes is not serious in practice,since all primes in the range160<p<600do not su?er from this risk.

One very important point is that the GHS attack is only one particular way to perform the general Weil descent strategy.One cannot deduce that a given instance of the elliptic curve discrete logarithm problem is hard simply by showing that the GHS attack cannot be applied.Hence,it is very important to think more generally about Weil descent as an attack on the ECDLP.

If we consider random elliptic curves over?nite?elds of the form F2p then Weil descent can only be performed with respect to the degree p extension F2p/F2.The abelian variety A which arises from Weil descent therefore is de?ned over F2and has

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM19 dimension p.The di?culty of the ECDLP depends on whether there exist curves of‘small’genus on this variety.Unless the abelian variety A has some very special properties then it seems to be very unlikely that A always has such curves in it. Indeed,the analysis of the GHS attack has reinforced the opinions of researchers that Weil descent is only applicable to a very small proportion of elliptic curves if the extension?eld is chosen to have prime degree p.

Note that almost all research on Weil descent has been performed in character-istic2,since this is the most important case.In fact,the ideas are easily applied to other?nite?elds F p n where p is odd and n>1.The results in these cases are not as strong as in the case of characteristic two,but we still recommend against using such systems if n has a factor which lies between4and10.

Implication8.The GHS and the Weil Descent methodology imply that one should take q=2p,where p is a prime in the even characteristic case.

We emphasise that the Weil descent methods do not apply to elliptic curves over prime?elds F p.

3.6.Special?nite?elds.There are implementation advantages from using ellip-tic curves over?nite?elds F p where p is of a special form such as a generalised Mersenne number.These are primes of the form

p=f(2w)

where w is a multiple of the word size and f is a sparse polynomial with coe?cients drawn from{?1,0,1}.As an example we have

p=2192?264?1=f(264)

where

f=x3?x?1.

We are not aware of any security risk associated with using these particular?nite ?elds.There are no results in the theory of elliptic curve cryptography which suggest that some prime?elds are more or less secure than others.

4.Koblitz curves versus general curves

The term‘Koblitz curves’originally referred to certain elliptic curves over the ?eld F2.Koblitz[22]pointed out that there are two advantages to performing elliptic curve cryptography in the group E(F2n)when E is de?ned over F2,namely:

(1)It is easy to compute the group order#E(F2n).

(2)The arithmetic can been made faster by using Frobenius expansions.

The?rst advantage above is no longer important as there are now extremely e?cient algorithms for counting points on elliptic curves over?elds of small characteristic [17].The second advantage is still of interest,as it can lead to cryptographic systems with improved performance.Hence Koblitz curves have remained very popular for implementations of elliptic curve cryptography.

Since we always want curves whose group order is divisible by a large prime it follows that we must take the extension degree n to be prime(otherwise the curve have large subgroups corresponding to the sub?elds of F2n and so the group order has various signi?cant factors).Hence,Koblitz curves over F2are not generally at risk from the Weil descent attack.

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

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

More recently the de?nition of Koblitz curves has been extended by Gallant, Lambert and Vanstone[14]to the case of elliptic curves over prime?elds 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 small?elds,and in particular F2)and second we discuss Koblitz curves over large prime?elds.

4.1.Koblitz curves in characteristic2.The SEC standard[2]gives20prede-?ned curves in characteristic two,a number of which appear in other standards such as ANSI X9.62,WAP WTLS or NIST FIPS186.2.Of these20prede?ned 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 e?cient 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 same?nite?eld.However,the e?ect 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 larger?nite?elds the e?ect of choosing a Koblitz curve is similar. Table3demonstrates this by showing the di?erence between the security of a general curve and a Koblitz curve for the?eld sizes in the above mentioned standard, with the speci?ed 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 a?eld 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.

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 15prede?ned curves over ?elds of large prime characteristic.Of these four are not chosen at random,but are chosen to have e?ciently 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 ?eld needs to be chosen so that p ≡1(mod 3),unlike the other curves in the standard the ?eld of de?nition 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 ?eld 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 di?erence between the security of a general curve and a Koblitz curve for the ?eld 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.

本文来源：https://www.bwwdw.com/article/aq81.html

相关文章：

2017年下半年教师资格证《教育教学知识与能力（中学）》04-01

先进事迹材料02-24

上一篇：ASCO+300系列开路切换自动转换开关ATS 下一篇：2015年关心下一代工作总结