Abstract:

Based on the Akishita’s idea of computing scalar multiplication kP+lQ on elliptic curve with Montgomery form, we propose a new algorithm to reduce the computation for scalar multiplication kP+lQ+tR by 23%.We then propose a subsection method on the basis of the above two algorithms to enhance the efficiency of computing scalar multiplication bP on elliptic curve by converting bP to kP+lQ or kP+lQ+tR, which combines the concept of sidechannel atomicity to resist SPA attacks. Simulations on Magma demonstrate that the twosegmentation algorithm is the fastest and the threesegmentation algorithm is the second, and they can both greatly improve the efficiency in comparison with the original Montgomery algorithm.

Key words: elliptic curve, scalar multiplication, Montgomery algorithm, segmentation, SPA