一个新的基于MOF从左到右编码的多标量乘算法  

A New Mutual Opposite Form Based Left-to-Right Multi-Scalar Multiplication Algorithm

作　　者：程一飞[1] 

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

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

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

摘　　要：很多基于椭圆曲线的密码协议都需要计算多标量乘法kP+lQ。目前常见的多标量乘算法的效率主要取决于标量的(联合)海明权值。JSF表示的平均联合海明权密度为1/2,是所有带符号二进制表示中最优的,但JSF编码只能从右到左实现。提出一个新的从左到右的基于MOF的编码方法,该方法的平均联合海明权密度与基于JSF表示的相同,并提出一个新的多标量乘算法,该算法对标量从左到右进行编码,并将编码合并到多标量乘的主计算中,从而节省了存储标量的新编码的内存空间,提高了实现效率。Many elliptic curve based cryptographic protocols require computation of multiple scalar multiplications such as kP ＋ lQ. Common methods to compute it are the Shamir method and the interleaving method whereas their speed mainly depends on the （joint） Hamming weight of the scalars. The joint sparse form of two L - bit integers has an average joint Hamming weight of L/2, which is an opti- mal- weight signed - binary representation, but it can be implemented only from right to left. In this paper, a new recoding method based on the mutual opposite form is proposed. This form has the same average Joint Hamming weight as the JSF. And a new MOF representation based multiple scalar multiplication algorithm is given. This method examines the integers from left to right. This results in the merging of reeoding and evaluation stages. So the proposed algorithm can improve the performance and reduce the memory consumption of scalar multiplication operation.

关 键 词：椭圆曲线密码系统 标量乘 多标量乘 MOF JSF 

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