利用多基数系统的高效椭圆曲线多标量乘算法  

Efficient Algorithm for Multi-Scalar Multiplication of Elliptic Curves Using Multi-Base Number System

作　　者：尤文珠 葛海波 YOU Wenzhu;GE Haibo(School of Electronic Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710121,China)

机构地区：[1]西安邮电大学电子工程学院,西安710121

出　　处：《计算机工程》2021年第2期182-187,共6页Computer Engineering

基　　金：陕西省自然科学基金(2011JM8038);陕西省重点产业创新链(群)项目(S2019-YF-ZDCXL-ZDLGY-0098)。

摘　　要：针对椭圆曲线密码体制中标量乘与多标量乘运算耗时过长的问题,设计以2、3、7为基元的多基整数表示方法,并结合多基数系统(MBNS)及滑动窗口算法,提出基于MBNS滑动窗口(Sliding MBNS)和交错MBNS滑动窗口(I-MBNS)的多标量乘快速算法,分析并比较两种多标量乘快速算法在二元域和素域及不同窗口宽度下的平均运算量。实验结果表明,与Shamir和交错非邻接形式算法相比,Sliding MBNS和I-MBNS算法在标量长度为160 bit的二元域上的平均运算量分别减少了10.00%、1.69%和13.00%、4.97%,具有更低的运算复杂度和更高的标量乘算法效率。To address the time-consuming scalar multiplication and multi-scalar multiplication in Elliptic Curve Cryptography(ECC)system,this paper designs a multi-base integer representation method based on 2,3 and 7.On this basis,it combines Multi-Base Number System(MBNS)and sliding window algorithm to proposes two fast multi-scalar multiplication algorithms based on MBNS sliding window and interleaved MBNS sliding window,called Sliding MBNS and I-MBNS.The average computation amounts of two fast multi-scalar multiplication algorithms in the binary domain,prime domain and different window widths are analyzed and compared. Experimental results show that compared with the Shamir and interleaved Non-Adjacent Form(NAF) algorithm,Sliding MBNS and I-MBNS reduce the average computation amount by 10.0%,1.69% and13.00%,4.97% respectively on a binary field with a scalar length of160 bit.Their computational complexity is reduced,and the efficiency of the scalar multiplication algorithm is improved.

关 键 词：多标量乘 椭圆曲线密码 多基数系统 公钥密码体制 滑动窗口算法 

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