论文标题:加速ECC体制的相关算法研究
Research on Accelerating the Relative Algorithms of ECC
论文作者
论文导师 祝跃飞,论文学位 硕士,论文专业 密码学
论文单位 解放军信息工程大学,点击次数 548,论文页数 57页File Size2768K
2006-04-01论文网 http://www.lw23.com/lunwen_28603197/
Elliptic Curve; ECC; multiple scalar multiplication; Tate Pairing; algorithm
公钥密码体制是实现信息安全保密的关键技术。应用椭圆曲线理论设计的公钥密码体制大致可分为两类：椭圆曲线密码ECC体制和基于身份的密码体制IBC。密码体制的快速实现是密码学界关注的热点之一，其中各实现算法的改进和优化是研究的重要内容。椭圆曲线密码体制实现中最关键的运算是椭圆曲线标量乘法和双标量乘法；基于身份密码体制实现中的核心运算是椭圆曲线Tate Pairing的计算。本文主要针对椭圆曲线双标量乘法的计算和椭圆曲线Tate Pairing的计算两个方面进行了研究。 首先，基于半点运算给出一种计算特征为2的有限域上椭圆曲线双标量乘法kP+lQ的新算法并分析了效率，当基域上求乘法与求逆的运算时间的比值比较小时，新算法的效率比已有算法提高5％～30％。 其次，本文对计算特征为3的有限域上超奇异椭圆曲线Tate Pairing的Duursma-Lee算法和Modifled Duursma-Lee算法进行了研究。应用除子理论由Tate Pairing的定义直接推导了Duursma-Lee算法；对特征值为3和2的有限域上超奇异椭圆曲线Tate Pairing给出一个等价定义，降低了最后的求幂次数；对Modified Duursma-Lee算法提出两个改进算法，分刖将效率提升了约6.7％和13.3％。 最后研究了特征为素数p(p＞3)的有限域上一般椭圆曲线Tate Pairing的计算，对Miller算法本身提出了一个改进算法，其效率比已有的算法提高了约12％。
Public Key Cryptosystems is key technology of realizing information security. Public Key Cryptosystems based on the Elliptic Curve theory are divided into two types: Elliptic Curve Cryptography (ECC) and Identity-Based Cryptosystems (IBC). Efficiently implementing cryptosystem is one of hot points in cryptography realm. Modifying and optimizing every implementing algorithm is the primary content of it. Scalar multiplication and multiple scalar multiplications are the most crucial algorithms of implementing Elliptic Curve Cryptosystems. Computing Tate Pairing is the kernel algorithm of implementing Identity-Based Cryptosystems. In this dissertation, we studied these two aspects.First, basing on point halving, this thesis proposed a new efficient algorithm of computing kP+lQ on an elliptic curve over the finite field with characteristic 2 and analyzed the computational efficiency. When the ratio I/M of inversion to multiplication cost is small, this new algorithm is about 5%～30% faster than the traditional algorithms.Subsequently, We studied the Duursma-Lee algorithm and the modified Duursma-Lee algorithm that are algorithms of computing Tate pairing of supersingular elliptic curve over finite fields with characteristic three. We directly reduced the Duursma-Lee algorithm applying the theory of divison from the defination of Tate Pairing. Then we introduced a new equavalent defination of Tate pairing of supersingular elliptic curve over finite fields with characteristic three or two, that it has lower final exponent. We proposed two refined algorithms of the modified Duursma-Lee algorithm. The two algorithms are enhanced by 6.7% and 13.3% respectively, comparing with the costs of the modified Duursma-Lee algorithm.Eventually, we also modified Miller algorithm of computing Tate pairing over the finite field with which characteristic is prime p (p>3) . The modified algorithm is enhanced by 12%.
|
