一种改进的固定基点标量乘快速算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (10): 135-138.

一种改进的固定基点标量乘快速算法

王玉玺,张串绒,张柄虹

空军工程大学信息与导航学院西安710077;空军工程大学信息与导航学院西安710077;空军工程大学信息与导航学院西安710077

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(61272486)资助

Improved Fast Algorithm of Scalar Multiplication for Fix Base Point

WANG Yu-xi,ZHANG Chuan-rong and ZHANG Bing-hong

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 对于固定基点的标量乘法,LLECC算法具有很高的计算效率,但是预计算量大、存储空间要求高限制了算法的应用。采用基于窗口的非相邻编码方法对标量k编码并按照新的排列方式得到系数矩阵后,利用编码方法的稀疏特性便可降低算法的存储量；为解决新的编码方式下增加的倍点计算,利用二进制有限域上计算效率较高的半点计算代替一般的倍点运算,从而提高改进算法的计算效率。对比分析显示,在标量长度为160bit、编码窗口宽度为4bit等相同条件下,改进算法与原算法相比计算效率提高了12.4%,存储量降低了53.3%。

关键词: 椭圆曲线,标量乘,半点运算,基于窗口的非相邻编码

Abstract: For the scalar multiplication of a fix base point,the algorithm of LLECC has a good performance in efficiency,however the huge amount of precomputation and storage restrict its application．Through a new arrangement of the coefficient matrix in which the scalar k is recoded in the non-adjacent form based on the window,the storage can be reduced with the sparse property of the encoding method．When the length of the scalar is 160bit and the window’s width is 4bit,the improved algorithm can reduce 12.4% and 53.3% in the aspect of the computational complexity and storage cost,compared with the original LLECC algorithm.

Key words: Elliptic curve,Scalar multiplication,Point halving,NAF-w

王玉玺,张串绒,张柄虹. 一种改进的固定基点标量乘快速算法[J]. 计算机科学, 2013, 40(10): 135-138. https://doi.org/

WANG Yu-xi,ZHANG Chuan-rong and ZHANG Bing-hong. Improved Fast Algorithm of Scalar Multiplication for Fix Base Point[J]. Computer Science, 2013, 40(10): 135-138. https://doi.org/

参考文献

[1] Koblitz N．Elliptic curve cryptosystems[J]．Mathematics ofcomputation,1987(48):203-209
[2] Miller V S．Use of elliptic curves in cryptography[C]∥Procee-dings of CRYPTO’85.LNCS 218,Springer,1986:417-426
[3] Lim C H,Lee P J．More flexible exponentation with precomputation Advances in Cryptology[C]∥Crypto’94．Springer-Verlag,Berlin,1994:95-107
[4] Yang W C,Lin K M,Laih C S．A precomputation method for elliptic curve point multiplication[J]．Journal of the Chinese Institute of Electrical Engineering,2002,9(4):339-344
[5] Lo G W．The study and implementation on elliptic curve digital signature schemes[D]．Taiwan,NCKU,2000
[6] Fong K,Hankerson D,Lopez J,et al．Field inversion and point halving revisited [J].IEEE Transactions on Computers,2004,53(8):1047-1059
[7] Hankerson D,Menezes A,Vanstone S．Guide to Elliptic Curve Cryptography[J]．Computer Reviews,2005,6(1):13-23
[8] Digital Signature Standard(DSS),FIPS 186-2[S]．USA:Federal Information Processing Standards Publication 186-2,National Institute of Standards and Technology,2000
[9] 白羽,范恒英．一种改进的椭圆曲线标量乘的快速算法[J].西南科技大学学报,2011,9
[10] Pang Shi-chun,Tong Shou-yu,Cong Fu-zong,et al．An Efficient Elliptic Curve Scalar Multiplication Algorithm Against Side Channel Attacks[C]∥Proceedings of the 2010International Conference on Computer,Mechatronics,Control and Electronic Engineering(CMCE2010)．Springer-Verlag,Berlin:2010:361-364
[11] 张建．GF(2ⁿ)上椭圆曲线标量乘法快速算法的研究[D]．呼和浩特:内蒙古大学,2012
[12] 周梦,周海波.椭圆曲线快速点乘算法优化[J].计算机应用研究,2012,9(8):3056-3058
[13] 李忠,彭代渊.基于滑动窗口技术的快速标量乘法[J].计算机科学,2012,9(6A):54-57

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed