基于预计算和周期性的ECC标量乘法算法

张晓强; 朱贵良; 王卫苹; 王蒙蒙

基于预计算和周期性的ECC标量乘法算法

1.
北京航空航天大学软件开发环境国家重点实验室, 北京 100191
2. 华北水利水电学院信息工程学院, 郑州 450011

详细信息

作者简介:
张晓强(1983-),男,河南内黄人,博士生,grayqiang@163.com.

中图分类号: TN 918.4
计量
- 文章访问数: 3089
- HTML全文浏览量: 156
- PDF下载量: 672
- 被引次数: 0
出版历程
- 收稿日期: 2010-07-02
- 网络出版日期: 2011-11-30

Scalar multiplication algorithm of ECC based on precomputation and periodicity

1.
State Key Lab of Software Development Environment, Beijing University of Aeronautics and Astronautics, Beijing 100191, China
2. Department of Information Engineering, North China University of Water Conservancy and Electric Power, Zhengzhou 450011, China

摘要

摘要: 在研究二进制、带符号的二进制(NAF,Non-Adjacent Form)等常见标量乘法算法的基础上,结合椭圆曲线基点的周期特性和预计算倍点序列方式,提出了一种新的标量乘法算法,并给出了新算法的详细步骤.点的周期性和系数决定了直接进行标量乘法运算还是转化为求其逆元,预计算倍点序列方式避免了椭圆曲线密码体制(ECC,Elliptic Curve Cryptosystem)加解密过程中大量的重复运算.为验证算法的正确性,采用密钥长度为192 bit椭圆曲线,给出了一个具体实例.实例结果和算法分析表明:与二进制和NAF算法相比,新算法虽占用了一些存储空间,但省去了倍点运算的时间开销,同时减少了点加的运算次数,极大地提高了标量乘法运算的效率.该算法的提出对完善ECC理论和加快ECC在实际中的应用具有重要意义.
- 椭圆曲线密码体制 /
- 二进制算法 /
- 带符号的二进制算法 /
- 标量乘法 /
- 预计算 /
- 周期性
Abstract: Based on the binary method, non-adjacent form (NAF) method, etc., a new scalar multiplication algorithm was proposed, which uses the periodicity of based point and the precomputation mean. Meanwhile, the steps of new algorithm were given. The periodicity of based point and the coefficient of scalar multiplication determine performing the operation of scalar multiplication directly or computing its inverse element. The precomputation mean can void a quantity of repeat computation during the encryption and decryption processes of elliptic curve cryptosystem (ECC). To verify the correctness of new algorithm, a concrete experiment was offered with an elliptic curve, whose key length is 192 bit. The experimental results and algorithm analyses show that comparing with binary and NAF methods, although the new algorithm requires a little extra space to store precomputed points, it does not need the operation of point doublings and reduces the operation times of point addition. Therefore, the new algorithm can improve the efficiency of scalar multiplication sharply. The research achievement is significant for completing the theory of ECC and accelerating its application in practice.
- elliptic curve cryptosystem(ECC) /
- binary method /
- non-adjacent form(NAF) method /
- scalar multiplication /
- precomputation /
- periodicity

HTML全文

参考文献(1)

[1] Yang Feng,Zhong Cheng,Yin Mengxiao,et al.Teaching cryptology course based on theory-algorithm-practice-application mode//Proceedings of the 1st International Workshop on Education Technology and Computer Science.Shanghai:Inst.of Elec and Elec Eng Computer Society,2009:468-470 [2] Koray K,Berkant U.Invalid-curve attacks on (hyper) elliptic curve cryptosystems[J].Advances in Mathematics of Communications,2010,4(3):307-321 [3] 祝跃飞,张亚娟.椭圆曲线公钥密码导引[M].北京:科学出版社,2006:129,219-223 Zhu Yuefei,Zhang Yajuan.Introduction of elliptic curve cyptosystem[M].Beijing:Science Press,2006:129,219-223(in Chinese) [4] Shah P G,Huang Xu,Sharma D.Sliding window method with flexible window size for scalar multiplication on wireless sensor network nodes//Proceedings of the 1st International Conference on Wireless Communication and Sensor Computing.New York:IEEE Computer Society,2010:1-6 [5] Katja S S,Olivier S,Tsuyoshi T.Analysis of fractional window recoding methods and their application to elliptic curve cryptosystems[J].IEEE Transactions on Computers,2006,55(1):48-57 [6] 赵佳,韩臻.自适应的椭圆曲线滑动窗口标量乘法[J].北京交通大学学报,2007,31(2):6-9 Zhao Jia,Han Zhen.Adaptive elliptic curve sliding window scalar multiplication algorithm[J].Journal of Beijing Jiaotong University,2007,31(2):6-9(in Chinese) [7] Shah P G,Huang Xu,Sharma D.lgorithm based on one's complement for fast scalar multiplication in ECC for wireless sensor network//Proceedings of the 24th International Conference on Advanced Information Networking and Applications Workshops.New York:IEEE Computer Society,2010:571-576 [8] Wu Keke,Li Dawei,Li Huiyun,et al.Partitioned computation to accelerate scalar multiplication for elliptic curve cryptosystems//Proceedings of the 15th International Conference on Parallel and Distributed Systems.New York:IEEE Computer Society,2009:551-555 [9] Miller V.Uses of elliptic curves in cryptography//Advances in Cryptology-Crypto'85.Berlin:Springer-Verlag,1985:417-426 [10] Koblitz N.Elliptic curve cryptosystems[J].Mathematics of Computation,1987,48(17):203-209 [11] Stinson D R.Cryptography theory and practice[M].3rd ed.London:Chapman & Hall/CRC Press Taylor & Francis Group,2006:257-258 [12] Diffie W,Hellman M E.New directions in cryptography[J].IEEE Transactions on Information Theory,1976,22(6):644-654 [13] 董付国,厉玉蓉.秦九韶算法思想在RSA密码算法中的应用研究[J].计算机工程与应用,2008,44(28):65-66 Dong Fuguo,Li Yurong.Study on Qin Jiushao algorithm and its application in RSA[J].Computer Engineering and Applications,2008,44(28):65-66(in Chinese)

施引文献

资源附件(0)

访问统计