Implementing an efficient elliptic curve cryptosystem over $GF(p)$ on a smart card

Abstract

Elliptic curve cryptosystems (ECCs) are becoming more popular because of the reduced number of key bits required in comparison to other cryptosystems (for example, a 160 bit ecc has roughly the same security as 1024 bit RSA). ECCs are especially suited to smart cards because of the limited memory and computational power available on these devices. This paper discusses an optimized implementation of the elliptic curve Digital Signature Algorithm implemented over the field $GF(p)$ on a Motorola smart card. Algorithms for point addition, point doubling and scalar multiplication are compared according to their timings. The effects of different memory usage, code size and speed tradeoffs which were considered during the implementation are discussed. Also, optimized point addition and doubling algorithms are presented.