|Table of Contents|

[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 Shuanggen1;  2;  Hu Yupu1
1Key Laboratory of Computer Network and Information Security of Ministry of Education, Xidian University, Xi’an 710071, China
2College of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, China
刘双根1;  2;  胡予濮1
1西安电子科技大学计算机网络与信息安全教育部重点实验室, 西安 710071; 2江西师范大学计算机信息工程学院, 南昌 330022
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.
为了抵抗椭圆曲线密码的边信道攻击, 提出了一种新型快速安全的标量乘算法.该算法是一种基于仅有点加运算的特殊加法链, 可自然地抵抗边信道攻击.此外, 提出在一种新型点加运算公式中引进特殊结构的加法链, 可以大大提高标量乘算法的运算效率.对于长度为160比特的整数, 其特殊加法链长度为260时, 仅仅需要1 719次乘法运算.特殊加法链长度为280~260时, 运行标量乘算法比倍点-点加算法效率上提高26%~31%, 比NAF算法快16%~22%, 比4-NAF算法快7%~13%, 比目前最好的方法双基链算法还要快1%~8%.

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.
Last Update: 2008-03-20