傳統的簽章方式必須使用書面的資料來加以簽名或蓋章，來確定彼此的權利與義務。然而在目前電子商務與電子化政府的時代，數位簽章是一個重要的應用，學會使用電子化的數位簽章也是一門重要的課題。我國已經在2001年10月31日通過電子簽章法，各種數位簽章演算法的安全性更是不可忽視。

　　一個完整的數位簽章系統必須達到「簽章文件的完整性」、「簽章者的鑑定性」與「簽章者的不可否認性」等功能。而一般的數位簽章系統可利用公開金鑰密碼系統或特定的演算法來達成。在這些密碼演算法中，我們可以根據其安全性的假設，將他們分為兩類。第一類為植基於解離散對數的數學難度假設之數位簽章演算法，在假設解離散對數的難題無法破解的前提之下，這種數位簽章演算法便是安全的；換句話說，如果解離散對數的難題可以破解，那麼這種數位簽章演算法也就同時變成不安全了。第二類為植基於解分解因數的數學難度假設之數位簽章演算法，同樣的在假設解分解因數的難題無法破解的前提之下，這種數位簽章演算法是安全的，也就是說，如果解分解因數的難題可以破解，那麼這種數位簽章演算法也就同樣的被破解了。

　　解離散對數與解分解因數這兩種數學難題，為世界上公認無法在有限合理的時間解開。但是若未來其中一種數學難題被破解，或者一個破密者在某種情況下，針對某特定演算法設計出一套方法，能夠破解其中一種數學難題，則此種數位簽章系統則會面臨到很大的威脅。所以若有一種數位簽章演算法，其安全性為同時基於解離散對數與解分解因數兩個難題，那麼即使將來有一種數學難題被破解，使用這種數位簽章演算法的系統依然是安全的。由此，採用同時基於兩個難度的數位簽章演算法，以加強系統的安全性，其重要性可見一斑。

　　在本論文中，我們特別針對同時基於解離散對數與解分解因數兩個數學難度的數位簽章演算法做研究與探討，並另外設計出一套完整的系統。我們首先針對個別解離散對數與解分解因數的數位簽章系統，分別介紹其代表性的數位簽章系統。接著，針對之前別人設計過的同時基於解離散對數與解分解因數兩個數學難度的數位簽章演算法，一一做詳細的介紹與分析，並整理出其攻擊方法跟探討其不安全的原因。最後在論文中，我們另外設計了一套同時基於解離散對數與解分解因數兩個數學難度的數位簽章演算法，並整理出其所有的變形。我們也證明了其安全性為基於同時解離散對數與解分解因數的數學難度。

　In the past, we made a signature by signing a name or affixing a seal on a document to establish the corresponding rights and duties. However since we are now in the age with Electronic Commerce and Electronic Government, the usage of digital signatures is very important. Learning how to use digital signatures is also significant. In addition, since the law of digital signature has been passed in October 31 2001, the security of digital signature schemes should not be ignored.

　A completed digital signature scheme should achieve the functions of “Integrity”, “Identification” and “Non-repudiation.” In general, a digital signature scheme can be achieved by a public key cryptosystem or by a special algorithm. For different security assumptions, we can divide digital signature algorithms into two categories. One is a digital signature scheme based on the discrete logarithm problem. Under the assumption that the discrete logarithm problem cannot be broken, this kind of digital signature scheme is secure. In other words if the discrete logarithm problem can be broken, this kind of digital signature scheme will become insecure. The other is a digital signature based on the factoring problem. Similarly under the assumption that the factoring problem cannot be broken, this kind of digital signature scheme is secure. That is, if the factoring problem can be broken, this kind of digital signature scheme will also be broken.

　The discrete logarithm problem and the factoring problem are two hard-solved mathematical problems, and the two problems are believed unsolved in a reasonable time-period in the world. However if any one of the two problems is solved in the future, the digital signature schemes based on this hard-problem assumption will become insecure. Hence if there is a digital signature algorithm of which the security is based on both the discrete logarithm problem and the factoring problem, the digital signature scheme will be still secure under the situation that any one of the two problems is solved. Therefore for the enhancement of system security, the adoption of the digital signature algorithm based on both assumptions is very important.

　In the dissertation, we specially have some researches and discussions on the digital signature algorithms based on both the discrete logarithm problem and the factoring problem. We also propose another digital signature scheme. Firstly aiming at the digital signature algorithms based on the discrete logarithm problem and the ones based on the factoring problem, we introduce some well-known and representative digital signature systems. Next focus on the digital signature algorithms based on two-hard-problem assumption, we have a detailed review on them and on their cryptanalysis methods. We also summarize the attacking methods and discuss the insecure reasons. Finally, we propose a digital signature scheme based on two assumptions and also list its all generations. Of course, we also proof that the security of the proposed scheme is based on both the discrete logarithm problem and the factoring problem.

[Abdalla & Reyzin 1976] M. Abdalla and L. Reyzin, “A New Forward-Secure Digital Signature Scheme,” Asiacrypto 2000, LNCS 1976, p. 116 ff.

[Agnew et al. 1990] G. B. Agnew, R. C. Mullin and S. A. Vanstone, “Improved Digital Signature Scheme Based on Discrete Exponentiation,” Electron. Lett., Vol. 26, No. 14, pp. 1024-1025, July 1990.

[Bellare & Rogaway 1993] M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in Proc. of 1st ACM Conference on Computer and Communications Security, 1993, pp. 62-73.

[Brickell & McCurley 1992] E. F. Brickell and K.S. McCurley, “An interactive identification scheme based on discrete logarithms and factoring,” J. Cryptology, vol.5, no.1, pp.29-40, 1992.

[Coron et al. 2000] J.S. Coron, M. Joye, D. Naccache, and P. Paillier, “New Attacks on PKCS#1 v1.5 Encryption,” Eurocrypt 2000.

[Diffie & Hellman 1976] W. Diffie and M. Hellman, “New Directions in Cryptography,” IEEE Trans. 1976, vol. IT-22, pp. 644-654.

[Ding & Laih 2002] L. Ding and C.S. Laih, “Comment: Digital signature scheme based on factoring and discrete logarithms,” 2002. (Unpublished.)

[ElGamal 1985] T. ElGamal, “A Public Key Cryptosystem and a Signature Scheme Based on the Discrete Logarithm,” IEEE Trans. on Information Theory, 1985, vol. IT-31, pp. 469-472.

[Grieu 2000] F. Grieu, “A Chosen Messages Attack on the ISO/IEC 9796-1 Signature Scheme,” Eurocrypt 2000, LNCS 1807, p. 70 ff.

[Girault & Misarsky 2000] M. Girault and J.F. Misarsky, “Cryptanalysis of Countermeasures Proposed for Repairing ISO 9796-1,” Eurocrypt 2000, LNCS 1807, p. 81 ff.

[Hada & Tanaka 1976] S. Hada and H. Tanaka, “A new approach to constructing a provably secure variant of Schnorr's identification scheme,” IEICE Trans. Fundamentals, vol.D78-A, no.9, pp.1154-1159, 1995.

[Harn1 1994] L. Harn, “New digital signature scheme based on discrete logarithm,” Electronics Letters Vol. 30 No. 5, 3 March 1994, pp. 396 –398.

[Harn2 1994] L. Harn, “Public-key Cryptosystem Design Based on Factoring and Discrete Logarithms,” IEE Proc.-Computers And Digital Techniques, vol.141, no.3, pp.193-195, 1994.

[Harn 1995] L. Harn, “Comment: Enhancing of the Security of ElGamal's Signature scheme,” IEE Proc.-E, 1995, Vol.142, No.5, p. 376.

[Harn & Gong 1997] L. Harn and G. Gong, “Digital signature with a subliminal channel,” Computers and Digital Techniques, IEE Proceedings- Volume: 144 6 , Nov. 1997 , pp. 387 –389.

[He 2001] W.H. He, “Digital Signature Scheme Based on Factoring and Discrete Logarithms,” Electronics Letters Vol. 37 No. 4, 15 Feb. 2001, pp. 220 –222.

[He & Kiesler 1994] J. He and T. Kiesler, “Enhancing the Security of ElGamal's Signature Scheme,” IEE Proc.-E, 1994, Vol.141, No.4, pp. 249-252.

[Horster et al. 1994] P. Horster, M. Michels and H. Petersen, “Meta-ElGamal Signature Schemes Using a Composite Module,” Technical Report TR-94-16-E, University of Technology Chemnitz-Zwickau, November, 1994.

[Horster et al. 1995] P. Horster, M. Michels and H. Petersen, “A Study of Signature Schemes Based on Discrete Logarithm and Factorization,” Technical Report TR-95-15-D, University of Technology Chemnitz-Zwickau, August, 1995.

[Horster & Petersen 1994] P. Horster and H. Petersen, “Classification of blind signature schemes and examples of hidden and weak blind signatures,” Presented at the Rump Session of Eurocrypt'94, Perugia, Italy, 1994.

[Jan & Tseng 1999] J.K. Jan and Y.M. Tseng, “New digital signature with subliminal channels based on the discrete logarithm problem,” Parallel Processing, 1999. Proceedings. 1999 International Workshops on , 1999 , pp. 198 - 203.

[Knobloch 1993] H. J. Knobloch, “A remark on the size of ElGamal-type digital signatures,” Draft version, 1993.

[Laih & Chiou 2002] C. S. Laih and S.Y. Chiou, “Cryptanalysis of An Optimized Protocol for Mobile Network Authentication and Security,” Information Processing Letters, 85, Apr. 2002, pp. 339-341.

[Laih & Kuo 1996] C. S. Laih and W. C. Kuo, “Cryptanalysis of Enhancing the Security of ElGamal's Signature Scheme,” Proc. Cryptography: Policy and Algorithms. Lecture Notes in Computer Science no. 1029, pp. 228-231, Springer-Verlag, Berlin Heidelberg, 1996.

[Laih & Kuo 1997] C.S. Laih and W.C. Kuo, “New Signature Schemes Based on Factoring and Discrete Logarithms,” IEICE Trans. Fundamentals, VOL. E80-A, No. 1 Jan. 1997, pp. 46-53.

[LaMacchia & Odlyzko 1991] B. LaMacchia and A. Odlyzko, “Computation of Discrete Logarithms in Prime Finite Fields,” Advances in Cryptology: Proceedings of Crypto '90 (Lecture Notes in Computer Science, Vol.537), Springer-Verlag, New York, 1991, pp. 616-618.

[Lee 1999] N. Y. Lee “ Security of Shao's Signature Schemes Based on Factoring and Discrete Logarithms,” IEE Proc., 1999, Vol.146, No.2, pp. 119-121.

[Lee & Hwang 1995] N. Y. Lee and T. Hwang, “The Security of He and Kiesler's Signature Schemes,” IEE Proc.-E, 1995, Vol.142, No.5, pp. 370-372.

[Lee & Hwang 1996] N. Y. Lee and T. Hwang, “Modified Harn signature scheme based on factoring and discrete logarithms,” IEE Proc. Computers And Digital Techniques, vol.143, no.3, pp.196-198,1996.

[Lenstra & Manasse 1990] A. K. Lenstra and M. S. Manasse, “Factoring By Electronic Mail,” Advances in Cryptology: Proceedings of Eurocrypt '89 (Lecture Notes in Computer Science, Vol.434), Springer-Verlag, New York, 1990, pp. 355-371.

[Lenstra & Verheul 1880] A. K. Lenstra and E. R. Verheul, “The XTR Public Key System,” Crypto 2000, LNCS 1880, p. 1 ff.

[Li & Xiao 1998] J. Li and G. Xiao, “Remarks on new signature scheme based on two hard problems,” Electronics Letters Volume: 34 25, 10 Dec. 1998, pp. 2401.

[Lim & Lee 1998] C.-H. Lim and P.-J. Lee, “A study on the proposed Korean digital signature algorithm,” Advances in Cryptology - Asiacrypt’98, LNCS 1514, Springer-Verlag, 1998, pp. 175-186.

[McCurley 1988] K.C. McCurley, “A key distribution system equivalent to factoring,” J. Cryptology, vol. 1, no.2, pp.95-106, 1988.

[McCurley 1990] K. C. McCurley, “The Discrete Logarithm Problem,” Proceedings of Symposia in Applied Mathematics, Providence, Rhode Island, 1990, Vol.42, American Mathematical Society, pp. 49-74.

[Michels et al. 1996] M. Michels, D. Naccache, and H. Petersen, GOST 34.10-A brief overview of Russia's DSA, Computers and Security, Vol. 15, No. 8, 1996, pp. 725-732.

[Moon et al. 1992] P.J. Moon, J.W. Lee, M.S. Jun, and C.H. Lee, “The new high-speed digital signature,” Local Computer Networks, 1992. Proceedings., 17th Conference on , 1992, pp. 262 –271.

[Naccache 1994] David Naccache, “Can O.S.S. be Repaired? Proposal for a New Practical Signature Scheme,” Advances in Cryptology: Proceedings of Eurocrypt '93 (Lecture Notes in Computer Science, Vol.765), Springer-Verlag, New York, 1994, pp. 233-239.

[NIST 1991] National Institute of Standards and Technology, “FIPS XX: Federal Information Processing Standard: Digital Signature Standard (DSS),” Aug. 1991, Vol. 56, No. 169, pp. 42980 – 42982..

[NIST 1992] National Institute of Standards and Technology, “The Digital Signature Standard,” Comm. ACM, July 1992, Vol.35, No.7, pp. 36-40.

[NIST 1994] National Institute of Standards and Technology, “FIPS 186: Federal Information Processing Standard: Digital Signature Standard,” May 1994.

[Nyberg & Rueppel 1993] K. Nyberg and R. Rueppel, “New signature schemes based on the discrete logarithm problem or how to add message recovery to the DSA,” preprint, Nov. 1993.

[Nyberg & Rueppel 1994] K. Nyberg and R. Rueppel, “Message Recovery For Signature SchemesBased on the DIscrete Logarithm Problem,” Pre-proceedings of Eurocrypt '94, 1994, pp.175-190.

[Odlyzko 1985] A. M. Odlyzko, “Discrete Logarithms and Their Cryptographic Significance,” (Lecture Notes in Computer Science, Vol.209), Springer-Verlag, New York, 1985, pp. 224-314.

[Odlyzko 2000] A. M. Odlyzko, “Discrete logarithms: The past and the future,” Designs, Codes, and Cryptography 19 (2000), pp. 129-145.

[Okamoto 1990] T. Okamoto, “A fast signature scheme based on congruential polynomial operations,” Information Theory, IEEE Transactions on Volume: 36 1, Jan. 1990, pp. 47 –53.

[Ong et al. 1984] H. Ong, C. Schnorr and A. Shamir, “An Efficient Signature Scheme Based On Quadratic Equations” in Proceedings of the 16th Symposium on the Theory of Computing, Washington, 1984, pp. 208-216.

[Pointcheval & Stern 1996] D. Pointcheval and J. Stern, “Security proofs for signature schemes,” in Advances in Cryptology - Eurocrypt’96, LNCS 1070, Springer-Verlag, 1996, pp. 387-398.

[Pomerance 1982] C. Pomerance, “Analysis and Comparison of Some Integer Factoring Algorithms,” Computational Methods in Number Theory, 1982, Vol.154, pp. 89-139.

[Pomerance 1990] C. Pomerance, “Factoring,” Proceedings of Symposia in Applied Mathematics, Providence, Rhode Island, 1990, Vol.42, American Mathematical Society, pp. 27-48.

[Pollard & Schnorr 1987] J. Pollard and C. Schnorr, “An Efficient Solution of the Congruence x2 + ky2 = m mod n,” IEEE Trans. on Information Theory, 1987, vol. IT-33 , pp. 17-28.

[Rabin 1979] M. O. Rabin, “Digitalized Signatures and Public-Key Functions as Intractable as Factorization,” MIT/LCS/TR-212, MIT Lab. for Computer Science, Cambridge, Mass. (Jan. 1979).

[Rivest et al. 1978] R. L. Rivest, A. Shamir and L. Adleman, “ A Method for Obtaining Digital Signatures and Public-key Cryptosystem,” Communications of the ACM, Vol. 21, pp. 120-126, 1978.

[Schneier 1996] Bruce Schneier, “Applied Cryptography,” 2nd, John Wiley & Sons, Inc., 1996.

[Schnorr 1990] C. P. Schnorr, “Efficient Identification and Signatures for Smart Cards,” Advances in Cryptology: Proceedings of Eurocrypt '89 (Lecture Notes in Computer Science, Vol.434), Springer-Verlag, New York, 1990, pp. 688-689.

[Shao1 1998] Z. Shao, “Signature scheme based on discrete logarithm without using one-way hash function,” Electronics Letters Volume: 34 11 , 28 May 1998, pp. 1079 - 1080.

[Shao2 1998] Z. Shao, “Signature schemes based on factoring and discrete logarithms,” Computers and Digital Techniques, IEE Proceedings- Volume: 145 1 , Jan. 1998, pp. 33 –36.

[Simmons 1992] G. J. Simmons ed., “Contemporary Cryptology: An Introduction, in Contemprtary Cryptology: The Science of Information Integrity,” Piscatoway, p.274, N.J.IEEE Press, 1992.

[Sun 2002] H.M. Sun, “Cryptanalysis of a digital signature scheme based on factoring and discrete logarithms,” NCS, 2002.

[Tiersma 1997] H. J. Tiersma, “Enhancing the security of El Gamal's signature scheme,” Computers and Digital Techniques, IEE Proceedings- Volume: 144 1 , Jan. 1997 , pp. 47 - 48.

[Yen & Laih 1993] S.M. Yen and C.S. Laih , “New Digital Signature Scheme Based onDiscrete Logarithm,” Electornics Letters, Vol.29, No.12, 1993, pp.1120-1121.

[Yen & Laih 1995] S.M. Yen and C.S. Laih, “Improved Digital Signature Algorithm,” IEEE Trans. on Computers, Vol.44, No.5, May 1995, pp.729-730.

[Yeun et al. 1998] C.Y. Yeun, C.J. Mitchell, and S.L. Ng, “Signature scheme based on discrete logarithm without using one-way hash-function,” Electronics Letters Volume: 34 24, 26 Nov. 1998, pp. 2329 - 2330.

[Yi el al. 1998] Xun Yi, Eiji Okamoto, and Kwok Yan Lam, “An optimized Protocol for Mobile Network Authentication and Security,” ACM Mobile Computing and Communications Review, Vol. 2, No. 3, 1998, pp. 37-39.