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.

In the execution on a smart card, elliptic curve cryptosystems have to be secure against side channel attacks such as the simple power analysis (SPA), the differential power analysis (DPA), and the refined power analysis (RPA), and so on. MMM-algorithm proposed by Mamiya, Miyaji, and Morimoto is a scalar multiplication algorithm secure against SPA, DPA, and RPA, which can decrease the computational complexity by increasing the size of a pre-computed table. However, it provides only 4 different cases of pre-computed tables. From the practical point of view, a wider range of time-memory tradeoffs is usually desired. This paper generalizes MMM-algorithm to improve the flexibility of tables as well as the computational complexity. Our improved algorithm is secure, efficient and flexible for the storage size.