【作者】 汪朝晖；

【导师】 陈建华；

【作者基本信息】 武汉大学 ， 应用数学， 2004， 博士

【摘要】 椭圆曲线密码是目前最具潜力的一类公钥密码系统。由于椭圆曲线密码在安全性、实现效率和实现代价等方面相对于其它公钥密码系统的优势，它已经得到越来越广泛的应用，并被许多国家和国际标准组织采纳为公钥密码算法标准，其安全性问题自然得到人们的广泛关注和研究。本论文讨论、研究并解决椭圆曲线密码系统中各方面存在的安全问题，特别是椭圆曲线密码机制的安全性及其证明问题。本文将椭圆曲线密码的安全性分为三个层面进行相对独立的研究：即数学基础的安全性、密码机制的安全性和工程实现的安全性。文章着重分析并解决了保障椭圆曲线密码安全性的几个技术难点：确定椭圆曲线的安全标准、设计可证安全的椭圆曲线加密机制及其安全性证明、设计可证安全的椭圆曲线签名机制及其安全性证明。 研究任何一个公钥密码系统的安全性，首先必须研究其数学基础的安全性，数学基础的安全性是一个公钥密码系统得以建立的前提，而椭圆曲线密码的数学基础就是椭圆曲线离散对数问题，因此作者在介绍了必要的背景知识和数学知识之后，就开始研究椭圆曲线离散对数问题的安全性。 研究椭圆曲线离散对数问题的安全性，就是要研究如何通过选择恰当的椭圆曲线参数使得其上的椭圆曲线离散对数在计算上是难解的，即能有效地抵抗各种椭圆曲线离散对数求解算法的攻击。为此作者将现今所有已知的求解椭圆曲线离散对数的算法分为两类(一般椭圆曲线上离散对数的求解算法和特殊椭圆曲线上离散对数的求解算法)进行详细的分析，找出能抵抗这些攻击算法的安全椭圆曲线。一般椭圆曲线上离散对数的求解算法不依赖于椭圆曲线的参数选取，有代表性的算法有Baby-Step Giant-Step(BSGS)算法、Pohlig-Hellman算法和Pollard’s Rho算法等，通过研究一般椭圆曲线上离散对数的求解算法我们得出结论：通过恰当选择椭圆曲线的阶，使得其有足够大的素因子，就可以抵抗这类算法的攻击。一些椭圆曲线，由于其中某些参数选取的特殊性，使得其上的离散对数存在非常有效的求解算法，因此这些特殊的椭圆曲线不能用来构建椭圆曲线密码系统。作者分析了所有求解特殊椭圆曲线上离散对数的有效算法，以指明这些特殊的椭圆曲线的安全隐患，这些攻击算法包括MOV算法、FR算法、SSSA算法和解奇异椭圆曲线上离散对数的算法。通过对上述所有椭圆曲线离散对数求解算法的仔细研究，作者得出结论：排除含有安全隐患的特殊的椭圆曲线，选择阶含有大素因子的椭圆曲线来构建椭圆曲线密码系统，则其数学基础是安全的。 在公钥密码系统的数学基础安全的基础上，研究密码机制的安全性，是公钥密码系统安全性的一个非常重要的内容，因而作者将文章的重点放在了研究椭圆曲线密码机制的安全性上，这包括椭圆曲线加密机制的安全性和椭圆曲线签名机制的安全性。 在公钥密码系统出现之初，人们总是试图论述公钥密码机制的安全性与其所基于的数学基础的安全性等价，并很难对此问题给出一个令人满意的严格证明，我们称通过论述而不是严格证明所得出的公钥密码机制的安全性为启发式安全性。 随着计算方法及计算技术的提高和攻击者攻击行为的逐步完善及提高，人们越来越意识到启发式安全性不足以作为衡量一个公钥密码机制安全性的标准。在RSA机制和EIGamal机制提出之初，人们都相信这两个机制的安全性与其数学基础的安全性等价，原因就是当时人们都想当然地认为攻击者是无法访问解密设备的。然而现在网络入侵和欺骗行为己是客观存在的事实，攻击者的手段日益完善，完全有可能访问解密设备，这样攻击者通过适当选择密文让解密设备解密就能轻易地破解RSA机制和EIGamal机制。我们称这种攻击行为为选择密文攻击，在选择密文攻击下RSA机制和EIGamal机制的安全性显然不等价于其数学基础的安全性。 目前已知的针对公钥加密机制的最强攻击行为是自主选择密文攻击，针对公钥签名机制的最强攻击行为是自主选择消息攻击，在这些攻击之下，公钥密码机制的安全性不再等价于其数学基础的安全性。这给人们提出了一个很严重的问题:基于某数学基础的公钥密码机制的安全性与该数学基础的安全性是两码事，要证明一个公钥密码系统是安全的，除了保证其数学基础的安全性外，还要证明其公钥密码机制的安全性。我们称通过严格证明而获得的公钥密码机制的安全性为可证安全性，可证安全性已经成为国际上衡量一个公钥密码机制安全性的主要标准。如何有效地保证并证明公钥密码机制的安全性成了密码学界一个重要的研究领域。 为研究椭圆曲线密码机制的安全性，作者首先根据公钥密码分析学近二十年的进展重新给出了公钥密码机制的各种安全性定义，这些安全性定义的最大好处就是将安全性的确切要求和攻击行为结合起来，使得严格证明公钥密码机制抵抗某种攻击方法的安全性变得可行。作者研究了各种提高公钥密码机制安全性的技术手段，并结合椭圆曲线加密机制和签名机制的特点，以 EIG别叮al加密机制和签名机制为基础，提出了一个可证明能抵抗自主选择密文攻击的椭圆曲线加密机制和一个可证明能抵抗自主选择消息攻击的椭圆曲?更多还原

【Abstract】 Elliptic curve cryptosystems are one kind of the most promising public key cryptosystems. As their advantages of securities, efficiencies and implementation costs over other public key cryptosystems, elliptic curves cryptosystems are getting broadly applied and adopted by many criteria organizations as one of their public key cryptosystem standards, thus the securities of elliptic curve cryptosystems are drawing much attentions and studied extensively. In this thesis, the author discussed and solved the security problems existing in every aspect of elliptic curve cryptosystems, especially the security problems of elliptic curve cryptoschemes and their security proofs. The author divided the securities of elliptic curve cryptosystems into three relatively independent levels: the securities of their mathematical foundations, the securities of the cryptoschemes and the securities of their implementations. The author led his emphasis on solving the following difficult but important problems: establishing a security criteria for elliptic curves, designing a provable secure elliptic curve encryption scheme and proving its security, designing a provable secure elliptic curve signature scheme and proving its security. The conclusions and produces in this thesis are very valuable to the applications of elliptic curve cryptosystems.To research any public key cryptosystem’s securities, one first has to study the securities of its mathematical foundation that is the premise of constructing the public key cryptosystem. As elliptic curve discrete logarithms being the mathematical foundations of all elliptic curve cryptosystems, the author first came into studying the securities of elliptic curve discrete logarithms after introducing some backgrounds and the necessary mathematical knowledge.To study the securities of elliptic curve discrete logarithms is to study how to select the proper parameters of elliptic curves, th s discrete logarithms on them is unsolvable in computation, that’s to say they can resists all existing attacks on the discrete logarithms of them. The author divided all known attacks on elliptic curve discrete logarithms in two types: attacks on general elliptic curve discrete logarithms and attacks on special elliptic curve discrete logarithms. The author studied these two types of attacks in details and found out a kind of secure elliptic curve, the discrete logarithms on which can resist all those attacks. Attacks on general elliptic curve discretelogarithms are not affected by the choices of elliptic curve parameters. The Baby-Step Giant-Step (BSGS) attack, Pohlig-Hellman attack and Pollard’s Rho attacks are all famous attacks on general elliptic curve discrete logarithms. By carefully studying this type of attacks, the author concluded that properly choosing the rank of an elliptic curve to make it contain a big enough prime factor can make the elliptic curve secure against this type of attacks. Because of the special parameters of some special types of elliptic curves, there are efficient attacks on them. Those special elliptic curves are not allowed to construct elliptic curve cryptosystems. The MOV attack, FR attack, SSSA attack and attacks on singular elliptic curves are all efficient attacks on special elliptic curves. Through analysis of those efficient attacks, the author pointed out the insecurities of those special elliptic curves. By studying the tow types of attacks, the author drew a conclusion that excluding all special elliptic curves and selecting elliptic curves which ranks contain big prime factors to construct elliptic curve cryptosystems can assure the securities of their mathematical foundations.Based on the securities of its mathematical foundation, the securities of cryptoschemes are very important contents of a public key cryptosystem’s securities. In this thesis, the author led his emphasis on studying the securities of elliptic curve cryptoschemes which including the securities of elliptic curve encryption cryptoschemes and the securities of elliptic curve signature cryptos更多还原