A Binary Redundant Scalar Point Multiplication in Secure Elliptic Curve Cryptosystems

The main back-bone operation in elliptic curve cryptosystems is scalar point multiplication. The most frequently used method implementing the scalar point multiplication which is performed in the top level of GF (Galois Field) multiplication and GF division, has been the double-andadd algorithm, which is being recently challenged by NAF (Non-Adjacent Format) algorithm. In this paper, we propose a more efficient and novel approach of a scalar point multiplication method than existing double-and-add by applying redundant recoding which originates from radix-4 Booth’s algorithm. We call the novel algorithm quadand-add. Along with the algorithm, we have created a new EC (Elliptic Curve) point operation, named point quadruple, and verified with calculations of a real-world application to utilize it. Derived numerical expressions were verified using both C programs and HDL (Hardware Description Language). Proposed method of EC scalar point multiplication can be utilized in many EC security applications for handling efficient and fast calculations.