基于w-NNAF的快速Edwards曲线标量乘法  

Fast Scalar Multiplication on Edwards Curves Based on w-NNAF

作　　者：贺毅朝[1] 寇应展[2] 曲文龙[1] 

机构地区：[1]石家庄经济学院信息工程学院,石家庄050031 [2]军械工程学院计算机工程系,石家庄050003

出　　处：《计算机科学》2010年第11期70-74,共5页Computer Science

基　　金：863国家基金项目(2007AA01Z454);河北省科学技术研究与发展指导计划项目(07216926)资助

摘　　要：在分析利用Edwards曲线上三倍点公式计算3nP(n=1,2,…)的基础上,根据各3nP的坐标具有统一表示形式的特性,提出了一种通过减少求逆运算而快速计算3nP(n=2,3…)的新算法Tripling_Algorithm,并将此算法与标量k的w-NNAF表示方法相结合,给出了一种计算标量乘法kP的高效算法ImprovedSM-3-NNAF。通过对ImprovedSM-3-NNAF的计算复杂性与安全性分析表明,利用该算法计算kP不仅是安全的,而且至少可节约20.78%的计算量,大大改进了Edwards曲线上标量乘法的计算效率。Based on analysing and using the triple formula of Edwards curve to calculate 3nP（n=1,2,…）,according to circumstances that the coordinate of every 3nPhave the unitive representation,we put forward a new algorithm Tripling-Algorithm which can quickly compute 3nP（n=2,3…）by reducing inverse operation.And combining this algorithm with the w-NNAF representation with scalar k,we gave a kind of highly efficient algorithm ImprovedSM-3-NNAF to calculate scalar multiplication kP（for short ImprovedSM-3-NNAF）.The analysis of the complexity and security of the Improved SM-3-NNAF shows that not only calculating kPby using this algorithm is security,but also it can save the amount of calculation by at least 20.78%,and has greatly improved the computational efficiency of the scalar multiplication in Edwards curve.

关 键 词：椭圆曲线密码 标量乘法 Edwards曲线 三倍点公式 w-NNAF 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]