基于复合域上的椭圆曲线密码体制的计算算法

Efficient Algorithms for Elliptic Curve Cryptosystems

基于有限域上椭圆曲线公开密钥协议的离散对数计算算法正日益成为热点 .其基本的操作是标量乘法 :即用一整数乘以椭圆曲线上给定的点 P.协议的主要开销在于椭圆曲线的标量乘操作上 .本文给出 3个算法进行椭圆曲线密码系统的有效计算 .第一个算法采用加 -减法链的方法处理标量乘法问题 ;第二个算法给出了正整数 n的 NAF形式 ;第三个算法采用窗口的方法处理 NAF(n)从而进一步提高加 -减法链的效率 .这三个算法的有机结合从很大程度上提高了椭圆曲线密码体制的加 /解密速度 .

It has become increasingly common to implement discrete logarithm based public key protocols on elliptic curves over finite fields. The basic operation is scalar multiplication: taking a given integer multiple of a given point on the elliptic curve over finite fields. The cost of the protocols depends on that of the elliptic scalar multiplication operation. This contribution describes three alogrithms for efficient implementations of elliptic curve cryptosystems. The addition subtraction method is used to process elliptic scalar multiplication operation in the first alogrithm. The second alogrithm deals with the computation of NAF(n) for addition subtraction method; and the third alogrithm provides window method for ordinary NAF's of integers. These three alogrithms integrated organically improve greatly the rates of encipher and decipher in the Elliptic Curve Cryptsystems.