臺灣博碩士論文加值系統

在密碼學中，離散對數問題是一個極受重視並且廣泛應用的研究主題。有許多的公開金鑰密碼系統，其安全性便是建立在解離散對數的難題上。本論文中，我們將討論一些以離散對數為基礎的密碼系統之安全性，諸如：Ghodosi 與Saeednia的群體式自我認證密碼系統，及Seo與Sweeney的可驗證式金鑰交換系統等一系列相關研究的安全性分析與改進。
此外，我們更進一步提出一個實用的轉換模型，將此類以離散對數為基礎的密碼系統轉換成以名稱為驗證基礎的系統，並保有原系統的安全等級。我們的方法只是一個轉換的前置作業，即可引入以名稱為驗證基礎系統的觀念。如此一來，便能享有驗證容易、不易偽造等多項以名稱為驗証基礎系統的好處。

The discrete logarithm problem has played an important role in the construction of some cryptographic protocols. Hence, many of the most widely used public key cryptosystems are based on the assumption that the discrete logarithm is indeed hard to compute. In this thesis, we discuss the security of some cryptosystems based on discrete logarithm, such as Ghodosi and Saeednia’s self-certified group-oriented cryptosystem and Seo and Sweeney’s simple authenticated key agreement protocol.
In addition, we further construct a practical model that embeds the concept of an ID-Based system into all of the cryptosystems based on the discrete logarithm, while maintaining the original security level. We not only design a transformation process to provide solutions rather than to re-invent a new scheme but also keep all the advantages of Identity-Based system such as the public-key forgeries prevention and identification and key management problem reduction.

Chapter 1 Introduction1
1.1 Background and Motivation1
1.2 Thesis Organization6
Chapter 2 Security of Self-Certified Group-Oriented Cryptosystem7
2.1 The Concept of the self-Certified Group-Oriented Cryptosystem7
2.1.1 Group-Oriented Cryptosystem7
2.1.2 Self-Certified Group-Oriented Cryptosystem8
2.2 Ghodosi and Saeednia’s Self-Certified Group-Oriented Cryptosystem8
2.3 Security Discussion10
Chapter 3 Security of Authenticated Key Agreement Protocol13
3.1 The Concept of Key Agreement Protocol13
3.2 The History of the Simple Authenticate Key Agreement Protocol (SAKA)16
3.2.1 Seo and Sweeney’s Simple Authenticated Key Agreement Protocol16
3.2.2 Tseng’s Security Enhancement for SAKA17
3.2.3 Ku and Wang’s Modified Authenticated Key Agreement Protocol18
3.2.4 Sun’s Attack20
3.2.5 Lin, Chang, and Hwang’s Security Enhancement for SAKA22
3.2.6 Hsieh et al.’s Attack22
3.3 Our Attacks23
3.3.1 Weaknesses of Ku et al.’s modified protocol23
3.4 Our Scheme26
3.5 Discussion and Security Analysis27
Chapter 4 Constructing ID-Based Cryptosystems for Discrete Logarithm Based Cryptosystems30
4.1 The Concept and History of ID-Based Cryptosystems30
4.2 Our Scheme31
4.2.1 Motivation31
4.2.2 Proposed Scheme32
4.2.3 Our ID-Based transformation model35
4.2.4 Example36
4.3 Discussion and Security Analysis38
Chapter 5 Conclusions41
References42

[1]M. Abe, and T. Okamoto, “Delegation Chains Secure up to Constant Length,” IEICE Trans. Fundamentals, Vol. E85-A, No. 1, pp. 110-116, 2002.[2]R. J. Anderson, and T. M. A. Lomas, “Fortifying Key Negotiation Schemes with Poorly Chosen Passwords,” Electronics Letters, Vol. 30, No. 13, pp. 1040-1041, 1994.[3]S. M. Bellovin, and M. Merritt, “Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks,” Proceedings 1992 IEEE Computer Society Conf. Research in Security and Privacy, pp. 72-84, 1992.[4]D.E.R. Denning, Cryptography and Data Security. Addison-Wesley, Reading, Mass., 1982.[5]W. Diffie, and M. E. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, Vol. IT-22, No. 6, pp. 644-654, 1976.[6]T. ElGamal, “A public-key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Transactions on Information Theory 31 (4), pp. 469-472, 1985.[7]D. M. Gordon, “Discrete logarithms using the number field sieve,” Preprint, 28 Mar. 1991.[8]C. G. Gunther, “An identity-based key exchange protocol,” Advances in Cryptology — Eurocrypt ‘89, Springer-Verlag, New York, pp. 29-37, 1989.[9]H. Ghodosi H., and S. Saeednia, “Modification to Self-certified Group-oriented Cryptosystem without Combiner,” Electronics Letters, Vol. 37, No. 2, pp. 1453-1454, 2001.[10]B. T. Hsieh, H. M. Sun, T. Hwang, “Cryptanalysis of enhancement for simple authentication key agreement algorithm,” Electronics Letters, Vol. 38, No. 1, pp. 20-21, 2002.[11]D. Knuth, The Art of Computer Programming: Volume 2 Seminumerical Algorithms, 2nd edition, Addison-Wesley, Chapter 4.5.2, Theorem D, pp. 324, 1981.[12]W. C. Ku, and S. D. Wang, “Cryptanalysis of modified authenticated key agreement protocol,” Electronics Letters, Vol. 36, No. 21, pp. 1770-1771, 2000.[13]B. A. LaMacchia, and A.M. Odlyzko, “Computation of discrete logarithms in prime fields,” Designs, Codes, and Cryptography, Vol. 1, pp. 46-62, 1911.[14]C. H. Lim and P. J. Lee, “Modified Maurer-Yacobi’s scheme and its application,” in: Proc. Auscrypt’92, pp. 308-323.[15]I. C. Lin, C. C. Chang, and M. S. Hwang, “Security Enhancement for the Simple Authentication Key Agreement Algorithm,” COMPSAC 2000. The 24th Annual International, pp. 113 -115, 2000.[16]W. B. Lee, and C.C. Chang, “On key changeable ID-Based digital signature scheme,” Journal of Information Science and Engineering, Vol. 12, No. 3, pp. 381-386, 1996.[17]A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, “Handbook of applied cryptography,” CRC Press, Inc., 1996.[18]T. Matsumoto, H. lmai, “On the key predistribution system,” Advances in Cryptology — Eurocrpt ’89, Springer-Verlag, New York, pp.29-37.[19]U. M. Maurer, Y. Yacobi, “A remark on a noninteractive public-key distribution system,” in: Proc. Eurocrpt ’92, pp. 458-460, 1993.[20]U. M. Maurer, Y.Yacobi, “A non-interactive public-key distribution system,” Designs, Codes Cryptography 9 (3) 1996, pp. 305-316.[21]U. M. Maurer, Y. Yacobi, “Non-interactive public key cryptography,” Advances in Cryptology — Eurocrypt ’91, Springer-Verlag, Now Youk, pp.498-507, 1991.[22]National Institute of Standards and Technology, NIST FIPS PUB 186, “Digital Signature Standard,” U.S. Department of Commerce, 1994.[23]E. Okamoto, and K. Tanaka, “Identity-based information Security Management for personal computer networks,” IEEE J. Selected Areas Commun., Vol. 7, No. 2, pp. 290-294, 1989.[24]E. Okamoto, and K. Tanaka, “Key distribution system based on identification information,” IEEE J. Selected Areas Commun. Vol. 7, No. 4, 481-485, 1989.[25]A. Shamir, “Identity-based cryptosystem and signature schemes,” Advances in Cryptology — Crypto ’84, Springer-Verlag, New York, pp. 47-53.[26]A. Shamir, “How to share a secret,” Commun. ACM. 22:612-613, 1979.[27]C. P. Schnorr, “Efficient Signature Generation for Smart Cards,” Journal of Cryptology, Vol. 4, No. 3, pp. 161-174, 1991.[28]D. Seo, and P. Sweeney, “Simple authenticated key agreement algorithm,” Electronics Letters, Vol. 35, No. 13, pp. 1073-1074, 1999.[29]H. Sun, “On the security of simple authenticated key agreement algorithm,” Proceedings of the Management Theory Workshop’2000, 2000.[30]S. Saryazdi, “An extension to ElGamal public key cryptosystem with a new signature scheme,” Communication, Control, and Signal Processing, Elsevier, pp. 194-198, 1990.[31]S. Saeednia, and H. Ghodosi, “A self-certified group-oriented cryptosystem without a combiner,” in PIEPRZYK, J., SAFAVI-NAINI, R., and SEBERY, J. (Eds.): Proc. ACISP ’99 — Australasian Conference on Information Security and Privacy, Lecture Notes in Computer Science, (Spring-Verlag, 1999), Vol. 1587, pp. 192-201.[32]W. SUSILO, and R. SAFAVI-NAINI, “Remark on Self-Certified Group-Oriented Cryptosystem without Combiner,” Electronics Letters, Vol.35, No.18, pp. 1539-1540, 1999.[33]H. Tanaka, “A realization scheme for the identity-based cryptosystem,” in Proc. Crypto’87, pp. 340-349.[34]Y. M. Tseng, and J. K. Jan, “ID-based cryptographic schemes using a non-interactive public-key distribution system,” The 14th Annual Computer Security Applications Conference, pp. 237-243, 1998.[35]Y. W. Tsai, and T. Hwang, “ID-based public key cryptosystems based on Okamoto and Tanaka’s ID-based one Way communication scheme,” Electron. Letters, Vol. 26, No. 10, pp. 666-668, 1990.[36]S. Tsujii, J. Chao, and K. Araki, “A simple ID-based for key sharing,” IEEE J. Selected Areas Commun., Vol. 11, No. 5, pp. 730-734, 1993.[37]S. Tsujii, and T. Itoh, K. Kurosawa, “ID-based cryptosystem using discrete logarithm problem,” Electron, Letters, Vol. 23, pp. 1318-1320, 1987.[38]Y. M. Tseng, “Weakness in simple authenticated key agreement protocol,” Electronics Letters, Vol. 36, No. 1, pp. 48-49, 2000.[39]A. L. Wells Jr., “A polynomial form for logarithms modulo a prime,” IEEE Transactions on Information Theory, pp. 845-846, 1984.