n-bit NAF recoded scalar is n/3, and an exhaustive search among the 2n/3 candidates is required. This paper shows that in a left-to-right NAF recoded or a left-to-right 2-bit sliding window manipulated scalar the relative position of nonzero bits will reveal their values. Our analysis skill reduces the number of candidates of the scalar from the naive search of 2n/3 to 22n/9 and 20.19n respectively for the cases of NAF and sliding window method." />
Nothing Special   »   [go: up one dir, main page]

On the Computational Sequence of Scalar Multiplication with Left-to-Right Recoded NAF and Sliding Window Technique

Chien-Ning CHEN
Sung-Ming YEN
SangJae MOON

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A    No.10    pp.1806-1812
Publication Date: 2010/10/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.1806
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Keyword: 
elliptic curve scalar multiplication,  exponentiation algorithm,  non-adjacent form,  simple power analysis,  sliding window recoding,  

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


Summary: 
Simple power analysis (SPA) can be employed in examining the power consumption trace of elliptic curve scalar multiplication to retrieve the computational sequence. However, SPA cannot distinguish point addition from point subtraction. The attacker still requires an exhaustive search to recover the private key when it is recoded in NAF or recoded by the 2-bit sliding window method. The average Hamming weight of an n-bit NAF recoded scalar is n/3, and an exhaustive search among the 2n/3 candidates is required. This paper shows that in a left-to-right NAF recoded or a left-to-right 2-bit sliding window manipulated scalar the relative position of nonzero bits will reveal their values. Our analysis skill reduces the number of candidates of the scalar from the naive search of 2n/3 to 22n/9 and 20.19n respectively for the cases of NAF and sliding window method.

open access publishing via