A FAST AND SECURE ELLIPTIC CURVE SCALAR MULTIPLICATION ALGORITHM OVER GF(p~m)

摘要

This paper presents an innovative method for accelerating the elliptic curve scalar multiplication algorithm over GF(p~m). The technique uses the substitution of multiplication with squaring and other cheaper operations by exploiting the fact that field squaring is generally less costly than multiplication. Applying this substitution to the traditional formulae, we obtain faster scalar multiplication in unprotected sequential implementations. We also show the significant impact our method has in protecting against simple side channel attacks(SSCA). We modify the ECC scalar multiplication to achieve a faster atomic structure when applying side channel atomicity protection. In contrast to previous atomic operations that assume squarings are indistinguishable from multiplications, our new atomic structure offers true SSCA-protection because it includes squaring in its formulation. In the scalar multiplication using NAF, our atomic blocks speed-up computation up to 30% in contrast to previous atomic implementations.