基于折半运算的快速双基数标量乘算法  

Fast DBNS scalar multiplication algorithm based on halving operation

作　　者：殷新春[1,2] 赵荣[1] 侯红祥[1] 谢立[2] 

机构地区：[1]扬州大学信息工程学院,江苏扬州225009 [2]南京大学计算机软件新技术国家重点实验室,南京210093

出　　处：《计算机应用》2009年第5期1285-1288,1292,共5页journal of Computer Applications

基　　金：国家863计划项目(2007AA0124487);国家自然科学基金资助项目(60473012);江苏省六大人才高峰资助项目(06-E-025)

摘　　要：为了提高椭圆曲线标量乘法效率,对二元域上椭圆曲线的基于双基数的标量乘法进行改进。在底层域推导出直接计算3kP的快速算法,该算法只需一次求逆;新设计的以1/2和3为基的双基数编码可结合高效的直接计算3kP和折半运算,基于该双基数编码的标量乘算法只涉及到点加运算、折半运算、三倍点和直接计算3kP,底层域运算复杂性得到降低,在NIST推荐的椭圆曲线上比Dimitrov算法效率提高70%以上,比Wong方法提高10%以上。To raise the efficiency of scalar multiplication on elliptic curve, a scalar multiplication algorithm based on double base number system over binary field was improved. Firstly a fast direct computing 3^kP algorithm in field was deduced, which only needed one inversion; the new double base number chain based on 1/2 and 3 could be integrated with high-speed direct computing 3^kP and halving algorithm. Scalar multiplication based on the new chain only employed point addition, halving algorithm, triplication and direct computing 3^kP. Thus the complexity was depressed and the efficiency was improved about 70% over Dimitrov algorithm and about 10% over Wong method on the elliptic curves recommended by NIST.

关 键 词：椭圆曲线密码体制 标量乘法 双基数系统 折半算法 

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