一个新的基于radix-8的标量乘算法  

A New Radix-8 Representation Based Scalar Multiplication Algorithm

作　　者：程一飞[1] 陈文莉[1] 

机构地区：[1]安庆师范学院计算机系,安徽安庆246011

出　　处：《计算机技术与发展》2007年第10期155-157,161,共4页Computer Technology and Development

基　　金：安徽省教育厅自然科学研究项目(2006KJ079B)

摘　　要：椭圆曲线标量乘是椭圆曲线密码系统中最关键、最耗时的运算,因此如何快速高效实现标量乘运算是研究的重点。目前常见的标量乘算法有:double-and-add算法,NAF算法,MOF算法等,但它们都是基于radix-2编码表示的,无论采用何种编码,倍点运算的次数都不变,减少的只是点加(或点减)运算的次数。提出一个基于radix-8表示的新的编码方法,及一个基于radix-8表示的标量乘算法,通过用八倍点运算代替倍点运算,且编码是从左到右(即从最高位向最低位)进行,编码和主计算可以合并,提高实现效率并节省内存空间。实验结果表明,该算法较经典的double-and-add算法能够提高效率30%以上。The scalar multiplication dorninates the execution time of elliptic curve cryptngraphic schemes, so various methods have been studied to enhance the performance of this operation. The double- and- add algorithm, the NAF algorithm and the MOF algorithm etc are the frequently used methods implementing this operation, but the common drawhack of these algorithms is that they are based on the radix- 2 representations. So no matter what coding is used, only the number of point addition （or subtraction） can be diminished, but the number of point doubling can not be diminished. In this paper, a new coding method based on the radix - 8 representatioh is proposed. A new radix - 8 representation based scalar multiplication algorithm is given. This method adopts point octuple instead of point doubling, ＇and examines the integer from left to right （from the most significant digit to the least significant digit）. This results in the merging of coding and evaluation stages, So the proposed algorithm can improve the performance and reduce the memory consumption of scalar multiplication operation. The result of the experiment shows that more than 30% performance enhances over the algorithm using double - and - add method.

关 键 词：椭圆曲线密码系统 标量乘 radix-8表示 改进Booth算法 编码 

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