Efficient Comb Elliptic Curve Multiplication Methods Resistant to Power Analysis

Elliptic Curve Cryptography (ECC) has found wide applications in smart cards and embedded systems. Point multiplication plays a critical role in ECC. Many efficient point multiplication methods have been proposed. One of them is the comb method [5] which is much more efficient than other methods if precomputation points are calculated in advance or elsewhere. Unfortunately, many efficient point multiplication methods including the comb method are vulnerable to power-analysis attacks. Various algorithms to make elliptic curve point multiplication secure to power-analysis attacks have been proposed recently, such as the double-and-add-always method [8], Moller's window method [17, 18], Okeya et al.'s odd-only window method [21, 22], and Hedabou et al.'s comb method [19]. In this paper, we first present a novel comb recoding algorithm which converts an integer to a sequence of signed, odd-only comb bit-columns. Using this recoding algorithm, we then present several comb methods, both Simple Power Analysis (SPA)-nonresistant and SPA-resistant, for point multiplication. These comb methods are more efficient than the original SPA-nonresistant comb method and Hedabou et al.'s SPA-resistant comb method. Our comb methods inherit the advantage of a comb method, running much faster than Möller's window method and Okeya et al.'s odd-only window method, as well as other window methods such as the efficient signed m-ary window method, if only the evaluation phase is taken into account. Combined with randomization projective coordinates or other randomization techniques and certain precautions in selecting elliptic curves and parameters, our SPA-resistant comb methods are resistant to all power-analysis attacks.