Optimizing {0, 1, 3}-NAF Recoding Algorithm Using Block-Method Technique in Elliptic Curve Cryptosystem

Abstract

The most expensive and time-consuming operation in Elliptic curve cryptosystem is scalar multiplication operation. Optimization of scalar multiplication will substantially enhance the ECC performance. Scalar multiplication can be improved by using an enhanced scalar recoding algorithm that can decrease the number of operations in the scalar representation process. The objective of this research is to introduce an efficient design and implementation of {0,1,3}-NAF scalar recoding algorithm by applying block method technique. The base algorithm has a complex look up table. With block method application on base algorithm, a complex look up table is undesired. Instead a fix look up table is introduced with less computation required for recoding. The Big-O notation is used to measure the complexity and (µs) used to evaluate the running time of base and proposed algorithm.