In ECDSA, how many field operations are used for signature verification?

Question

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).

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$.