一种基于多基表示的标量乘扩展算法  

Extended Algorithm for Scalar Multiplication Based on MBNS

作　　者：李艳梅[1] 殷新春[1] 

机构地区：[1]扬州大学信息工程学院,江苏扬州225000

出　　处：《小型微型计算机系统》2017年第12期2699-2702,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61472343)资助;江苏省普通高校研究生科研创新计划项目(KYLX15_1362)资助

摘　　要：标量乘是椭圆曲线密码体制操作中最耗时、最主要的工作,所以椭圆曲线密码体制的快速实现问题的关键归结为椭圆曲线标量乘法的计算.为了提高椭圆曲线密码的效率,在已有的二进制域椭圆曲线标量乘算法的基础上,结合扩展系数集和半点运算方法,提出一种新的形如d(1/2)a3b5c7z的标量k的多基表示算法和相应的多基标量乘算法.在美国国家标准技术研究所推荐的椭圆曲线NIST B-163、NIST B-233和NIST B-283上进行实验,结果表明,新算法以增加少量预计算存储为代价,有效降低了算法复杂度,提高了标量乘算法的效率,使标量乘法的运算更高效.相比于相关工作,提高了约14.4%~41.4%.因此,新算法可以较好地应用到智能卡等计算资源、存储资源受限的领域中.Scalar multiplication is the most time-consuming and important work in the operation of elliptic curve cryptosystem, So the key point of the problem of the fast realization of the elliptic curve cryptosystem is the calculation of Scalar Multiplication of elliptic curves. In order to improve the efficiency of the elliptic curve cryptography, this paper proposes a new representation algorithm of a scalar k in the form of d （ 1/2） a 3b5c7z and multibase scalar multiplication algorithm relying on the representation. This representation is a combination of the method of Extended DBNS and point halving. In the United States National Institute of Standards and Technology recommended elliptic curve including NIST B-163, NIST B-233, NIST B-283, the experimental results show that the new approach can effectively reduce the complexity of the algorithm and improve the efficiency of scalar multiplication algorithm at the cost of a few pre-computations and storages, so that the scalar multiplication is more efficient. Compared to related work, the new approach is improved about 14.4% -41.4%. Therefore,the new algorithm can be applied to the domain of smart cards and other limited computing and storage resources.

关 键 词：椭圆曲线密码体制 标量乘 多基表示 半点运算 

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