计算椭圆曲线上多标量乘的快速算法  

A New Algorithm of Elliptic Curve Multi-Scalar Multiplication

作　　者：刘铎[1] 戴一奇[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》2008年第7期1131-1137,共7页Chinese Journal of Computers

基　　金：国家自然科学基金项目(90304014)资助

摘　　要：椭圆曲线密码体制最主要的运算就是椭圆曲线上的标量乘和多标量乘,在各种密码协议中起到了核心作用.文中设计了多个整数的一种新的联合带符号二进制表示的编码算法,它每次最多处理相邻的两列,因此在实现上是简单而快速的;在此基础上提出了计算椭圆曲线上多标量乘的一个新算法,并对这个算法进行了分析,最后将新算法和已有多标量乘算法进行了比较,指出新算法在一般情况下(m3时)效率可提高7%～15%.The main operations of elliptic curve cryptosystem are scalar multiplication and multiscalar multiplication for a pair of integers. In this paper, a new encoding algorithm, which transforms multiple integers into a new kind of signed binary representation of them, is presented. The new encoding algorithm needs only to handle two adjacent columns, and thus is fast and easy to implement. Using this new kind of joint signed binary expressions, a new elliptic curve multiscalar multiplication algorithm is proposed. The analysis about its time complexity is given, and the comparisons of traditional methods and the new method are also presented, based on which the authors draw the conclusion that the new multi-scalar multiplication algorithm requires about 7% to 15% less running time than the known ones.

关 键 词：密码学 椭圆曲线 多标量乘 联合带符号二进制表示 

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