基于双基链的快速标量乘算法研究  

Research on Fast Scalar Multiplication Algorithm Based on Double-Base Chain

作　　者：武永波[1] 彭青松[1] 高茂庭[1] 

机构地区：[1]上海海事大学信息工程学院,上海201306

出　　处：《现代计算机（中旬刊）》2016年第10期3-10,共8页Modern Computer

摘　　要：在有限域GF（2~m）上,实现椭圆曲线密码体制（ECC）中关键运算是标量乘算法,该算法也是椭圆曲线密码体制中耗时最长、极易受到攻击的运算之一。为了提高椭圆曲线密码算法计算的安全性和效率性,从分析以2、3为底的双基链椭圆曲线标量乘特点出发,在现在有的双基链算法基础之上,提出一种新的快速标量乘算法。新算法中,通过应用米勒算法和2-3链相结合的方法,寻找出权重更小的双基链。此外,考虑到小权重也有其局限性。引入了技术Tate配对与2-3链相结合来提高算法效率,比基于贪心算法的双基链更加高效。经仿真实验比较分析和研究,表明该改进算法可以很好提高计算效率,并且同时能大大降低存储量。In order to improve the security of elliptic curve cryptographic algorithms and efficiency of the existing side-channel attacks and scalar multiplication algorithm on the basis of a new scalar multiplication algorithm is proposed.Scalar multiplication is the elliptic curve cryptosystem（ECC） of the basic operation, is also one of the most time-consuming and vulnerable to attack. Elliptic curve scalar multiplication, 2-3 double-base chain represents an integer N, can improve the efficiency of the scalar multiplication. In a scalar Multiplication algorithm, to find the optimal 2-3 double-base chain will takes longer than scalar multiplication itself, the cost of pay more. New algorithm, the application of Tate pairing and 2-3 chain combination, to find out better 2-3 chain. In addition, than 2-3 chain based on greedy algorithm. Simulation results show that the improved algorithm can reduce the storage with improving the calculation efficiency.

关 键 词：椭圆曲线密码体制 标量乘法 双基数系统 TATE配对 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]