A New Radix-4 Representation Based Multiple Scalar Multiplication Algorithm
Wei Wang · Microcomputer applications · 2008
Many elliptic curve based cryptographic protocols,such as ECDSA signature verification require computation of multiple scalar multiplications such as kP+IQ.Common methods to compute it are the Shamir method and the interleaving method whereas their speed mainly depends on the (joint) Hamming weight of the scalars.The common drawback of these algorithms is that they are based on the radix-2 representations.So no matter what recording is used,only the number of point addition (or subtraction) can be diminished,but the number of point doubling can not be diminished.In this paper,a new recoding method based on the radix-4 representation is proposed.A new radix-4 representation based scalar multiplication algorithm is given. This method adopts point quadruple instead of point doubling,and examines the integer from left to right (from the most significant digit to the least significant digit).This results in the merging of recoding and evaluation stages.So the proposed algorithm can improve the performance and reduce the memory consumption of scalar multiplication operation.