I am wondering about the computational cost of ECDSA signature verification, in term of multiplications in the base field; and, as an aside, in term of (much cheaper) additions. To make things concrete, assume ECDSA in a field $GF(p)$ per FIPS 186-3 (which refers to ANSI X9.62:2005 (webstore)), using parameters as in appendix D.1.2.

I'm interested first in the straightest standard-abiding method with a cost in the right ballpark; then in the most worthwhile refinements of that. I have identified (by name, but not quantitative effect, especially for the first one):

  • projective coordinate systems, said to allow replacing inversion in the base field (as used in straight point addition in the elliptic curve group) by fewer operations than standard inversion algorithms, e.g $x\mapsto x^{p-2}\bmod p$ (or the more efficient extended euclidian, but that does not quite match my "multiplications in the base field" evaluation criteria);
  • Shamir's trick, where $a*P+b*Q$ is computed by adding either $P$, $Q$ or $P+Q$ (on the elliptic curve group) when scanning the bits of integer multiplicands $a$ and $b$;
  • sliding window techniques when scanning the bits of a multiplicand.

I'm not interested in the cost of verification of a certificate introducing the public key, or the cost of hashing; and only marginally by savings enabled by pre-computations, or techniques applicable only to $GF(2^n)$, or using the special form of the $p$ parameter (which allows speed-up of modular reduction $\bmod p$, but leave the number of operations in the base field unchanged).

  • $\begingroup$ The Ed25519 code (on a 255 bit curve) I'm using seems to need around 1500 squarings and 1500 additions to verify a signature. But it's 1) another signature algorithm 2) an edwards curve. | It uses Shamir's trick and some form of pre-computation, but no batch verification. $\endgroup$ Commented Jun 5, 2013 at 14:06
  • $\begingroup$ I'm talking about operations in the underlying field. In this case multiplication or squaring modulo $2^{255}-19$. I didn't count additions etc. since those are cheap. $\endgroup$ Commented Jun 5, 2013 at 17:05
  • $\begingroup$ @CodesInChaos: so that's 1500 squarings and 1500 multiplications in the base field. Makes sense. Thanks. $\endgroup$
    – fgrieu
    Commented Jun 5, 2013 at 18:18

1 Answer 1


Usually, the interleaving of wNAFs is faster than Shamir's trick for simultaneous point multiplication. Using interleaving with window sizes 5 (fixed) and 4 (random), the total number of operations is roughly (taken from Hankerson et al's Guide to ECC)

$(0.37t + 3)A + (t + 1)D$

where t is the bitlength of the scalars (which should be the same as the bitlength of the field size for standard curves), A is a mixed point addition (projective + affine) and D is a point doubling.

For standard prime curves with $a=-3$, using Jacobian coordinates, we have (from the EFD):

$A = 7M + 4S$,

$D = 3M + 5S$,

where $M$ is a field multiplication and $S$ is a field squaring. Therefore,

$M = (5.59t + 24)$,

$S = (6.48t + 17)$.

For the 128-bit level of security, if I got everything right, $t=256, M = 1455, S = 1675$.

  • $\begingroup$ I'll try to cross-check this (which is much easier than coming with it in the first place). And that's pretty similar to the values in this comment. Thanks! $\endgroup$
    – fgrieu
    Commented Jun 6, 2013 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.