一种改进的联合点乘算法及其应用

作者：杨 宇，任丰博,胡速登 日期：2008-04-23/span> 浏览：3218 查看PDF文档

一种改进的联合点乘算法及其应用
杨 宇，任丰博,胡速登
（浙江大学 超大规模集成电路研究所，浙江 杭州 310027）

摘 要：在现代密码系统中使用椭圆曲线密码（ECC）最频繁的一种方法是多点乘算法。通过分析ECC各种点乘计算方法，研究了不同算法性能的影响,并针对计算ECC多点乘算法耗时大的问题，提出了一种改进的联合点乘算法。该算法采用了基于基底4的布斯算法和结合相互对立形式（MOF)的标量表示方法。与传统方法相比较,该算法可以有效地提高运算速度，减少运算时间，并在椭圆曲线数字签名算法（ECDSA）中得到了应用。
关键词：椭圆曲线密码；多点乘算法；布斯算法；椭圆曲线数字签名算法

An improved method for joint scalar multiplication
YANG Yu, REN Fenbo, HU Sudeng
(Institute of VLSI design, Zhejiang University, Hangzhou 310027, China)

Abstract: The multiscalar multiplication with two scalars is the most time consuming operations in elliptic curve cryptography （ECC）. A new improved method on the basis of radix4 booth algorithm combining with the mutual opposite form (MOF) method was presented , by analyzing different ECC scalar multiplication and their effect on the performance. The method can improve operation speed and reduce operation time effectively over traditional algorithm, and can be used in elliptic curve digital signature algorithm (ECDSA).
Key words: elliptic curve cryptography （ECC）; multiscalar multiplication; booth algorithm; elliptic curve digital signature algorithm (ECDSA)

参考文献(Reference):
［1］MILLER V S. Use of Elliptic Curves in Cryptography［C］. Advances in CryptologyCrypto ’85, SpringerVerlag, 1986:417-426.
［2］KOBLITZ N. Elliptic curve cryptosystems［J］. Mathematics of Computation,1997,4(8):203-209.
［3］ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms［J］. IEEE Transactions on Information Theory,1985,3(1):469-472.
［4］MOLLER B. Algorithms of multiexponentiation［J］. Selected Areas in CryptographySAC 2001, 2001,225(9):165-180.
［5］MOON S. Elliptic Curve Scalar Point Multiplication Using Radix4 Booths Algorithm［C］. International Symposium on Communications and Information Technologies 2004 (ISCIT 2004). Japan:［s. n.］,2004:80-83.
［6］LIM C H, HWANG H S. Speeding Up Elliptic Scalar Multiplication with Precomputation［C］. ICISC’99. Berlin:［s. n.］,2000:102-119.
［7］OKEYA K, S AMOA K S. Signed Binary Representations Revisited［C］. CRYPTO 2004. Santa Barbara, California:［s. n.］,2004:123-139.