Efficient Scalar Multiplication on Montgomery-Form Elliptic Curves

Yuichi FUTA  Motoji OHMORI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.8   pp.2126-2136
Publication Date: 2004/08/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
elliptic curve,  Montgomery-form elliptic curve,  scalar multiplication,  fixed point,  

Full Text: PDF(503.6KB)>>
Buy this Article

Montgomery-form elliptic curves have the advantage of faster arithmetic than Weierstrass-form elliptic curves. The dominant operation of the Elliptic Curve Cryptosystem (ECC) is scalar multiplication of points on an elliptic curve, and it usually includes scalar multiplication of a fixed base point of ECC. For Weierstrass-form elliptic curves, accelerating methods of scalar multiplication by using a pre-computed table of the fixed point have been widely studied. However, such methods cannot naturally expand to Montgomery-form elliptic curves. In this paper, we propose a fast scalar multiplication method on Montgomery-form elliptic curves by using a pre-computed table for the first time. Our method is 1.6 times as fast as the known method for Montgomery-form elliptic curves under the practical conditions that the size of the definition field is 160 bits and the memory size used for the pre-computed table is 3.2 KB.