On the performance of signature schemes based on elliptic curves

This paper describes a fast software implementation of the elliptic curve version of DSA, as specifled in draft standard documents ANSI X9.62 and IEEE P1363. We did the implementations for the flelds GF(2n), using a standard basis, and GF(p). We discuss various design decisions that have to be made for the operations in the underlying fleld and the operations on elliptic curve points. In particular, we conclude that it is a good idea to use projective coordinates for GF(p), but not for GF(2n). We also extend a number of exponentiation algorithms, that result in considerable speed gains for DSA, to ECDSA, using a signed binary representation. Finally, we present timing results for both types of flelds on a PPro-200 based PC, for a C/C++ implementation with small assembly-language optimizations, and make comparisons to other signature algorithms, such as RSA and DSA. We conclude that for prac- tical sizes of flelds and moduli, GF(p) is roughly twice as fast as GF(2n). Furthermore, the speed of ECDSA over GF(p) is similar to the speed of DSA; it is approximately 7 times faster than RSA for signing, and 40 times slower than RSA for veriflcation (with public exponent 3).