TY - JOUR
T1 - Extended elliptic curve Montgomery ladder algorithm over binary fields with resistance to simple power analysis
AU - Cho, Sung Min
AU - Seo, Seog Chung
AU - Kim, Tae Hyun
AU - Park, Young Ho
AU - Hong, Seokhie
N1 - Funding Information:
This research was supported by the MSIP (Ministry of Science, ICT & Future Planning), Korea, under the C-ITRC (Convergence Information Technology Research Center) support program (NIPA-2013-H0301-13-3007) supervised by the NIPA(National IT Industry Promotion Agency).
PY - 2013/10/1
Y1 - 2013/10/1
N2 - In this paper, we propose a scalar multiplication algorithm on elliptic curves over GF(2m). The proposed algorithm is an extended version of the Montgomery ladder algorithm with the quaternary representation of the scalar. In addition, in order to improve performance, we have developed new composite operation formulas and apply them to the proposed scalar multiplication algorithm. The proposed composite formulas are 2P1 + 2P2, 3P1 + P2, and 4P1, where P 1 and P2 are points on an elliptic curve. They can be computed using only the x-coordinate of a point P = (x, y) in the affine coordinate system. However, the proposed scalar multiplication algorithm is vulnerable to simple power analysis attacks, because different operations are performed depending on the bits of the scalar unlike the original Montgomery ladder algorithm. Therefore, we combine the concept of the side-channel atomicity with the proposed composite operation formulas to prevent simple power analysis. Furthermore, to optimize the computational cost, we use the Montgomery trick which can reduce the number of finite field inversion operations used in the affine coordinate system. As the result, the proposed scalar multiplication algorithm saves at least 26% of running time with small storage compared to the previous algorithms such as window-based methods and comb-based methods.
AB - In this paper, we propose a scalar multiplication algorithm on elliptic curves over GF(2m). The proposed algorithm is an extended version of the Montgomery ladder algorithm with the quaternary representation of the scalar. In addition, in order to improve performance, we have developed new composite operation formulas and apply them to the proposed scalar multiplication algorithm. The proposed composite formulas are 2P1 + 2P2, 3P1 + P2, and 4P1, where P 1 and P2 are points on an elliptic curve. They can be computed using only the x-coordinate of a point P = (x, y) in the affine coordinate system. However, the proposed scalar multiplication algorithm is vulnerable to simple power analysis attacks, because different operations are performed depending on the bits of the scalar unlike the original Montgomery ladder algorithm. Therefore, we combine the concept of the side-channel atomicity with the proposed composite operation formulas to prevent simple power analysis. Furthermore, to optimize the computational cost, we use the Montgomery trick which can reduce the number of finite field inversion operations used in the affine coordinate system. As the result, the proposed scalar multiplication algorithm saves at least 26% of running time with small storage compared to the previous algorithms such as window-based methods and comb-based methods.
KW - Composite formulas
KW - Elliptic curve
KW - Montgomery ladder algorithm
KW - Side-channel atomicity
KW - Simple power analysis
UR - http://www.scopus.com/inward/record.url?scp=84880313577&partnerID=8YFLogxK
U2 - 10.1016/j.ins.2013.05.009
DO - 10.1016/j.ins.2013.05.009
M3 - Article
AN - SCOPUS:84880313577
SN - 0020-0255
VL - 245
SP - 304
EP - 312
JO - Information Sciences
JF - Information Sciences
ER -