Evaluation of Security Level of Cryptography:
ECDSA Signature Scheme
Alfred Menezes, Minghua Qu, Doug Stinson, Yongge Wang
Certicom ResearchContact: amenezes@certicom.com
January 15, 2001

2

Protocol specification

1

Summary

Page 1This document summarizes the state-of-the-art in knowledge on the security of the elliptic curve
digital signature algorithm (ECDSA). ECDSA is the elliptic curve analogue of the digital signature algorithm (DSA) and has been standardized by many standards organizations around theworld including NIST, IEEE, ANSI and ISO. The security of DSA, ECDSA and related discrete
logarithm signature schemes have been widely studied by the cryptographic community. Our
study found no new weaknesses in ECDSA.

2

Protocol specification

2.1 EC domain parameters
Elliptic Curve domain parameters are comprised of:
1. a field size q, where either qp, an odd prime, or q

2m ;2. an indication FR (field representation) of the representation used for the elements ofq;

3. (optional) a bit string   of length at least 160 bits, if the elliptic curve was generated
in accordance with the method described in the submission;
4. two field elements a and b in q which define the equation of the elliptic curve E over q(i.e., y2 x3 ax b in the case p 3, and y2 xy x3 ax2 b in the case q 2m);

xG  yG  of prime order
5. two field elements xG and yG in q which define a finite point G
in E q  ;6. the order n of the point G, with n
7. the cofactor h #E q  n.

2160 and n

4  q; and2.2 ECDSA key pairs
An entity A’s key pair is associated with a particular set of EC domain parameters D  q  FR  a  b,
G  n  h  . This association can be assured cryptographically (e.g., with certificates) or by context(e.g., all entities use the same domain parameters). The entity A must have the assurance thatthe domain parameters are valid (see the submission) prior to key generation.
ECDSA K EY PAIR G ENERATION. Each entity A does the following:2

Protocol specification

Page 2

1. Select a random or pseudorandom integer d in the interval 1  n
2. Compute Q



1.


dG.

3. A’s public key is Q; A’s private key is d.

2.3 ECDSA signature generation
To sign a message m, an entity A with domain parameters D  q  FR  a  b  G  n  h  and associatedkey pair d  Q  does the following:
1. Select a random or pseudorandom integer k, 1

k


n


1.

x1  y1  and convert x1 to an integer x1 .

2. Compute kG
3. Compute r



x1 mod n. If r

0 then go to step 1.

4. Compute k 1 mod n.


5. Compute SHA-1 m  and convert this bit string to an integer e.
6. Compute s

k 1 e


dr  mod n. If s

0 then go to step 1.

7. A’s signature for the message m is r s  .

2.4 ECDSA signature verification
To verify A’s signature r s  on m, B obtains an authentic copy of A’s domain parameters D
q  FR  a  b  G  n  h  and associated public key Q. It is recommended that B also validates D and
Q (see the submission). B then does the following:
1. Verify that r and s are integers in the interval 1  n

1.


2. Compute SHA-1 m  and convert this bit string to an integer e.
3. Compute w

s 1 mod n.

4. Compute u1

ew mod n and u2

5. Compute X

u1 G



rw mod n.

u2Q.

6. If X O , then reject the signature. Otherwise, convert the x-coordinate x 1 of X to an
integer x1 , and compute v x1 mod n.
7. Accept the signature if and only if vr.

4Security level of cryptographic primitive functions

Page 3

P ROOF THAT S IGNATURE V ERIFICATION W ORKS. If a signature r s  on a message m wasindeed generated by A, then s k 1 e dr  mod n. Rearranging givesThus u1 G

3

k

s 1 e

dr 

u2 Q

u1

u2 d  G



s 1e


s 1 rdkG, and so v

we

wrd

u1

u2 d

mod n r as required.

Security level of cryptographic techniques

The security objective of ECDSA is to be existentially unforgeable against a chosen-message
attack. The goal of an adversary who launches such an attack against a legitimate entity A
is to obtain a valid signature on a single message m, after having obtained A’s signature on acollection of messages (not including m) of the adversary’s choice.
Some progress has been made on proving the security of ECDSA, albeit in strong theoreticalmodels. Slight variants of DSA and ECDSA (but not ECDSA itself) have been proven to be
existentially unforgeable against chosen-message attack by Pointcheval and Stern [32] (see also[7]) under the assumptions that the discrete logarithm problem is hard and that the hash function
employed is a random function. Specifically, their results show that any successful attack which
does not use the structure of the specific hash function in the scheme must break the Elliptic
Curve Discrete Logarithm Problem (ECDLP). ECDSA itself has been recently proven secureby Brown [8] under the strong assumption that the underlying group is a generic group andthat the hash function employed is collision resistant. Specifically, Brown’s results show thatany successful attack which does not use the structure of the Elliptic Curve group must findcollisions in the hash function.

4

Security level of cryptographic primitive functions

4.1 Attacks on the hash function
D EFINITION. A (cryptographic) hash function H is a function that maps bit strings of arbitrary
lengths to bit strings of a fixed length t such that:
1. H can be computed efficiently;

2. (preimage resistance) For y selected uniformly at random from 0  1  t , it is computationally infeasible to find a bit string x such that H x y.
3. (second preimage resistance) Given x1 , it is computationally infeasible to find a different
bit string x2 such that H x1 H x2  .

4Security level of cryptographic primitive functions

Page 44. (collision resistance) It is computationally infeasible to find distinct bit strings x 1 and x2
such that H x1 H x2  .
SHA-1 S ECURITY R EQUIREMENTS. The following gives some examples of how attacks on
ECDSA can be successfully launched if SHA-1 is not preimage resistant, second preimage
resistant, or collision resistant.
1. If SHA-1 is not preimage resistant, then an adversary E may be able to forge A’s signatures as follows. E selects an arbitrary integer l, and computes r as the x-coordinateof Q lG reduced modulo n. E sets s r and computes e rl mod n. If E can find amessage m such that e SHA-1 m  , then r s  is a valid signature for m.
2. If SHA-1 is not collision resistant, then an entity A may be able to repudiate signatures asfollows. A first generate two messages m and m such that SHA-1 m 
SHA-1 m  ; sucha pair of messages is called a collision for SHA-1. She then signs m, and later claims tohave signed m (note that every signature for m is also a signature for m ).
3. If SHA-1 is not collision resistant, then an entity B could use the birthday attack to swindle
A as follows. B prepares two versions (m1 and m2 ) of a contract, where m1 is favorable to
A and m2 bankrupts A. B makes several subtle changes to each document and compares
SHA-1 m2  , where m1 (m2 ) is a subtle variant of m1 (m2 ). When
whether SHA-1 m1 
B finds two such variants, B gets the signature r s  of m1 from A. Then r s  is also asignature of m2 .
4. If SHA-1 is not second preimage resistant, then an entity B may be able to forge signatures
as follows. B generates a message m, find another message m such that SHA-1 m 
SHA-1 m  , and gets the signature r s  of m from A. Then r s  is also a signature of m.
I DEAL S ECURITY. A t-bit hash function is said to be have ideal security [26] if both: (i) given ahash output, producing a preimage (or a second preimage) requires approximately 2t operations;and (ii) producing a collision requires approximately 2t 2 operations (this is the best that can be
hoped for, in view of the birthday attacks). SHA-1 is a 160-bit hash function and is believed tohave ideal security. The fastest method known for attacking ECDSA by exploiting propertiesof SHA-1 is to find collisions for SHA-1. Since this is believed to take 280 steps, attacking
ECDSA in this way is computationally infeasible. Note, however, that this attack imposes anupper bound of 280 on the security level of ECDSA, regardless of the size of the primary security
parameter n. Of course, this is also the case with all present signature schemes with appendix
since the only hash functions that are widely accepted as being both secure and practical are
SHA-1 and RIPEMD-160 (see Dobbertin, Bosselaers and Preneel [10]), both of which are 160bit hash functions.


VARIABLE O UTPUT L ENGTH H ASH F UNCTIONS . It is expected that SHA-1 will soon be
replaced by a family of hash functions Hl , where Hl is an l-bit hash function having ideal

5

Security level of cryptographic primitive problem

Page 5security. If one uses ECDSA with parameter n, then one would use Hl , where llog2 n , as
the hash function. In this case, attacking ECDSA by solving the ECDLP and attacking ECDSA
by finding collisions for Hl , both take approximately the same amount of time. The new family
will have output lengths of 256, 384 and 512 bits [29].
VAUDENAY ’ S ATTACKS . Vaudenay [43] demonstrated a theoretical weakness in DSA based on
his insight that the actual hash function used in the DSA is SHA-1 modulo q, not just SHA-1,
where q is a 160-bit prime. (Since SHA-1 is a 160-bit hash function, some of its outputs, whenconverted to integers, are larger than q. Hence, in general, SHA-1 m   SHA-1 m  mod q).)This weakness allows the selective forgery of one message if the adversary can select the domain
parameters. This weakness is not present in ECDSA because of the requirement that n (theanalogous quantity to q in the DSA) be greater than 2160.

5

Security level of cryptographic primitive problem: the elliptic curve discrete logarithm problem

One way in which an adversary can succeed is to compute A’s private key d from A’s domain
parameters q  FR  a  b  G  n  h  and public key Q. Then the adversary could subsequently forge
A’s signature on any message of its choice.
P ROBLEM D EFINITION. The elliptic curve discrete logarithm problem (ECDLP) is the follow
ing: given an elliptic curve E defined over a finite field q, a point P  E q  of order n, and apoint Q lP where 0 l n 1, determine l.


5.1 Known attacks
This subsection overviews the algorithms known for solving the ECDLP and discusses how
they can be avoided in practice.
1. NAIVE E XHAUSTIVE S EARCH. In this method, one simply computes successive multiples of P: P, 2P, 3P, 4P until Q is obtained. This method can take up to n steps in theworst case.
2. P OHLIG -H ELLMAN A LGORITHM . This algorithm, due to Pohlig and Hellman [31], exploits the factorization of n, the order of the point P. The algorithm reduces the problem
of recovering l to the problem of recovering l modulo each of the prime factors of n; thedesired number l can then be recovered by using the Chinese Remainder Theorem.
The implications of this algorithm are the following. To construct the most difficult instance of the ECDLP, one must select an elliptic curve whose order is divisible by a large

5

Security level of cryptographic primitive problem

Page 6prime n. Preferably, this order should be a prime or almost a prime (i.e. a large prime ntimes a small integer h). For the remainder of this section, we shall assume that the ordern of P is prime.
3. BABY-S TEP G IANT-S TEP A LGORITHM. This algorithm is a time-memory trade-off ofthe method of exhaustive search. It requires storage for about  n points, and its running
time is roughly  n steps in the worst case.
4. P OLLARD ’ S R HO A LGORITHM . This algorithm, due to Pollard [33], is a randomized
version of the baby-step giant-step algorithm. It has roughly the same expected running
time ( πn  2 steps) as the baby-step giant-step algorithm, but is superior in that it requiresa negligible amount of storage.
Gallant, Lambert and Vanstone [16], and Wiener and Zuccherato [44] showed how Pollard’s rho algorithm can be sped up by a factor of  2. Thus the expected running time of
Pollard’s rho method with this speedup is  πn   2 steps.
5. PARALLELIZED P OLLARD ’ S R HO A LGORITHM . Van Oorschot and Wiener [30] showed
how Pollard’s rho algorithm can be parallelized so that when the algorithm is run in parallel on r processors, the expected running time of the algorithm is roughly  πn   2r 
steps. That is, using r processors results in an r-fold speed-up.
6. P OLLARD ’ S LAMBDA METHOD. This is another randomized algorithm due to Pollard[33]. Like Pollard’s rho method, the lambda method can also be parallelized with a linear
speedup. The parallelized lambda-method is slightly slower than the parallelized rhomethod [30]. The lambda-method is, however, faster in situations when the logarithm
being sought is known to lie in a subinterval 0  b of 0  n 1 , where b 0  39n [30].








7. M ULTIPLE L OGARITHMS . R. Silverman and Stapleton [37] observed that if a single
instance of the ECDLP (for a given elliptic curve E and base point P) is solved using(parallelized) Pollard’s rho method, then the work done in solving this instance can beused to speed up the solution of other instances of the ECDLP (for the same curve E andbase point P). More precisely, if the first instance takes expected time t, then the second
instance takes expected time  2 1  t 0  41t. Having solved these two instances, thethird instance takes expected time  3  2  t 0  32t. Having solved these three instances, the fourth instance takes expected time  4  3  t 0  27t. And so on. Thus
subsequent instances of the ECDLP for a particular elliptic curve become progressively
easier. Another way of looking at this is that solving k instances of the ECDLP (for thesame curve E and base point P) takes only  k as much work as it does to solve one
instance of the ECDLP. This analysis does not take into account storage requirements.












Concerns that successive logarithms become easier can be addressed by ensuring that theelliptic parameters are chosen so that the first instance is infeasible to solve.

5

Security level of cryptographic primitive problem

Page 7

8. S UPERSINGULAR E LLIPTIC C URVES. Menezes, Okamoto and Vanstone [25, 24] andFrey and Rück [14] showed how, under mild assumptions, the ECDLP in an elliptic curveE defined over a finite field q can be reduced to the ordinary DLP in the multiplicativegroup of some extension field qk for some k 1, where the number field sieve algorithm
applies. The reduction algorithm is only practical if k is small — this is not the case formost elliptic curves, as shown by Balasubramanian and Koblitz [4]. To ensure that the
reduction algorithm does not apply to a particular curve, one only needs to check that n,the order of the point P, does not divide qk 1 for all small k for which the DLP in qk is
tractable — in practice, when n 2160 then 1 k 20 suffices [2].
An elliptic curve E over q is said to be supersingular if the trace t of E is divisible by
the characteristic p of q . For this very special class of elliptic curves, it is known thatk 6. It follows that the reduction algorithm yields a subexponential-time algorithm for
the ECDLP in supersingular curves. For this reason, supersingular curves are explicitly
excluded from use in the ECDSA by the above divisibility check.








More generally, the divisibility check rules out all elliptic curves for which the ECDLP
can be efficiently reduced to the DLP in some small extension of q . These include thesupersingular elliptic curves and elliptic curves of trace 2 (elliptic curves E over q for
which #E q 
q 1).

9. P RIME -F IELD A NOMALOUS C URVES. An elliptic curve E over p is said to be prime
p. Semaev [35], Smart [39], and Satoh and Araki [34]field-anomalous if #E p showed how to efficiently solve the ECDLP for these curves. The attack does not extend
to any other classes of elliptic curves. Consequently, by verifying that the number ofpoints on an elliptic curve is not equal to the cardinality of the underlying field, one caneasily ensure that the Semaev-Smart-Satoh-Araki attack does not apply.


10. C URVES D EFINED OVER A S MALL F IELD. Suppose that E is an elliptic curve definedover the finite field 2e . Gallant, Lambert and Vanstone [16], and Wiener and Zuccherato [44] showed how Pollard’s rho algorithm for computing elliptic curve logarithms inE 2ed  can be further sped up by a factor of  d — thus the expected running time of
Pollard’s rho method for these curves is
πn  d  2 steps. For example, if E is a Koblitz
curve (see the submission), then Pollard’s rho algorithm for computing elliptic curve logarithms in E 2m  can be sped up by a factor of  m. This speedup should be consideredwhen doing a security analysis of elliptic curves whose coefficients lie in a small subfield.

11. C URVES D EFINED OVER 2m , m C OMPOSITE . Galbraith and Smart [15], expandingon earlier work of Frey [12, 13], discuss how the Weil descent might be used to solve
the ECDLP for elliptic curves defined over 2m where m is composite (such fields are
sometimes called composite fields). More recently, Gaudry, Hess and Smart [17] refinedthese ideas to provide some evidence that when m has a small divisor l, e.g. l 4, the
ECDLP for elliptic curves defined over 2m can be solved faster than with Pollard’s rho

5

Security level of cryptographic primitive problem

Page 8algorithm. See also Menezes and Qu [27] for an analysis of the Weil descent attack. In
light of these results, it seems prudent to not use elliptic curves over composite fields.
It should be noted that some ECC standards, including the draft ANSI X9.63 [3], explicitly exclude the use of elliptic curves over composite fields. The ANSI X9F1 committee
also agreed in January 1999 to exclude the use of such curves in a forthcoming revisionof ANSI X9.62.
12. N ON -A PPLICABILITY OF I NDEX -C ALCULUS M ETHODS. Whether or not there exists a
general subexponential-time algorithm for the ECDLP is an important unsettled question,and one of great relevance to the security of ECDSA. It is extremely unlikely that anyone
will ever be able to prove that no subexponential-time algorithm exists for the ECDLP.
However, much work has been done on the DLP over the past 24 years, and more specifically on the ECDLP over the past 16 years, and no subexponential-time algorithm has
been discovered for the ECDLP. Miller [28] and J. Silverman and Suzuki [38] have given
convincing arguments for why the most natural way in which the index-calculus algorithms can be applied to the ECDLP is most likely to fail.
13. X EDNI -C ALCULUS ATTACKS. A very interesting line of attack on the ECDLP, called thexedni-calculus attack was recently proposed by J. Silverman [36]. One intriguing aspectof the xedni-calculus is that it can be adapted to solve both the ordinary discrete logarithm
and the integer factorization problems. However, it was subsequently shown by a teamof researchers including J. Silverman (see Jacobson et al. [19]) that the attack is virtuallycertain to fail in practice.
14. H YPERELLIPTIC C URVES. Hyperelliptic curves are a family of algebraic curves of arbitrary genus that includes elliptic curves. Hence, an elliptic curve can be viewed as a hyperelliptic curve of genus 1. Adleman, DeMarrais and Huang [1] (see also Stein, Müller andThiel [41]) presented a subexponential-time algorithm for the discrete logarithm problem
in the jacobian of a large genus hyperelliptic curve over a finite field. However, in thecase of elliptic curves, the algorithm is worse than naive exhaustive search.
15. E QUIVALENCE TO OTHER D ISCRETE L OGARITHM P ROBLEMS . Stein [40] and Zuccherato [45] showed that the discrete logarithm problem in real quadratic congruencefunction fields of genus 1 is equivalent to the ECDLP. Since no subexponential-time algorithm is known for the former problem, this may provide further evidence for the hardnessof the ECDLP.

5.2 Experimental results
The best general-purpose algorithm known for the ECDLP is the parallelized version of Pollard’s rho algorithm which has an expected running time of  πn   2r  steps, where n is the(prime) order of the base point P, and r is the number of processors utilized.

5

Security level of cryptographic primitive problem

Page 9C ERTICOM ’ S ECC C HALLENGE. Certicom initiated an ECC challenge [9] in November 1997
in order to encourage and stimulate research on the ECDLP. Their challenges consist of instances of the ECDLP on a selection of elliptic curves. The challenge curves are divided into
three categories listed below. In the following, ECCp-k denotes a random curve over a field p ,ECC2-k denotes a random curve over a field 2m , and ECC2K-k denotes a Koblitz curve (see
the submission) over 2m ; k is the bitlength of n. In all cases, the bitsize of the order of theunderlying finite field is equal or slightly greater than k (so curves have either prime order oralmost prime order).


1. Randomly generated curves over p, where p is prime: ECCp-79, ECCp-89, ECCp-97,
ECCp-109, ECCp-131, ECCp-163, ECCp-191, ECCp-239, and ECCp-359.

2. Randomly generated curves over 2m , where m is prime: ECC2-79, ECC2-89, ECC2-97,
ECC2-109, ECC2-131, ECC2-163, ECC2-191, ECC2-238, and ECC2-353.

3. Koblitz curves over 2m , where m is prime: ECC2K-95, ECC2-108, ECC2-130, ECC2163, ECC2-238, and ECC2-358.
R ESULTS OF THE C HALLENGE . Escott et al. [11] report on their 1998 implementation of theparallelized Pollard’s rho algorithm which incorporates some improvements of Teske [42]. The
hardest instance of the ECDLP they solved was the Certicom ECCp-97 challenge. For this task
they utilized over 1200 machines from at least 16 countries, and found the answer in 53 days.
The total number of steps executed was about 2 1014 elliptic curve additions which is close
to the expected time ((  πn  2 3  5 1014, where n 297). Escott et al. [11] conclude thatthe running time of Pollard’s rho algorithm in practice fits well with the theoretical predictions.
They estimate that the ECCp-109 challenge could be solved by a network of 50,000 Pentium
Pro 200MHz machines in about 3 months.


5.3 Hardware attacks
Van Oorschot and Wiener [30] examined the feasibility of implementing parallelized Pollard’s
rho algorithm using special-purpose hardware. They estimated that if n 10 36 2120, thena machine with r 330  000 processors could be built for about US $10 million that could
compute a single elliptic curve discrete logarithm in about 32 days. Since ANSI X9.62 mandates
that the parameter n should satisfy n 2160, such hardware attacks appear to be infeasible withtoday’s technology.




6

Other attacks

Page 10

6

Other attacks

I MPLEMENTATION ATTACKS . The existing ECDSA standards do not address attacks that could
be launched against implementations of ECDSA such as timing attacks (Kocher [21]), differential fault analysis (Boneh, DeMillo and Lipton [6]), differential power analysis (Kocher, Jaffe
and Jun [22]), and attacks which exploit weak pseudorandom number generators (Kelsey et al.
[20]).
S ECURITY R EQUIREMENTS FOR P ER -M ESSAGE S ECRETS. The per-message secrets k in
ECDSA signature generation have the same security requirements as the private key d. Thisis because if an adversary E learns a single per-message secret k which was used by A togenerate a signature r s  on some message m, then E can recover A’s private key since d
r 1 ks e  mod n where e SHA-1 m  (see step 6 of ECDSA signature generation). Henceper-message secrets must be securely generated, securely stored, and securely destroyed after
they have been used.


R EPEATED U SE OF P ER -M ESSAGE S ECRETS. The per-message secrets k used to sign two or
more messages should be generated independently of each other. In particular, a different permessage secret k should be generated for each different message signed; otherwise, the private
key d can be recovered. Note that if a secure random or pseudorandom number generator isused, then the chance of generating a repeated k value is negligible. To see how private keys
can be recovered if per-message secrets are repeated, suppose that the same per-message secret k
was used to generate ECDSA signatures r s1  and r s2  on two different messages m1 and m2 .
Then s1 k 1 e1 dr  mod n  and s2 k 1 e2 dr  mod n  , where e1 SHA-1 m1  ande2 SHA-1 m2  . Then ks1 e1 dr mod n  and ks2 e2 dr mod n  . Subtraction gives
k s1 s2  e1 e2 mod n  . If s1  s2 mod n  , which occurs with overwhelming probability,
then k
s1 s2  1 e1 e2  mod n  . Thus, an adversary can determine k, and then use thisto recover d, as described above.














ATTACK U SING K NOWN R ELATIONS O N P ER -M ESSAGE S ECRETS. There should also be no
obvious relations between the per-message secrets. For example, suppose that there is a relation
k2 ak1 b for some fixed a and b. Since k1 s1 e1 dr1 and k2 s2 e2 dr2, we can get two
equations k1 s1 e1 dr1 and ak1 b  s2 e2 dr2 in two unknows k1 and d. Hence one cansolve the equations and obtain the value of d.
PARTIAL I NFORMATION O N P ER -M ESSAGE S ECRETS . In [18], Howgrave-Graham and Smart
use lattice reduction techniques to show that partial information of DSA per-message secrets
can lead to the complete exposure of the private key. For example, the attack is practical if acontiguous block of 5% of the bits in 20 per-message secrets is known, for p a 160 bit prime.
Their results could easily be extended to ECDSA.
To avoid similar attacks where partial information about the per-message secrets may be leaked,

8

Performance comparison

Page 11

it is imperative that the per-message secrets be generated uniformly at random (or pseudorancom) from the interval 1  n 1 , and securely destroyed after usage.


D UPLICATE -S IGNATURE K EY S ELECTION. A signature scheme S is said to have the duplicatesignature key selection (DSKS) property if given A’s public key PA and given A’s signature sA
on a message M, an adversary E is able to select a valid key pair PE  SE  for S such that sA is
also E’s signature on M. Note that this definition requires that SE is known to E. Blake-Wilson
and Menezes [5] showed how this property can be exploited to attack a key agreement protocol
which employs a signature scheme. They also demonstrated that if entities are permitted to
select their own domain parameters, then ECDSA possesses the DSKS property. To see this,
suppose that A’s domain parameters are DA
q  FR  a  b  G  n  h  , A’s key pair is QA  dA  , andr s  is A’s signature on M. The adversary E selects an arbitrary integer c, 1 c n 1, suchthat t :s 1 e s 1 rc  mod n   0, computes X s 1 eG s 1 rQ (where e SHA-1 M and G
t 1 mod n  X . E then forms DE
q  FR  a  b  G  n  h  and QE cG. Then it is easily
verified that DE and QE are valid, and that r s  is also E’s signature on M.
















If one mandates that the generating point G be selected verifiably at random (that is, verify that
G is a valid point on the curve and it has the correct order) during domain parameter generation,then it appears that ECDSA no longer possesses the DSKS property. It must be emphasized thatpossession of the DSKS property does not constitute a weakness of the signature scheme — thegoal of a signature scheme is to be existentially unforgeable against a chosen-message attack.
Rather, it demonstrates the importance of auditing domain parameter and public key generation.

7

Recommended parameters

In Table 1, the security levels of the ECDSA with the parameters recommended in the submission are compared with other submitted schemes, with RSA, and with symmetric schemes(e.g., the Advanced Encryption Standard–AES). Some of the comparisons among symmetrickey cryptography, RSA security, and ECDSA security are adapted from Lenstra and Verheul
[23].

8

Performance comparison

Table 1 presented comparable key lengths of several schemes. Generally, the ESIGN signaturescheme is faster than both ECDSA and RSA signature schemes with comparable key lengths.
ACE, RSA, and ESIGN have roughly the same public key size for comparable security level.
ACE and RSA have roughly the same private key size for comparable security level. ESIGN’s
private key size is roughly 2  3 of the ACE (or RSA) private key size for comparable security
level. ECDSA and MY-ELLTY have significantly smaller key size for comparable security

8

Performance comparison

Symmetric
Key Size
40
48
76
80
(SKIPJACK)112(Triple-DES)
128(128-bit AES)
192
(192-bit AES)
256
(256-bit AES)

Page 12

Table 1: Rough Comparison of Security Levels
RSA
ESIGN
ACE
ECDSA
Modulus
Modulus
ModulusKey Size
Size
Size
Size

MY-ELLTY
Key Size
160
192

960

960

960

152

1024

1024

1024

160

2048

2048

2048

224

3072

3072

3072

256

7680

7680

7680

384

15360

15360

15360

512

level. However, the hash function used in MY-ELLTY is not collision resistant, thus it is notsecure against attacks on the hash function.

References

Page 13

References[1] L. Adleman, J. DeMarrais and M. Huang, “A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves
over finite fields”, Algorithmic Number Theory, Lecture Notes in Computer Science, 877(1994), Springer-Verlag, 28-40.
[2] ANSI X9.62, Public Key Cryptography for the Financial Services Industry: The Elliptic
Curve Digital Signature Algorithm (ECDSA), 1999.
[3] ANSI X9.63, Public Key Cryptography for the Financial Services Industry: Elliptic Curve
Key Agreement and Key Transport Protocols, working draft, October 2000.
[4] R. Balasubramanian and N. Koblitz, “The improbability that an elliptic curve has subexponential discrete log problem under the Menezes–Okamoto–Vanstone algorithm”, Journalof Cryptology, 11 (1998), 141-145.
[5] S. Blake-Wilson and A. Menezes, “Unknown key-share attacks on the station-to-station(STS) protocol”, Public Key Cryptography – Proceedings of PKC ’99, Lecture Notes in
Computer Science, 1560 (1999), 154-170.
[6] D. Boneh, R. DeMillo and R. Lipton, “On the importance of checking cryptographic protocols for faults”, Advances in Cryptology – Eurocrypt ’97, Lecture Notes in Computer
Science, 1233 (1997), Springer-Verlag, 37-51.
[7] E. Brickell, D. Pointcheval, S. Vaudenay and M. Yung, “Design validations for discrete
logarithm based signature schemes”, Public Key Cryptography – Proceedings of PKC
2000, Lecture Notes in Computer Science, 1751 (2000), 276-292.
[8] D. Brown, “The exact security of ECDSA”, Technical report CORR 2000-54, Dept. of
C&O, University of Waterloo, 2000. Available from http://www.cacr.math.uwaterloo.ca[9] Certicom ECC Challenge, November 1997, http://www.certicom.com[10] H. Dobbertin, A. Bosselaers and B. Preneel, “RIPEMD-160: A strengthened version of
RIPEMD”, Fast Software Encryption – FSE ’96, Lecture Notes in Computer Science,
1039 (1996), Springer-Verlag, 71-82.
[11] A. Escott, J. Sager, A. Selkirk and D. Tsapakidis, “Attacking elliptic curve cryptosystems
using the parallel Pollard rho method”, CryptoBytes – The Technical Newsletter of RSA
Laboratories, volume 4, number 2, Winter 1999, 15-19. Also available at http://www.
rsasecurity.com[12] G. Frey, “How to disguise an elliptic curve (Weil descent)”, talk at ECC ’98. Slides available at http://www.cacr.math.uwaterloo.ca

References

Page 14[13] G. Frey, “Applications of arithmetical geometry to cryptographic constructions”, Proceedings of the Fifth International Conference on Finite Fields and Applications, to appear.
[14] G. Frey and H. Rück, “A remark concerning m-divisibility and the discrete logarithm inthe divisor class group of curves”, Mathematics of Computation, 62 (1994), 865-874.
[15] S. Galbraith and N. Smart, “A cryptographic application of Weil descent”, Codes andCryptography, Lecture Notes in Computer Science, 1746 (1999), Springer-Verlag, 191200.
[16] R. Gallant, R. Lambert and S. Vanstone, “Improving the parallelized Pollard lambda
search on binary anomalous curves”, to appear in Mathematics of Computation.
[17] P. Gaudry, F. Hess and N. Smart, “Constructive and destructive facets of Weil descent on elliptic curves”, preprint, January 2000. Available from http://www.hpl.hp.com/
techreports/2000/HPL-2000-10.html[18] N. Howgrave-Graham and N. Smart. Lattice attacks on digital signature schemes. To appear in: Design, Codes, and Cryptography.
[19] M. Jacobson, N. Koblitz, J. Silverman, A. Stein and E. Teske, “Analysis of the xedni
calculus attack”, Designs, Codes and Cryptography, 20 (2000), 41-64.
[20] J. Kelsey, B. Schneier, D. Wagner and C. Hall, “Cryptanalytic attacks on pseudorandom
number generators”, Fast Software Encryption – FSE ’98, Lecture Notes in Computer
Science, 1372 (1998), Springer-Verlag, 168-188.
[21] P. Kocher, “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and othersystems”, Advances in Cryptology – Crypto ’96, Lecture Notes in Computer Science, 1109
(1996), Springer-Verlag, 104-113.
[22] P. Kocher, J. Jaffe and B. Jun, “Differential power analysis”, Advances in Cryptology –Crypto ’99, Lecture Notes in Computer Science, 1666 (1999), Springer-Verlag, 388-397.
[23] A. Lenstra and E. Verheul. Selecting cryptographic key sizes. Distributed in the 3rd workshop on Elliptic Curve Cryptography (ECC 99). Available from http://www.cryptosavvy.
com/[24] A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers,
Boston, 1993.
[25] A. Menezes, T. Okamoto and S. Vanstone, “Reducing elliptic curve logarithms to logarithms in a finite field”, IEEE Transactions on Information Theory, 39 (1993), 1639-1646.
[26] A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC
Press, 1997.

References

Page 15[27] A. Menezes and M. Qu, “Analysis of the Weil descent attack of Gaudry, Hess and Smart”,
Proceedings of RSA 2001, 2001, to appear.
[28] V. Miller, “Uses of elliptic curves in cryptography”, Advances in Cryptology – Crypto ’85,
Lecture Notes in Computer Science, 218 (1986), Springer-Verlag, 417-426.
[29] National Institute of Standards and Technology, “Descriptions of SHA-256, SHA-384,
and SHA-512”, preprint, 2000.
[30] P. van Oorschot and M. Wiener, “Parallel collision search with cryptanalytic applications”,
Journal of Cryptology, 12 (1999), 1-28.
[31] S. Pohlig and M. Hellman, “An improved algorithm for computing logarithms over GF p and its cryptographic significance”, IEEE Transactions on Information Theory, 24 (1978),106-110.
[32] D. Pointcheval and J. Stern, “Security proofs for signature schemes”, Advances in Cryptology – Eurocrypt ’96, Lecture Notes in Computer Science, 1070 (1993), Springer-Verlag,
387-398.
[33] J. Pollard, “Monte Carlo methods for index computation mod p”, Mathematics of Computation, 32 (1978), 918-924.
[34] T. Satoh and K. Araki, “Fermat quotients and the polynomial time discrete log algorithm
for anomalous elliptic curves”, Commentarii Mathematici Universitatis Sancti Pauli, 47(1998), 81-92.
[35] I. Semaev, “Evaluation of discrete logarithms in a group of p-torsion points of an elliptic
curve in characteristic p”, Mathematics of Computation, 67 (1998), 353-356.
[36] J. Silverman, “The xedni calculus and the elliptic curve discrete logarithm problem”, Designs, Codes and Cryptography, 20 (2000), 5-40.
[37] R. Silverman and J. Stapleton, Contribution to ANSI X9F1 working group, 1997.
[38] J. Silverman and J. Suzuki, “Elliptic curve discrete logarithms and the index calculus”,
Advances in Cryptology – Asiacrypt ’98, Lecture Notes in Computer Science, 1514 (1999),
Springer-Verlag, 110-125.
[39] N. Smart, “The discrete logarithm problem on elliptic curves of trace one”, Journal of
Cryptology, 12 (1999), 193-196.
[40] A. Stein, “Equivalences between elliptic curves and real quadratic congruence function
fields”, Journal de Théorie des Nombres de Bordeaux, 9 (1997), 75-95.
[41] A. Stein, V. Müller and C. Thiel, “Computing discrete logarithms in real quadratic congruence function fields of large genus”, Mathematics of Computation, 68 (1999), 807-822.

References

Page 16[42] E. Teske, “Speeding up Pollard’s rho method for computing discrete logarithms”, Algorithmic Number Theory, Lecture Notes in Computer Science, 1423 (1998), Springer-Verlag,
541-554.
[43] S. Vaudenay, “Hidden collisions on DSS”, Advances in Cryptology – Crypto ’96, Lecture
Notes in Computer Science, 1109 (1996), Springer-Verlag, 83-88.
[44] M. Wiener and R. Zuccherato, “Faster attacks on elliptic curve cryptosystems”, Selected
Areas in Cryptography, Lecture Notes in Computer Science, 1556 (1999), SpringerVerlag, 190-200.
[45] R. Zuccherato, “The equivalence between elliptic curve and quadratic function field discrete logarithms in characteristic 2”, Algorithmic Number Theory, Lecture Notes in Computer Science, 1423 (1998), Springer-Verlag, 621-638.