椭圆曲线密码的安全性研究
|
摘要
椭圆曲线密码是目前最具潜力的一类公钥密码系统。由于椭圆曲线密码在安全性、实现效率和实现代价等方面相对于其它公钥密码系统的优势，它已经得到越来越广泛的应用，并被许多国家和国际标准组织采纳为公钥密码算法标准，其安全性问题自然得到人们的广泛关注和研究。本论文讨论、研究并解决椭圆曲线密码系统中各方面存在的安全问题，特别是椭圆曲线密码机制的安全性及其证明问题。本文将椭圆曲线密码的安全性分为三个层面进行相对独立的研究：即数学基础的安全性、密码机制的安全性和工程实现的安全性。文章着重分析并解决了保障椭圆曲线密码安全性的几个技术难点：确定椭圆曲线的安全标准、设计可证安全的椭圆曲线加密机制及其安全性证明、设计可证安全的椭圆曲线签名机制及其安全性证明。
研究任何一个公钥密码系统的安全性，首先必须研究其数学基础的安全性，数学基础的安全性是一个公钥密码系统得以建立的前提，而椭圆曲线密码的数学基础就是椭圆曲线离散对数问题，因此作者在介绍了必要的背景知识和数学知识之后，就开始研究椭圆曲线离散对数问题的安全性。
研究椭圆曲线离散对数问题的安全性，就是要研究如何通过选择恰当的椭圆曲线参数使得其上的椭圆曲线离散对数在计算上是难解的，即能有效地抵抗各种椭圆曲线离散对数求解算法的攻击。为此作者将现今所有已知的求解椭圆曲线离散对数的算法分为两类(一般椭圆曲线上离散对数的求解算法和特殊椭圆曲线上离散对数的求解算法)进行详细的分析，找出能抵抗这些攻击算法的安全椭圆曲线。一般椭圆曲线上离散对数的求解算法不依赖于椭圆曲线的参数选取，有代表性的算法有Baby-Step Giant-Step(BSGS)算法、Pohlig-Hellman算法和Pollard's Rho算法等，通过研究一般椭圆曲线上离散对数的求解算法我们得出结论：通过恰当选择椭圆曲线的阶，使得其有足够大的素因子，就可以抵抗这类算法的攻击。一些椭圆曲线，由于其中某些参数选取的特殊性，使得其上的离散对数存在非常有效的求解算法，因此这些特殊的椭圆曲线不能用来构建椭圆曲线密码系统。作者分析了所有求解特殊椭圆曲线上离散对数的有效算法，以指明这些特殊的椭圆曲线的安全隐患，这些攻击算法包括MOV算法、FR算法、SSSA算法和解奇异椭圆曲线上离散对数的算法。通过对上述所有椭圆曲线离散对数求解算法的仔细研究，作者得出结论：排除含有安全隐患的特殊的椭圆曲线，选择阶含有大素因子
的椭圆曲线来构建椭圆曲线密码系统，则其数学基础是安全的。
在公钥密码系统的数学基础安全的基础上，研究密码机制的安全性，是公钥密
码系统安全性的一个非常重要的内容，因而作者将文章的重点放在了研究椭圆曲
线密码机制的安全性上，这包括椭圆曲线加密机制的安全性和椭圆曲线签名机制
的安全性。
在公钥密码系统出现之初，人们总是试图论述公钥密码机制的安全性与其所基
于的数学基础的安全性等价，并很难对此问题给出一个令人满意的严格证明，我
们称通过论述而不是严格证明所得出的公钥密码机制的安全性为启发式安全性。
随着计算方法及计算技术的提高和攻击者攻击行为的逐步完善及提高，人们越
来越意识到启发式安全性不足以作为衡量一个公钥密码机制安全性的标准。在
RSA机制和EIGamal机制提出之初，人们都相信这两个机制的安全性与其数学基
础的安全性等价，原因就是当时人们都想当然地认为攻击者是无法访问解密设备
的。然而现在网络入侵和欺骗行为己是客观存在的事实，攻击者的手段日益完善，
完全有可能访问解密设备，这样攻击者通过适当选择密文让解密设备解密就能轻
易地破解RSA机制和EIGamal机制。我们称这种攻击行为为选择密文攻击，在选
择密文攻击下RSA机制和EIGamal机制的安全性显然不等价于其数学基础的安全
性。
目前已知的针对公钥加密机制的最强攻击行为是自主选择密文攻击，针对公钥
签名机制的最强攻击行为是自主选择消息攻击，在这些攻击之下，公钥密码机制
的安全性不再等价于其数学基础的安全性。这给人们提出了一个很严重的问题:
基于某数学基础的公钥密码机制的安全性与该数学基础的安全性是两码事，要证
明一个公钥密码系统是安全的，除了保证其数学基础的安全性外，还要证明其公
钥密码机制的安全性。我们称通过严格证明而获得的公钥密码机制的安全性为可
证安全性，可证安全性已经成为国际上衡量一个公钥密码机制安全性的主要标准。
如何有效地保证并证明公钥密码机制的安全性成了密码学界一个重要的研究领
域。
为研究椭圆曲线密码机制的安全性，作者首先根据公钥密码分析学近二十年的
进展重新给出了公钥密码机制的各种安全性定义，这些安全性定义的最大好处就
是将安全性的确切要求和攻击行为结合起来，使得严格证明公钥密码机制抵抗某
种攻击方法的安全性变得可行。作者研究了各种提高公钥密码机制安全性的技术
手段，并结合椭圆曲线加密机制和签名机制的特点，以 EIG别叮al加密机制和签名
机制为基础，提出了一个可证明能抵抗自主选择密文攻击的椭圆曲线加密机制和
一个可证明能抵抗自主选择消息攻击的椭圆曲?
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 secur
ity 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 discrete
logarithms 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
研究任何一个公钥密码系统的安全性，首先必须研究其数学基础的安全性，数学基础的安全性是一个公钥密码系统得以建立的前提，而椭圆曲线密码的数学基础就是椭圆曲线离散对数问题，因此作者在介绍了必要的背景知识和数学知识之后，就开始研究椭圆曲线离散对数问题的安全性。
研究椭圆曲线离散对数问题的安全性，就是要研究如何通过选择恰当的椭圆曲线参数使得其上的椭圆曲线离散对数在计算上是难解的，即能有效地抵抗各种椭圆曲线离散对数求解算法的攻击。为此作者将现今所有已知的求解椭圆曲线离散对数的算法分为两类(一般椭圆曲线上离散对数的求解算法和特殊椭圆曲线上离散对数的求解算法)进行详细的分析，找出能抵抗这些攻击算法的安全椭圆曲线。一般椭圆曲线上离散对数的求解算法不依赖于椭圆曲线的参数选取，有代表性的算法有Baby-Step Giant-Step(BSGS)算法、Pohlig-Hellman算法和Pollard's Rho算法等，通过研究一般椭圆曲线上离散对数的求解算法我们得出结论：通过恰当选择椭圆曲线的阶，使得其有足够大的素因子，就可以抵抗这类算法的攻击。一些椭圆曲线，由于其中某些参数选取的特殊性，使得其上的离散对数存在非常有效的求解算法，因此这些特殊的椭圆曲线不能用来构建椭圆曲线密码系统。作者分析了所有求解特殊椭圆曲线上离散对数的有效算法，以指明这些特殊的椭圆曲线的安全隐患，这些攻击算法包括MOV算法、FR算法、SSSA算法和解奇异椭圆曲线上离散对数的算法。通过对上述所有椭圆曲线离散对数求解算法的仔细研究，作者得出结论：排除含有安全隐患的特殊的椭圆曲线，选择阶含有大素因子
的椭圆曲线来构建椭圆曲线密码系统，则其数学基础是安全的。
在公钥密码系统的数学基础安全的基础上，研究密码机制的安全性，是公钥密
码系统安全性的一个非常重要的内容，因而作者将文章的重点放在了研究椭圆曲
线密码机制的安全性上，这包括椭圆曲线加密机制的安全性和椭圆曲线签名机制
的安全性。
在公钥密码系统出现之初，人们总是试图论述公钥密码机制的安全性与其所基
于的数学基础的安全性等价，并很难对此问题给出一个令人满意的严格证明，我
们称通过论述而不是严格证明所得出的公钥密码机制的安全性为启发式安全性。
随着计算方法及计算技术的提高和攻击者攻击行为的逐步完善及提高，人们越
来越意识到启发式安全性不足以作为衡量一个公钥密码机制安全性的标准。在
RSA机制和EIGamal机制提出之初，人们都相信这两个机制的安全性与其数学基
础的安全性等价，原因就是当时人们都想当然地认为攻击者是无法访问解密设备
的。然而现在网络入侵和欺骗行为己是客观存在的事实，攻击者的手段日益完善，
完全有可能访问解密设备，这样攻击者通过适当选择密文让解密设备解密就能轻
易地破解RSA机制和EIGamal机制。我们称这种攻击行为为选择密文攻击，在选
择密文攻击下RSA机制和EIGamal机制的安全性显然不等价于其数学基础的安全
性。
目前已知的针对公钥加密机制的最强攻击行为是自主选择密文攻击，针对公钥
签名机制的最强攻击行为是自主选择消息攻击，在这些攻击之下，公钥密码机制
的安全性不再等价于其数学基础的安全性。这给人们提出了一个很严重的问题:
基于某数学基础的公钥密码机制的安全性与该数学基础的安全性是两码事，要证
明一个公钥密码系统是安全的，除了保证其数学基础的安全性外，还要证明其公
钥密码机制的安全性。我们称通过严格证明而获得的公钥密码机制的安全性为可
证安全性，可证安全性已经成为国际上衡量一个公钥密码机制安全性的主要标准。
如何有效地保证并证明公钥密码机制的安全性成了密码学界一个重要的研究领
域。
为研究椭圆曲线密码机制的安全性，作者首先根据公钥密码分析学近二十年的
进展重新给出了公钥密码机制的各种安全性定义，这些安全性定义的最大好处就
是将安全性的确切要求和攻击行为结合起来，使得严格证明公钥密码机制抵抗某
种攻击方法的安全性变得可行。作者研究了各种提高公钥密码机制安全性的技术
手段，并结合椭圆曲线加密机制和签名机制的特点，以 EIG别叮al加密机制和签名
机制为基础，提出了一个可证明能抵抗自主选择密文攻击的椭圆曲线加密机制和
一个可证明能抵抗自主选择消息攻击的椭圆曲?
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 secur
ity 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 discrete
logarithms 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
引文
[ABR99] M. Abdalla, M. Bellare, and P. Rogaway, DHAES: an encryption scheme based onthe Diffie-Hellman problem, Cryptology ePrint Archive, Report 1999/007, 1999. http://eprint.iacr.org.
[ADH94] L.Adleman J.Demarrais and M.D.Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobian of large genus hyperelliptic curves over finite fields, Proc First Int'l Symp on Algorithmic Number Theory (ANTS-Ⅰ), 1994, pages:28～40.
[AM93] A.O.L. Atkin and F. Morain. Elliptic curves and primality proving.Mathematics of Computation, 61(203), July 1993, pages:29～68.
[Atk91] A.O.L. Atkin, The number of points on an elliptic curves modulo a prime, Seriea of e-mails to the NMBRTHRY mailing list, 1991-1992.
[BDPR98] M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway, Relations among notions of security for public-key encryption schemes, In Advances in Cryptology-Crypto '98, 1998, pages:26～45.
[BK98] R. Balasubramanian and N.Koblitz, The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm, Journal of Cryptology, 11, 1998, pages: 141～145.
[BL96] D.Boneh and R.J.Lipton, Algorithms for black-box fields and their application to cryptography, In Advances in Cryptology-Crypto'96, 1996, pages:283～296.
[Ble98] D. Bleichenbacher, Chosen ciphertext attacks against protocols based on RSA encryption standard PKCS#1, Advances in Cryptology—CRYPTO'98 Proceedings, Springer-Verlag, 1998, pages: 1～12.
[BLK00] J. Baek, B. Lee, and K. Kim, Secure length-saving E1Gamal encryption under the computational Diffie-Hellman assumption, In Proc. 5th Australian Conference on Information, Security, and Privacy, 2000.
[Bon98] D. Boneh, The decision Diffie-Hellman problem, In Ants-Ⅲ, Springer, LNCS 1423, 1998, pages:48～63.
[Bro00] DRL. Brown, The exact security of ECDSA, Technical report, CORR 2000-54, Dept. of Combinatorics and Optimization, Univ. of Waterloo, 2000.
[BR93] M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, In First ACM Conference on Computer and
Communications Security, 1993, pages:62～73.
[BR94] M. Bellare and P. Rogaway, Optimal asymmetric encryption, In Advances in Cryptology -Eurocrypt '94, 1994, pages:92～111.
[CGH98] R. Canetti, O. Goldreich, and S. Halevi, The random oracle model, revisited, In 30th Annual ACM Symposium on Theory of Computing, 1998.
[Cor99] J.S. Coron, Resistance against differential power analysis for elliptic curve cryptosystems, Proceedings of CHES '99 (C. K. Ko_c and Chr. Paar, eds.), Lecture Notes in Computer Science, vol. 1717, Springer-Verlag, 1999, pages: 292～302.
[CS98] R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, In Advances in Cryptology,Crypto '98, 1998, pages: 13～25.
[CS01] R. Cramer and V. Shoup, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, Cryptology ePrint Archive, Report 2001/108, 2001. http://eprint.iacr.org.
[DDN91] D. Dolev, C. Dwork, and M. Naor, Non-malleable cryptography, In 23rd Annual ACM Symposium on Theory of Computing, 1991, pages:542～552.
[DDN98] D. Dolev, C. Dwork, and M. Naor, Non-malleable cryptography, 1998. Manuscript (updated, full length version of STOC paper).
[DH76] W. Diffie and M.F. Hellman, New direction in cryptology, IEEE Transactions on Information Theory, vo122, no.6, 1976, pagese:644～654.
[ElG85] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, 1985, 31, pages:469～472.
[Elk92] Noam D. Elkies, Explicit isogenies, manuscript, Boston, MA, 1992.
[Elk98] Noam D. Elldes, Elliptic and modular curves over finite fields and related computational issues, In D.A. Buell and J.T. Teitelbaum, editors, Computational Perspectives in Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin, (Chicago, IL, 1995), AMS, 1998. pages:21～76.
[FGH00] M. Fouquet, P.Gaudry, and R.Harley, An extention of Satoh's algorithm and its implementation, J.Ramanujan Math. Soc., 15, 2000, pages:281～318.
[FO99] E. Fujisaki and T. Okamoto, Secure integration of asymmetric and symmetric encryption schemes, In Advances in Cryptology-Crypto '99, 1999, pages:537～554.
[FOPS01] E. Fujisald, T. Okamoto, D. Pointcheval, and J. Stem, RSA-OAEP is secure under the RSA assumption, In Advances in Cryptology-Crypto'2001,2001.
[FOPS02] Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stem, RSA-OAEP is secure under the RSA assumption, Journal of Cryptology 24 (2002)
[FR94] G.Frey. and H. Rück, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of Computation, 62, 1994, pages:865～874.
[GHS02] P. Gaudry, F. Hess and N. Smart, Constructive and destructive facets of Weil descent on elliptic curves, Journal of Cryptology, 15, 2002, pages: 19～46.
[GLV] R.Gallant, R.Lambert and S. Vanstone, Improving the parallelized Pollard lambda serach on binary anomalous curves, to appear in Mathematics of Computation.
[GM84] S. Goldwasser and S. Micali, Probabilistic encryption, Journal of Computer and System Sciences, 28, 1984, pages: 270～299.
[Gor98] D. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, 1998, 27, pages: 129～146.
[Hus87] D.Husemller, Elliptic Curves, Springer-Verlag, New York, 1987.
[JM96] D. Johnson and S. Matya, Asymmetric encryption: evolution and enhancements, Cryptobytes, 2(1), 1996. http://www.rsasecurity.com/rsalabs.
[JM99] D. Johnson and A. Menezes, The elliptic curve digital signature algorithm (ECDSA), Technical report CORR 99-34, Dept. of C&O, University of Waterloo, 1999.
[JN01] A. Joux and K. Nguyen, Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups, Cryptology ePrint Archive, Report 2001/003, 2001. http ://eprint.iacr.org.
[KI00] Kazukuni Kobara and Hideki Imai, New chosen-plaintext attacks on the one-wayness of the modified McEliece PKC, Proposed at Asiacrypt 2000, pages:237-251.
[KJJ98] P. Kocher, J. Jaffe, and B. Jun, Introduction to differential power analysis and related attacks, http://www.cryptography.com/dpa/technical/, 1998.
[KJJ99] P. Kocher, J. Jaffe, and B. Jun,Differential power analysis, Proceedings of CRYPTO '99 (M. J. Wiener, ed.), Lecture Notes in Computer Science, vol. 1666, Springer-Verlag, 1999, pages:388～397.
[Kob87] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, 48, 1987, pages:203～209.
[Lan78] S.Lang, Elliptic Curve:Diophantine Analysis, Springer-Verlag, New York, 1978.
[LL94] C. Lim and P. Lee, More flexible exponentiation with precomputation,
Advances in Cryptology—Crypto'94, LNCS839, 1994, pages:95～107.
[Man01] J. Manger, A chosen ciphertext attack on RSA optimal asymmetric encryption padding (OAEP) as standardized in PKCS #1 v2.0, In Advances in Cryptology-Crypto 2001, 2001, pages:230～238.
[McC90] K. McCurley, The discrete logarithm problem, Cryptology and Computational Number Theory, 42, 1990, pages:49～74.
[MDS99] T. S. Messerges, E. A. Dabbish, and R. H. Sloan, Investigations of power analysis attacks on smartcards,Proceedings of USENIX Workshop on Smartcard Technology, 1999, pages: 151～161.
[Mil85] V. Miller, Uses of elliptic curves in cryptography, Advances in Cryptology-Crypto'85, LNCS218, 1986, pages:417～426.
[MOV93] A.Menezes T.Okamoto and S.Vanstone, Reducing elliptic cueve logarithms to logarithms in a finite field, IEEE Transaction on Information Theory, Vol.IT-39, 5, 1993, pages: 1639～1646.
[Nec94] V.I. Nechaev, Complexity of a determinate algorithm for the discrete logarithm, Math. Notes, 55(2), 1994, pages:165～172.
[NIST93] Natioard Institute of Standards and Technology, Digital Signature Standard, FIPS Publication 186,1993.
[NR93] K. Nyberg and R. A. Rueppel, A new signature scheme based on the DSA giving message recovery, in 1st ACM Conf on Computer and Communication Security, Fairfax, VA, 1993, pages:58～61.
[NY90] M. Naor and M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, In 22nd Annual ACM Symposium on Theory of Computing, 1990, pages:427～437.
[OO98] K. Ohta and T. Okamoto, On concrete security treatment of signatures derived from identification, In Crypto'98, LNCS 1462, Springer-Verlag, 1998, pages:354～369.
[OP011] T. Okamoto and D. Pointcheval, The gap-problems: a new class of problems for the security of cryptographic schemes, In Proc. 2001 Intemational Workshop on Practice and Theory in Public Key Cryptography (PKC 2001), 2001.
[OP012] T.Okamoto and D. Pointcheval, REACT:Rapid Enhanced-security Asymmetric Cryptosystem Transform, In CT-RSA'2001, LNCS2020, Springer-Verlag, Berlin, 2001, pages: 159～175.
[OW99] P.C. Van Oorschot and Michael Wiener, Parallel collision search with cryptanalytic applications, Journal of Cryptology, 12(12), 1999, pages: 1～28.
[PH78] S.C.Polig and M.E.Hellman, An improved algorithm over GF(p) and its cryptographic significance, IEEE Transaction on Information Theory, 24, 1978, pages: 106～110.
[Pol78] J.M. Pollard, Monte Carlo methods for index computation (mod p), Mathematics of Computation, 32, 1978, pages:918～924.
[PS96] D. Pointcheval and J. Stem, Security proofs for signature schemes, Advances in Cryptology-Proceedings of EUROCRYPT '96 Springer-Verlag, LNCS 1070, pages:387～398.
[RS01] R. Cramer and V. Shoup, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, manuscript, December 17th, 2001, 62 p.
[RS91] C. Rackoff and D. Simon, Noninteractive zero-knowledge proof of knowledge and chosen ciphertext attack, In Advances in Cryptology-Crypto '91, 1991, pages:433～444.
[RSA78] R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM, 21(2), February 1978, pages: 120～126.
[SA98] T. Satoh and K. Araki, Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Commentarii Mathematici Universitatis Sancti Pauli, 47, 1998, pages:81～92.
[Sat00] T.Satoh, The canonical lift of an ordinary elliptic curves over a finite field and its point counting, J.Ramanujan Math. Soc., 15, 2000, pages:247～270.
[Sch85] R. School, Elliptic curves over finite fields and the computation of square roots rood p, Mathematics of Computation, 44, 1985, pages:483～494.
[Sch95] R. School, Counting points on elliptic curves over finite fields, Journal de Theorie des Nombres de Bordeaux, 7, 1995, pages:219～254.
[Sem98] I.A.Semaev, Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p, Mathematics of Computation, 67(221), January 1998, pages:353～356.
[Sha71] D.Shanks, Class number, a theory of factorizations and genera, In Proceedings of Symposia in Pure Mathematics, 1971, pages:415～440.
[Sho97] V. Shoup, Lower bounds for discrete logarithms and related problems, In Advances in Cryptology-Eurocrypt '97, 1997.
[Sho00] V. Shoup, Using hash functions as a hedge against chosen ciphertext attack, In
Advances in Cryptology-Eurocrypt 2000, 2000.
[Sho01] V. Shoup, OAEP reconsidered, In Advances in Cryptology-Crypto 2001,2001.
[Sil00] J.Silverman, The xedni calculus and the elliptic curve discrete logarithm problem, Design, Codes and Cryptology, 2000.
[Sil86] J.Silverman, The Arithmetic of Elliptic Curve, Springer-Verlag, New York,1986.
[Sma99] N.P. Smart, The discrete logarithms problem on elliptic curves of trace one, Journal of Cryptology, 12, 1999, pages: 193～196.
[SS97] R.Silverman and J.Stapleton, Contribution to ANSI X9F1 working group, 1997.
[SS98] J.Silverman and J.Suzuki, Elliptic curve discrete logarithms and the index calculus, Proc of Asiacrypt '98, 1998, pages: 110～125.
[SS99] J.Silverman and J.Suzuki, Elliptic curve discrete logarithms and the index calculus, Advance in Cryptology-Asiacrypt'98, Lecture Notes in Computer Science, Springer-Verlag, 1514, 1999, pages: 110～125.
[Ste97] A.Stein, Equivalences between elliptic curves and real quadratic congruence function fields, Journal de Theorie des Nombres de Bordeaux, 9, 1997, pages:75～95.
[TY98] Y.Tsiounis and M.Yung, On the security of E1Gamal based encryption, PKC'98, LNCS1431, Springer-Verlag, 1998, pages: 117～134.
[WZ99] M.Wiener and R.Zuccherato, Fast attacks on elliptic curve cryptosystems, Selected Areas in Cryptology, Lecture Notes in Computer Science, Springer-Verlag, 1556, 1999, pages:190～200.
[ZS92] Y. Zheng and J. Seberry, Practical approaches to attaining security against adaptively chosen ciphertext attacks, In Advances in Cryptology-Crypto '92,1992,pages:292～304.
[Zuc98] R.Zuccherato, The equivalance between elliptic curve and quadrtic function field discrete logarithms in characeristic 2, ANTS-Ⅲ, Lecture Notes in Computer Science, Springer-Verlag, 1423, 1998, pages:621～638.
[ADH94] L.Adleman J.Demarrais and M.D.Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobian of large genus hyperelliptic curves over finite fields, Proc First Int'l Symp on Algorithmic Number Theory (ANTS-Ⅰ), 1994, pages:28～40.
[AM93] A.O.L. Atkin and F. Morain. Elliptic curves and primality proving.Mathematics of Computation, 61(203), July 1993, pages:29～68.
[Atk91] A.O.L. Atkin, The number of points on an elliptic curves modulo a prime, Seriea of e-mails to the NMBRTHRY mailing list, 1991-1992.
[BDPR98] M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway, Relations among notions of security for public-key encryption schemes, In Advances in Cryptology-Crypto '98, 1998, pages:26～45.
[BK98] R. Balasubramanian and N.Koblitz, The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm, Journal of Cryptology, 11, 1998, pages: 141～145.
[BL96] D.Boneh and R.J.Lipton, Algorithms for black-box fields and their application to cryptography, In Advances in Cryptology-Crypto'96, 1996, pages:283～296.
[Ble98] D. Bleichenbacher, Chosen ciphertext attacks against protocols based on RSA encryption standard PKCS#1, Advances in Cryptology—CRYPTO'98 Proceedings, Springer-Verlag, 1998, pages: 1～12.
[BLK00] J. Baek, B. Lee, and K. Kim, Secure length-saving E1Gamal encryption under the computational Diffie-Hellman assumption, In Proc. 5th Australian Conference on Information, Security, and Privacy, 2000.
[Bon98] D. Boneh, The decision Diffie-Hellman problem, In Ants-Ⅲ, Springer, LNCS 1423, 1998, pages:48～63.
[Bro00] DRL. Brown, The exact security of ECDSA, Technical report, CORR 2000-54, Dept. of Combinatorics and Optimization, Univ. of Waterloo, 2000.
[BR93] M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, In First ACM Conference on Computer and
Communications Security, 1993, pages:62～73.
[BR94] M. Bellare and P. Rogaway, Optimal asymmetric encryption, In Advances in Cryptology -Eurocrypt '94, 1994, pages:92～111.
[CGH98] R. Canetti, O. Goldreich, and S. Halevi, The random oracle model, revisited, In 30th Annual ACM Symposium on Theory of Computing, 1998.
[Cor99] J.S. Coron, Resistance against differential power analysis for elliptic curve cryptosystems, Proceedings of CHES '99 (C. K. Ko_c and Chr. Paar, eds.), Lecture Notes in Computer Science, vol. 1717, Springer-Verlag, 1999, pages: 292～302.
[CS98] R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, In Advances in Cryptology,Crypto '98, 1998, pages: 13～25.
[CS01] R. Cramer and V. Shoup, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, Cryptology ePrint Archive, Report 2001/108, 2001. http://eprint.iacr.org.
[DDN91] D. Dolev, C. Dwork, and M. Naor, Non-malleable cryptography, In 23rd Annual ACM Symposium on Theory of Computing, 1991, pages:542～552.
[DDN98] D. Dolev, C. Dwork, and M. Naor, Non-malleable cryptography, 1998. Manuscript (updated, full length version of STOC paper).
[DH76] W. Diffie and M.F. Hellman, New direction in cryptology, IEEE Transactions on Information Theory, vo122, no.6, 1976, pagese:644～654.
[ElG85] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, 1985, 31, pages:469～472.
[Elk92] Noam D. Elkies, Explicit isogenies, manuscript, Boston, MA, 1992.
[Elk98] Noam D. Elldes, Elliptic and modular curves over finite fields and related computational issues, In D.A. Buell and J.T. Teitelbaum, editors, Computational Perspectives in Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin, (Chicago, IL, 1995), AMS, 1998. pages:21～76.
[FGH00] M. Fouquet, P.Gaudry, and R.Harley, An extention of Satoh's algorithm and its implementation, J.Ramanujan Math. Soc., 15, 2000, pages:281～318.
[FO99] E. Fujisaki and T. Okamoto, Secure integration of asymmetric and symmetric encryption schemes, In Advances in Cryptology-Crypto '99, 1999, pages:537～554.
[FOPS01] E. Fujisald, T. Okamoto, D. Pointcheval, and J. Stem, RSA-OAEP is secure under the RSA assumption, In Advances in Cryptology-Crypto'2001,2001.
[FOPS02] Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stem, RSA-OAEP is secure under the RSA assumption, Journal of Cryptology 24 (2002)
[FR94] G.Frey. and H. Rück, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of Computation, 62, 1994, pages:865～874.
[GHS02] P. Gaudry, F. Hess and N. Smart, Constructive and destructive facets of Weil descent on elliptic curves, Journal of Cryptology, 15, 2002, pages: 19～46.
[GLV] R.Gallant, R.Lambert and S. Vanstone, Improving the parallelized Pollard lambda serach on binary anomalous curves, to appear in Mathematics of Computation.
[GM84] S. Goldwasser and S. Micali, Probabilistic encryption, Journal of Computer and System Sciences, 28, 1984, pages: 270～299.
[Gor98] D. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, 1998, 27, pages: 129～146.
[Hus87] D.Husemller, Elliptic Curves, Springer-Verlag, New York, 1987.
[JM96] D. Johnson and S. Matya, Asymmetric encryption: evolution and enhancements, Cryptobytes, 2(1), 1996. http://www.rsasecurity.com/rsalabs.
[JM99] D. Johnson and A. Menezes, The elliptic curve digital signature algorithm (ECDSA), Technical report CORR 99-34, Dept. of C&O, University of Waterloo, 1999.
[JN01] A. Joux and K. Nguyen, Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups, Cryptology ePrint Archive, Report 2001/003, 2001. http ://eprint.iacr.org.
[KI00] Kazukuni Kobara and Hideki Imai, New chosen-plaintext attacks on the one-wayness of the modified McEliece PKC, Proposed at Asiacrypt 2000, pages:237-251.
[KJJ98] P. Kocher, J. Jaffe, and B. Jun, Introduction to differential power analysis and related attacks, http://www.cryptography.com/dpa/technical/, 1998.
[KJJ99] P. Kocher, J. Jaffe, and B. Jun,Differential power analysis, Proceedings of CRYPTO '99 (M. J. Wiener, ed.), Lecture Notes in Computer Science, vol. 1666, Springer-Verlag, 1999, pages:388～397.
[Kob87] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, 48, 1987, pages:203～209.
[Lan78] S.Lang, Elliptic Curve:Diophantine Analysis, Springer-Verlag, New York, 1978.
[LL94] C. Lim and P. Lee, More flexible exponentiation with precomputation,
Advances in Cryptology—Crypto'94, LNCS839, 1994, pages:95～107.
[Man01] J. Manger, A chosen ciphertext attack on RSA optimal asymmetric encryption padding (OAEP) as standardized in PKCS #1 v2.0, In Advances in Cryptology-Crypto 2001, 2001, pages:230～238.
[McC90] K. McCurley, The discrete logarithm problem, Cryptology and Computational Number Theory, 42, 1990, pages:49～74.
[MDS99] T. S. Messerges, E. A. Dabbish, and R. H. Sloan, Investigations of power analysis attacks on smartcards,Proceedings of USENIX Workshop on Smartcard Technology, 1999, pages: 151～161.
[Mil85] V. Miller, Uses of elliptic curves in cryptography, Advances in Cryptology-Crypto'85, LNCS218, 1986, pages:417～426.
[MOV93] A.Menezes T.Okamoto and S.Vanstone, Reducing elliptic cueve logarithms to logarithms in a finite field, IEEE Transaction on Information Theory, Vol.IT-39, 5, 1993, pages: 1639～1646.
[Nec94] V.I. Nechaev, Complexity of a determinate algorithm for the discrete logarithm, Math. Notes, 55(2), 1994, pages:165～172.
[NIST93] Natioard Institute of Standards and Technology, Digital Signature Standard, FIPS Publication 186,1993.
[NR93] K. Nyberg and R. A. Rueppel, A new signature scheme based on the DSA giving message recovery, in 1st ACM Conf on Computer and Communication Security, Fairfax, VA, 1993, pages:58～61.
[NY90] M. Naor and M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, In 22nd Annual ACM Symposium on Theory of Computing, 1990, pages:427～437.
[OO98] K. Ohta and T. Okamoto, On concrete security treatment of signatures derived from identification, In Crypto'98, LNCS 1462, Springer-Verlag, 1998, pages:354～369.
[OP011] T. Okamoto and D. Pointcheval, The gap-problems: a new class of problems for the security of cryptographic schemes, In Proc. 2001 Intemational Workshop on Practice and Theory in Public Key Cryptography (PKC 2001), 2001.
[OP012] T.Okamoto and D. Pointcheval, REACT:Rapid Enhanced-security Asymmetric Cryptosystem Transform, In CT-RSA'2001, LNCS2020, Springer-Verlag, Berlin, 2001, pages: 159～175.
[OW99] P.C. Van Oorschot and Michael Wiener, Parallel collision search with cryptanalytic applications, Journal of Cryptology, 12(12), 1999, pages: 1～28.
[PH78] S.C.Polig and M.E.Hellman, An improved algorithm over GF(p) and its cryptographic significance, IEEE Transaction on Information Theory, 24, 1978, pages: 106～110.
[Pol78] J.M. Pollard, Monte Carlo methods for index computation (mod p), Mathematics of Computation, 32, 1978, pages:918～924.
[PS96] D. Pointcheval and J. Stem, Security proofs for signature schemes, Advances in Cryptology-Proceedings of EUROCRYPT '96 Springer-Verlag, LNCS 1070, pages:387～398.
[RS01] R. Cramer and V. Shoup, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, manuscript, December 17th, 2001, 62 p.
[RS91] C. Rackoff and D. Simon, Noninteractive zero-knowledge proof of knowledge and chosen ciphertext attack, In Advances in Cryptology-Crypto '91, 1991, pages:433～444.
[RSA78] R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM, 21(2), February 1978, pages: 120～126.
[SA98] T. Satoh and K. Araki, Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Commentarii Mathematici Universitatis Sancti Pauli, 47, 1998, pages:81～92.
[Sat00] T.Satoh, The canonical lift of an ordinary elliptic curves over a finite field and its point counting, J.Ramanujan Math. Soc., 15, 2000, pages:247～270.
[Sch85] R. School, Elliptic curves over finite fields and the computation of square roots rood p, Mathematics of Computation, 44, 1985, pages:483～494.
[Sch95] R. School, Counting points on elliptic curves over finite fields, Journal de Theorie des Nombres de Bordeaux, 7, 1995, pages:219～254.
[Sem98] I.A.Semaev, Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p, Mathematics of Computation, 67(221), January 1998, pages:353～356.
[Sha71] D.Shanks, Class number, a theory of factorizations and genera, In Proceedings of Symposia in Pure Mathematics, 1971, pages:415～440.
[Sho97] V. Shoup, Lower bounds for discrete logarithms and related problems, In Advances in Cryptology-Eurocrypt '97, 1997.
[Sho00] V. Shoup, Using hash functions as a hedge against chosen ciphertext attack, In
Advances in Cryptology-Eurocrypt 2000, 2000.
[Sho01] V. Shoup, OAEP reconsidered, In Advances in Cryptology-Crypto 2001,2001.
[Sil00] J.Silverman, The xedni calculus and the elliptic curve discrete logarithm problem, Design, Codes and Cryptology, 2000.
[Sil86] J.Silverman, The Arithmetic of Elliptic Curve, Springer-Verlag, New York,1986.
[Sma99] N.P. Smart, The discrete logarithms problem on elliptic curves of trace one, Journal of Cryptology, 12, 1999, pages: 193～196.
[SS97] R.Silverman and J.Stapleton, Contribution to ANSI X9F1 working group, 1997.
[SS98] J.Silverman and J.Suzuki, Elliptic curve discrete logarithms and the index calculus, Proc of Asiacrypt '98, 1998, pages: 110～125.
[SS99] J.Silverman and J.Suzuki, Elliptic curve discrete logarithms and the index calculus, Advance in Cryptology-Asiacrypt'98, Lecture Notes in Computer Science, Springer-Verlag, 1514, 1999, pages: 110～125.
[Ste97] A.Stein, Equivalences between elliptic curves and real quadratic congruence function fields, Journal de Theorie des Nombres de Bordeaux, 9, 1997, pages:75～95.
[TY98] Y.Tsiounis and M.Yung, On the security of E1Gamal based encryption, PKC'98, LNCS1431, Springer-Verlag, 1998, pages: 117～134.
[WZ99] M.Wiener and R.Zuccherato, Fast attacks on elliptic curve cryptosystems, Selected Areas in Cryptology, Lecture Notes in Computer Science, Springer-Verlag, 1556, 1999, pages:190～200.
[ZS92] Y. Zheng and J. Seberry, Practical approaches to attaining security against adaptively chosen ciphertext attacks, In Advances in Cryptology-Crypto '92,1992,pages:292～304.
[Zuc98] R.Zuccherato, The equivalance between elliptic curve and quadrtic function field discrete logarithms in characeristic 2, ANTS-Ⅲ, Lecture Notes in Computer Science, Springer-Verlag, 1423, 1998, pages:621～638.