This paper presents a scalar multiplication method for Koblitz curves. Koblitz curves are elliptic curves where the scalar multiplication can be computed in a much faster way than with other curves, allowing designs and implementations without arithmetic coprocessor. The new method is as fast as the fastest known techniques on Koblitz curves but requires much less memory; therefore, it is of particular interest for environments with low resources. Our technique is well suited for both hardware and software implementations. In hardware, we show that a normal basis implementation reduces memory consumption by 85 percent compared to conventional methods, but this still has exactly the same computational cost. In software, thanks to a mixed normal-polynomial bases approach, our technique allows memory savings up to 70 percent and, depending on the instruction set of the CPU, can be as fast as the fastest known scalar multiplication methods or can even beat them by a large margin. Therefore, in software and in hardware, our scalar multiplication technique offers high performance without sacrifice in view of memory.

We show that the advanced version of the randomized addition-subtraction chains countermeasure against side channel attacks is vulnerable to a multiple power analysis attack, a new kind of side channel attack, under distinguishability between addition and doubling. The side channel attack takes advantage of information leaked during execution of a cryptographic procedure. The randomized addition-subtraction chains countermeasure was proposed by E. Oswald and M. Aigner (see Lect. Notes in Comp. Sci., vol.2162, p.39-50, 2001), and is based on a random decision inserted into computations. The countermeasure has two versions; the basic version and the advanced version. The basic version has been proved to be vulnerable to a side channel attack. This is due to a shrinkage of states for randomization if a bit of the secret scalar is zero. However, the advanced version does not have such a shrinkage. The multiple power analysis uses plural AD sequences, which are sequences of additions and doublings, and obtained by the distinguishability and measurements. The multiple power analysis relates the AD sequences to each other, and deduces the secret scalar. A point of the multiple power analysis against the advanced version is that two different states are combined, and regarded as the same state. This provides a shrinkage of states if a bit of the secret scalar is zero.