A Flexible Approach for Efficient Elliptic Curve Multi-Scalar Multiplication on Resource-constrained Devices
Seo Seogchung, Hyung-Chan Kim, R. S. Ramakrishna · Information Security and Cryptology · 2006
Elliptic Curve Cryptosystem (ECC) is suitable for resource-constrained devices such as smartcards, and sensor motes because of its short key size. This paper presents an efficient multi-scalar multiplication algorithm which is the main component of the verification procedure in Elliptic Curve Digital Signature Algorithm (ECDSA). The proposed algorithm can make use of a precomputed table of variable size and provides an optimal efficiency for that precomputed table. Furthermore, the given scalar is receded on-the-fly so that it can be merged with the main multiplication procedure. This can achieve more savings on memory than other receding algorithms. Through experiments, we have found that the optimal sizes of precomputed tables are 7 and 15 when uP+vQ is computed for u, v of 163 bits and 233 bits integers. This is shown by comparing the computation time taken by the proposed algorithm and other existing algorithms.