On fast elliptic curve multiplication resistant against side channel attacks

摘要

We enhance the efficiency of the Montgomery-type scalar multiplication for the standard elliptic curves over prime fields. The Montgomery-type scalar multiplication utilizes the addition formulae assembled by only x-coordinates, namely xECDBL and xECADD. We encapsulate the two addition formulae into one addition formula xECADDDBL, which accomplishes a faster computation because several auxiliary variables of two formulae can be shared. The efficiency improvement of the proposed scalar multiplication over the scheme without the encapsulation is about 11%. Moreover, we extend the proposed algorithm for the implementation over SIMD. Compared with the similar scheme proposed by Fischer et al., our scheme is about 16% faster.