基于Frobenius映射的快速标量乘算法  

Fast Scalar Multiplication Algorithm Based on Frobenius Mapping

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

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

出　　处：《计算机研究与发展》2008年第9期1561-1566,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60473012);国家"八六三"高技术研究发展计划基金项目(2007AA012448);江苏省"六大人才高峰"项目(06-E-025)~~

摘　　要：标量乘法的效率决定着椭圆曲线密码体制的性能，而Koblitz曲线上的快速标量乘算法是标量乘法研究的重要课题，在标量k的TNAF约简基础上，给出了一种基于Frobenius映射的上层运算：Comb算法．在预计算阶段，该算法利用Frobenius映射对宽度为r的序列计算其对应椭圆曲线上的点，从而建立预计算表，在累加赋值阶段结合约简后的TNAF（k）和预计算表来提高效率．Comb算法基于高效的Frobenius映射无须进行倍点运算，经过Comb矩阵的组合，其所需点加量是传统算法的1／5～1／4，当行数r任意时，其效率在任意坐标下比传统Comb算法提高至少67％．Elliptic curve cryptosystem（ECC） is a novel public key cryptosystem, which will be the primary standard for application in the future. The capability of ECC depends on the efficiency of scalar multiplication. Furthermore, fast scalar multiplication algorithm on Koblitz curve is the top demanding task in the research of scalar multiplication. After the reduction of TNAF（k）, a super operation algorithm based on Frobenius mapping is proposed, which is Comb algorithm. At precompute stage, in order to establish a pre-compute table, the algorithm calculates the coordinate of some points on elliptic curve corresponding to any sequence at a fixed length of r with the help of Frobenius mapping. On the other hand, at evaluation stage, the algorithm employs the reduction of TNAF（k） as well as the pre-compute table to improve the efficiency of the whole Comb algorithm. Because of high performance of Frobenius mapping, Comb algorithm doesn＇t relate to point doubling. And after arranging of Comb matrix, the quantity of point addition needed by the algorithm in this paper is 1/5-1/4 times of that needed by traditional algorithms. In addition, the efficiency of the algorithm is faster at least about 67% than the traditional Comb algorithm with arbitrary length of row in any coordinate.

关 键 词：椭圆曲线密码体制 标量乘法 KOBLITZ曲线 Frobenius映射 Comb算法 

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