Improved Left-to-Right Scalar Multiplication Algorithms

概要

論文の詳細を見る
In 1987, Peter L. Montgomery proposed a left-to-right scalar multiplication algorithm to make the scalar multiplication on elliptic curve more efficient, called Montgomery Ladder, which uses only two registers such that it can be computed by using Co-Z coordinate addition formulae proposed by Raveen R. Goundar, M. Jove, and A. Miyaji in 2010. In Montgomery Ladder, we found a dummy operation in the last round of the main loop, so it maybe attacked by Safe-Error Attacks (SEA). We improve Montgomery Ladder to be secure to SEA without increasing memory amount. We also propose a form which is capable of using Co-Z coordinate addition formulae. In 2010, Raveen R. Goundar et al. proposed a new scalar multiplication algorithm which is named Signed-digit Method, which is based on the fact that all the odd numbers can be transformed into a non-zero signed-digit expansion. Therefore, their Signed-digit Method can be used for odd scalar only. We improve their signed-digit method by combining with the core idea of Montgomery Ladder to be available for both odd and even scalar.
2012-02-23