椭圆曲线底层域快速算法的优化

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (22): 115-118.

椭圆曲线底层域快速算法的优化

赖忠喜，张占军

台州职业技术学院机电工程学院，浙江台州 318000

出版日期:2015-11-15 发布日期:2015-11-16

Optimizing fast field operation in elliptic curves

LAI Zhongxi, ZHANG Zhanjun

College of Mechanical and Electrical Engineering, Taizhou Vocational Technical, Taizhou, Zhejiang 318000, China

Online:2015-11-15 Published:2015-11-16

摘要/Abstract

摘要： 为了提高椭圆曲线底层域运算的效率，基于将乘法转换为平方运算的思想，提出在素数域[FP]上用雅克比坐标直接计算[2kP]和[3kP]的改进算法，其运算量分别为[(3k-1)M+(5k+3)S]和[(6k-1)M+(9k+3)S]，与DIMITROY和周梦等人所提的算法相比，算法效率分别提升了6.25%和5%。另外，利用相同的原理，给出了素数域[FP]上用在仿射坐标系直接计算[3kP]的改进算法，其运算量为[I+(6k+1)M+(9k+1)S]，与周梦和殷新春等人所提的算法相比，效率分别提升了3.4%和24%。

关键词: 椭圆曲线密码体制, 标量乘法, 底层域运算, 仿射坐标, 雅克比坐标

Abstract: To raise the efficiency of field operation on elliptic curve, based on the idea of trading multiplications for squares, two modified algorithms are proposed to compute 4P and 5P directly over prime field [FP] in terms of affine coordinates, their computational complexity are[(3k-1)M+(5k+3)S] and[(6k-1)M+(9k+3)S] respectively, which are improved to 6.25% and 5% respectively than those of Dimitroy’s and Zhou meng’s method. Moreover, using the same idea, an improved method is given to compute [3kP] directly in terms of affine coordinates, its computational complexity is [I+(6k+1)M+(9k+1)S], and the efficiency of the new method is improved to 3.4% and 24% respectively than those of Zhong meng’s and Yin xin-chun’s method.

Key words: elliptic curve cryptosystem, scalar multiplication, field operation, affine coordinate, jacobian coordinate

赖忠喜，张占军. 椭圆曲线底层域快速算法的优化[J]. 计算机工程与应用, 2015, 51(22): 115-118.

LAI Zhongxi, ZHANG Zhanjun. Optimizing fast field operation in elliptic curves[J]. Computer Engineering and Applications, 2015, 51(22): 115-118.

[1]	刘双根1，姚华童1，李发根2. Edwards曲线上抗SPA快速标量乘算法[J]. 计算机工程与应用, 2017, 53(1): 103-106.
[2]	李明. 新的适用于WSN网络的双方认证密钥协商协议[J]. 计算机工程与应用, 2016, 52(3): 100-102.
[3]	赖忠喜，张安洁，张占军. 椭圆曲线中一种计算7P和7kP的改进算法[J]. 计算机工程与应用, 2016, 52(1): 29-32.
[4]	赖忠喜，林君焕，张占军. 素数域[GF(P)]上椭圆曲线快速标量乘算法的研究[J]. 计算机工程与应用, 2015, 51(4): 100-104.
[5]	赖忠喜，张占军，陶东娅. 椭圆曲线底层域快速算法的研究[J]. 计算机工程与应用, 2014, 50(3): 67-70.
[6]	乔晓林，张建中. 基于ECC的多组织间的多级秘密共享方案[J]. 计算机工程与应用, 2011, 47(20): 56-57.
[7]	徐凯平1，郑洪源1，刘锦峰2，顾晶晶1. 椭圆曲线密码体制中快速标量乘方法研究[J]. 计算机工程与应用, 2011, 47(15): 112-115.
[8]	童莲，钱江. 椭圆曲线中抗SPA和DPA攻击标量乘算法研究[J]. 计算机工程与应用, 2010, 46(35): 72-74.
[9]	张鑫平,俞龙江,孙圣和. 基于身份的门限多重盲签名方案[J]. 计算机工程与应用, 2009, 45(15): 115-117.
[10]	王建峰,孟涛,孙圣和. 椭圆曲线有序多重签名中阈下信道及封闭方法[J]. 计算机工程与应用, 2009, 45(14): 79-80.
[11]	刘连浩¹,申勇^1,2. Koblitz椭圆曲线标量乘法的二次研究[J]. 计算机工程与应用, 2008, 44(4): 141-144.
[12]	殷新春,侯红祥. 一种定点快速标量乘算法的优化[J]. 计算机工程与应用, 2008, 44(4): 80-82.
[13]	刘文波,张帆,郭云飞,刘力雄. F₂^m域椭圆曲线密码系统软件实现的优化技术研究[J]. 计算机工程与应用, 2008, 44(19): 28-30.
[14]	王旭,钱雪忠. 一个标准模型下可证明安全的无证书签名方案[J]. 计算机工程与应用, 2008, 44(11): 129-132.
[15]	程艳傅鹂陈承源向宏胡海波. 基于椭圆曲线密码体制的XML盲签名方案[J]. 计算机工程与应用, 2007, 43(7期): 163-166.