无移位操作的快速comb乘法算法  

Fast Comb-multiplication without Shift Operation

作　　者：李忠[1,2] 彭代渊[1] 郝悦彤[3] 

机构地区：[1]西南交通大学信息科学与技术学院,成都610031 [2]宜宾学院计算机科学与技术系,宜宾644000 [3]西南大学经济管理学院,重庆400715

出　　处：《计算机科学》2009年第3期158-160,共3页Computer Science

基　　金：四川省教育厅资助科研项目(07ZA145)资助

摘　　要：有限域GF(2n)上乘法运算是影响GF(2n)上椭圆曲线密码实现效率的关键运算之一。基于窗口技术的comb乘法算法,被认为是目前有限域GF(2n)上乘法运算最快的算法之一。但是,它仍然使用了移位操作,而移位操作恰好又是域GF(2n)乘法运算中很耗时的操作。提出并实现了一种新的基于窗口技术的快速comb乘法算法,该算法避免了移位操作,且不增加异或运算次数。理论分析和实验结果表明,新算法有很好的实现效率,适合于有限域GF(2n)上椭圆曲线密码算法的软件实现。Efficient algorithms for multiplication in GF（2^n） are required to implement elliptic curve cryptosystems over GF（2^n）. Comb-multiplication, based on window technology, is considered one of the fastest algorithms for multiplication in GF（2^n）. However, it includes SHIFT operations, and SHIFT operations are just time-consuming operation among the operations of multuiplication in GF（2^n）. A new algorithm for multiplication in GF（2^n）, based on window technology, was presented, it completely avoided the SHIFT operations, and did not increase the number of XOR operations. The analysis and experiment results show that the new algorithm is faster than the comb-multiplication based on window technology, and is particularly useful for software implementation of elliptic curve cryptosystems over GF（2^n）.

关 键 词：GF(2n)乘法运算 移位操作 comb乘法算法 椭圆曲线密码 

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