Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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. –  CodesInChaos Jun 5 '13 at 14:06
    
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. –  CodesInChaos Jun 5 '13 at 17:05
    
@CodesInChaos: so that's 1500 squarings and 1500 multiplications in the base field. Makes sense. Thanks. –  fgrieu Jun 5 '13 at 18:18
add comment

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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! –  fgrieu Jun 6 '13 at 17:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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