Paper 2006/313

Efficient Scalar Multiplication and Security against Power Analysis in Cryptosystems based on the NIST Elliptic Curves Over Prime Fields

Lars Elmegaard-Fessel

Abstract

In cryptosystems based on elliptic curves over finite fields (ECC-systems), the most time-consuming operation is scalar multiplication. We focus on the NIST elliptic curves over prime fields. An implementation of scalar multiplication, developed by IBM Danmark A/S for test purposes, serves as a point of reference. In order to achieve maximal efficiency in an ECC-system, one must choose an optimal method for scalar multiplication and the best possible coordinate representation for the curve being used. We perform an analysis of known scalar multiplication methods. This analysis contains a higher degree of detail than existing publications on the subject and shows that the NAF$_w$ scalar multiplication method with precomputations in affine coordinates, intermediate doublings in Jacobian coordinates and additions in mixed coordinates is the optimal choice. We compare our scalar multiplication scheme with the one implemented by IBM and conclude that a substantial improvement of efficiency is achieved by using our scheme. We implement our efficient scheme and support our conclusions with timings of the implementations. Side channel attacks using power analysis is considered to be a major threat against the security of ECC-systems. Mathematical countermeasures exist but reduce the performance of the system. So far, no comparison of the countermeasures has been published. We perform such a comparison and conclude that if a sufficient amount of storage is available, a combination of side channel atomicity and scalar randomization should be used as a countermeasure. If storage is limited, countermeasures should be based on a combination of Montgomery's ladder algorithm and scalar randomization. We specify side channel atomic elliptic curve operations on the NIST elliptic curves in mixed coordinates. So far, no such specifications have been published. We develop an efficient and secure scalar multiplication scheme and conclude that this scheme is more efficient than the scheme used in the IBM implementation, which provides no security against side channel attacks. We implement our efficient, secure scheme and support our conclusions with timings of the implementations.