[1] Liu Shuanggen, Hu Yupu,. Fast and secure elliptic curve scalar multiplication algorithmbased on special addition chains [J]. Journal of Southeast University (English Edition), 2008, 24 (1): 29-32. [doi:10.3969/j.issn.1003-7985.2008.01.007]

Copy

Fast and secure elliptic curve scalar multiplication algorithmbased on special addition chains()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

24

Issue:

2008 1

Page:

29-32

Research Field:

Computer Science and Engineering

Publishing date:

2008-03-30

Info

Title:

Fast and secure elliptic curve scalar multiplication algorithmbased on special addition chains

Author(s):

Liu Shuanggen¹;  2;  Hu Yupu¹

¹Key Laboratory of Computer Network and Information Security of Ministry of Education, Xidian University, Xi’an 710071, China
²College of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, China

Keywords:

scalar multiplication algorithm;  special addition chains;  side channel attacks;  double base chain

PACS:

TP301

DOI:

10.3969/j.issn.1003-7985.2008.01.007

Abstract:

To resist the side channel attacks of elliptic curve cryptography, a new fast and secure point multiplication algorithm is proposed.The algorithm is based on a particular kind of addition chains involving only additions, providing a natural protection against side channel attacks.Moreover, the new addition formulae that take into account the specific structure of those chains making point multiplication very efficient are proposed.The point multiplication algorithm only needs 1 719 multiplications for the SAC260 of 160-bit integers.For chains of length from 280 to 260, the proposed method outperforms all the previous methods with a gain of 26% to 31% over double-and add, 16% to 22% over NAF, 7% to 13% over 4-NAF and 1% to 8% over the present best algorithm—double-base chain.

References:

[1] Miller Victor S.Uses of elliptic curves in cryptography[C]//Advances in Cryptology—CRYPTO’85, Lecture Notes in Computer Sciences.Springer-Verlag, 1986:417-428.
[2] Koblitz Neal.Elliptic curve cryptosystems [J].Mathematics of Computation, 1987, 48(177):203-209.
[3] Avanzi Roberto M, Cohen Henri, Doche Christophe, et al.Handbook of elliptic and hyperelliptic curve cryptography[M].Boca Raton, FL, USA: Chapman and Hall/CRC Press, 2005.
[4] Hankerson Darrel, Menezes Alfred J, Vanstone Scott.Guide to elliptic curve cryptography[M].Springer-Verlag, 2004.
[5] Montgomery P L.Speeding the Pollard and elliptic curve methods of factorization [J].Mathematics of Computation, 1987, 48(177):143-264.
[6] Okeya Katsuyuki, Sakurai Kouichi.Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form elliptic curve[C]//Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science.Springer-Verlag, 2001, 2162:126-141.
[7] Kocher P C.Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems[C]//Advances in Cryptology—CRYPTO’96, Lecture Notes in Computer Sciences.Springer-Verlag, 1996:104-113.
[8] Kocher P C, Jaffe J, Jun B.Differential power analysis[C]//Advances in Cryptology—CRYPTO’99, Lecture Notes in Computer Sciences. Springer-Verlag, 1999:388-397.
[9] Chevallier-Mames Benoit, Ciet Mathieu, Joye Marc.Low-cost solutions for preventing simple side-channel analysis:side-channel atomicity [J].IEEE Transactions on Computers, 2004, 53(6):760-768.
[10] Knuth Donald E.The art of computer programming:fundamental algorithms [M].Addison-Wesley, 1981.
[11] Dimitrov Vassil, Imbert Laurent, Mishra Pradeep Kumar.Efficient and secure elliptic curve point multiplication using double-base chains[C]//11th International Conference on the Theory and Application of Cryptology and Information Security, Lecture Notes in Computer Sciences.Springer-Verlag, 2005, 3788:59-78.

Memo

Memo:

Biographies: Liu Shuanggen(1979—), male, graduate;Hu Yupu(corresponding author), male, doctor, professor, yphu@mail.xidian.edu.cn.
Foundation item: The National Natural Science Foundation of China(No.60473029, 60673072).
Citation: Liu Shuanggen, Hu Yupu.Fast and secure elliptic curve scalar multiplication algorithm based on special addition chains[J].Journal of Southeast University(English Edition), 2008, 24(1):29-32.

Common functions