Elliptic Curve Scalar Point Multiplication Algorithm Using Radix-4 Booth’s Algorithm

Abstract

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 topmost level of GF multiplication and GF division, has been the double-and-add 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 multiplication method than the double-and-add by applying redundant recoding which originates from the radix-4 modified Booth’s algorithm. We call the novel algorithm quad-and-add. After deriving the algorithm, we created a new GF 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 elliptic curve scalar point multiplication can be utilized in many elliptic curve security applications for handling efficient and fast calculations.