论文部分内容阅读
椭圆曲线密码体制(Elliptic Curve Cryptosystem,简称ECC)是当前最流行实用的公钥密码体制之一,由于其构造的独特性,达到一定安全需求所需的密钥长度很短,并且实现效率很高。椭圆曲线离散对数问题(ECDLP)是ECC的安全核心,求解ECDLP问题最快的算法是指数时间的,这意味着由此设计的加密与签名方案更加的安全。主要有两类计算ECDLP问题的算法:一是与所选椭圆曲线及其有限域无关的通用算法,二是特定椭圆曲线或有限域的特定算法。Pollard rho及其并行算法为计算ECDLP的一种非常有效的通用算法。1997年,加拿大公司Certicom为了鼓励对ECC的研究以及评估其安全性,开展了Certicom ECC挑战项目。对计算ECDLP问题的研究,一方面能够让人们更好地理解其工业标准及ECDLP问题的困难性,另一方面鼓励着人们对于ECC的安全性进行更深入的研究。Koblitz曲线是定义在2上形如2+=3+1或2+=3+2+1的一种特殊的椭圆曲线。在Koblitz曲线上,存在一种特殊的映射叫做Frobenius自同态。由于在Koblitz曲线上可以进行快速的群运算,同时快速的Frobenius自同态和半分运算可以对标量乘运算的速度有着很大的提高,因此Koblitz曲线受到了欢迎并在实际的工业标准中有着广泛的应用。例如,在NIST推荐使用的椭圆曲线中就有5条Koblitz曲线。本文研究的是这种特殊的椭圆曲线Koblitz曲线的安全问题,即用Pollard rho算法在Koblitz曲线上求解ECDLP问题。本文利用Frobenius自同态和半分运算,在Koblitz曲线上分别用多项式基和正规基进行了软件上的仿真实现,成功求解出了41和83比特上的ECDLP问题。本文首次在Koblitz曲线上对多项式基和正规基软件上的实现进行了理论和实践上的比较,并得出了结论。虽然正规基多用于硬件实现,但在Koblitz曲线上与Frobenius自同态和半分运算相结合的前提下,正规基在软件上的实现效率仍高于多项式基。