Enhancement of {0, 1, 3}-NAF Recoding Algorithm using Block Method Technique for Elliptic Curve Cryptosystem

In mid 80s Neal Koblitz and Victor Miller independently proposed the use of elliptic curves in cryptography. Elliptic Curve Cryptosystem (ECC) is a type of public key cryptography (PKC) based on the algebraic structure of elliptic curve over finite fields. For a smaller key size, ECC is able to provide the same level of security with RSA. This feature made ECC one of the most popular PKC algorithms today. Scalar multiplication is known as the fundamental operation in ECC algorithm and protocols. The efficiency of ECC critically depends on the efficiency of the scalar multiplication operation. Scalar multiplication involves three levels of computations: scalar arithmetic, point arithmetic and field arithmetic. Improving the first two levels will lead to significant increment in the efficiency of the scalar multiplication. Scalar arithmetic level can be improved by employing an enhanced scalar recoding algorithm that can reduce the Hamming weight or decrease the number of operations in the scalar representation process. The objective of this research is to introduce an efficient implementation of {0,1, 3}-NAF scalar recoding algorithm by implementing block method. With block method application on the based algorithm, a complex look up table is undesired. Instead a fix look up table is introduced with less computation required for recoding. The proposed look up table contains equivalent value for 256 binary number in {0, 1, 3}-NAF representation. Each binary number in table is 8 bits length. Therefore, the input binary must be partitioned in n blocks of 8 bits before being processed through look up table. The running time is used to measure the performance of the based and the proposed algorithm. The focus of this research is on the enhancement of the scalar arithmetic level by designing and analysing an inexpensive {0, 1, 3}-NAF scalar recoding algorithm in an effort to maintain the Hamming weight for the based algorithm and reduce the algorithm complexity. In order to clearly demonstrate the running time difference between the based and the proposed algorithm, both algorithms performance time are measured and compared. The environment is controlled and there is no effect from the test bed, the running process has been repeated 5, 10 and 20 times. To enhance the reliability of results the average of each run has been calculated and used. The result from the input data yielded the following results: The proposed algorithm has overall 86% speed up in comparison to the base algorithm. In the proposed algorithm, partitioning function takes up to 74% and look up table takes up to 29% of the total elapsed time.

Preview PDF FSKTM 2015 8RR.pdf Download (1MB) | Preview

Actions (login required)

View Item