Efficient Scalar Multiplication And Side Channel Attacks On ECC

Elliptic curve cryptosystem (ECC), which is independently proposed by Miller and Koblitz, is based on the elliptic curve discrete logarithm problem (ECDLP). The basic operation of ECC is the scalar multiplication sP, where P is a point on elliptic curves and s is an integer.At CRYPTO 1991, Koblitz proposed the anomalous binary curves, on which the Frobenius endomorphism φ(x, y)=(x², y²) has negligible computational cost, to speed up scalar multiplication. At CRYPTO 1997, Solinas proposed the τ-NAF on Koblitz curves and reduced the Hamming weight of the scalar to n/3 over field F_2ⁿ, which is equivalent to the number of point additions needed in scalar multiplication. At PKC 2004, Avanzi et al combined the τ-NAF with one point halving and reduced the Hamming weight to 2?/7. At SAC 2006, Avanzi et al proposed the wide-double-NAF and its Hamming weight is about n/4.In this paper, we propose the wide-w-NAF using D:={0, ±1, ±(τ|-), ..., ±(τ|-)⁽(2^(?)-2))^-1)} for arbitrary w, which is a generalization of the wide-double-NAF, to further speed up scalar multiplication on Koblitz curves. A Lucas sequence is used to construct the algorithm for computing the wide-w-NAF, whose Hamming weight is n/(w+1). For n>110, the analysis shows that w=5 is the best and this method for scalar multiplication on Koblitz curves is at least 34%-47% faster than the τ-NAF method and 12%-37% faster on average than Avanzi's wide-double-NAF method without requiring additional memory. This brings some advantages, especially in the memory-constrained environments like smart card.Koblitz curves are a special family of binary curves on which scalar multiplication can be computed very efficiently. But when we implement the ECC on a smart card, side channel attack will be a serious threat. Side channel attacks monitor power consumption to reveal bits of a secret key d although d is hidden inside a smart card. Since Koblitz curves have some useful properties compared to the general curves, the implementation of scalar multiplication on Koblitz curves is different with the implementation on general curves. Then the attacks and countermeasures on Koblitz curves have their own characters. Though there are some attcks and countermeasures on Koblitz curves already, there still some problems. In this paper, how to use the doubling attack on Koblitz curves is discribed, and we show novel countermeasures resistant against RPA, ZPA, SPA and DPA on Koblitz curves. Then a randomized method against doubling attack is proposed by using point halving. The analysis shows that the algorithms for scalar multiplication on Koblitz curves in this paper are against to SCA and also effient.