Remarks on new Digital Signature Algorithm based on Factorization and Discrete Logarithm problem

  IJCOT-book-cover
 
International Journal of Computer Trends and Technology (IJCTT)          
 
© - September Issue 2013 by IJCTT Journal
Volume-4 Issue-9                           
Year of Publication : 2013
Authors :Shin-Yan Chiou, Yi-Xuan He

MLA

Shin-Yan Chiou, Yi-Xuan He"Remarks on new Digital Signature Algorithm based on Factorization and Discrete Logarithm problem"International Journal of Computer Trends and Technology (IJCTT),V4(9):3322-3324 September Issue 2013 .ISSN 2231-2803.www.ijcttjournal.org. Published by Seventh Sense Research Group.

Abstract:- Most digital signature schemes have the common feature that they are based on a single cryptographic assumption, like integer factorization problem (IFP) or discrete logarithm problem (DLP). For example, RSA scheme is based on the IFP, and ElGamal scheme is based on the DLP. So far, these hard problems still cannot be solved efficiently and we believe that the schemes are secure. However, if these problems can be solved by an efficient method in the future, the associated cryptographic scheme will no longer be secure. Thus, people try to enhance the security of cryptographic schemes by constructing them based on multiple hard problems simultaneously. Recently, S. Vishnoi and V. Shrivastava proposed a new signature scheme which is based on factorization and discrete logarithm problem, denoted as V & S scheme in this paper. S. Vishnoi and V. Shrivastava claimed that their scheme is secure and its security is based on the difficulty of computing factoring and discrete logarithms. In this paper, we show that this scheme is not secure and is not based on any hard problems; a simple attack is given.

 

References -
[1] W.Diffie and M. E.Hellman, “New direction in cryptography,” IEEE Transaction on Information Networking and Application, pp. 557–560, 1975.
[2] R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signature and public-key cryptosystem,” Communications of the ACM, vol. 21, no. 2, pp. 120–126, 1978.
[3] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Transaction on Information Theory, vol. IT-31, no. 4, pp. 469–472, 1985.
[4] S. Pohlig and M. Hellman, “An improved algorithm for computing logarithms over GF p( ) ,” Information Theory, IEEE Transactions on 24.1: 106-110, 1978.
[5] K. S. McCurley, “A key distribution system equivalent to factoring,” Journal of cryptology, 1.2 : 95-105 , 1988.
[6] L. Harn, “Public-key cryptosystem design based on factoring and discrete logarithms,” IEE Proceedings-Computers and Digital Techniques, 141.3: 193-195, 1994.
[7] J. He and T. Kiesler, “Enhancing the security of El Gamal`s signature scheme,” IEE Proceedings-Computers and Digital Techniques, 141.4: 249-252, 1994.
[8] N. Y. Lee and T. Hwang, “Modified Harn signature scheme based on factorizing and discrete logarithms,” IEE Proceedings-Computers and Digital Techniques 143.3:196-198, 1996.
[9] C. S. Laih and W. C. Kuo, “New signature schemes based on factoring and discrete logarithms,” IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences 80.1: 46-53, 1997.
[10] Z. Shao, “Signature schemes based on factoring and discrete logarithms,” Computers and Digital Techniques, IEE Proceedings-. Vol. 145. No. 1. IET, 1998.
[11] W. H. He, “Digital signature scheme based on factoring and discrete logarithms,” Electronics Letters 37.4: 220-222, 2001.
[12] Z. Shao, “Digital signature schemes based on factoring and discrete logarithms,” Electronics Letters 38.24: 1518-1519, 2002.
[13] S. F. Tzeng, C. Y. Yang, and M. S. Hwang, “A new digital signature scheme based on factoring and discrete logarithms,” International Journal of Computer Mathematics 81.1: 9-14, 2004.
[14] S. Wei, “A New Digital Signature Scheme Based on Factoring and Discrete Logarithms,” Progress on Cryptography : 107, 2004.
[15] E. S. Ismail, N. M. F. Tahat, and R. R. Ahmad, “A new digital signature scheme based on factoring and discrete logarithms,” Journal of Mathematics and Statistics 4.4: 222, 2008.
[16] D. Poulakis, “A variant of digital signature algorithm,” Designs, codes and cryptography 51.1: 99-104, 2009.
[17] L. Harn, “Enhancing the security of El Gamal`s signature scheme,” Computers and Digital Techniques, IEE Proceedings-. Vol. 142. No. 5. IET, 1995.
[18] N. Y. Lee and T. Hwang, “The security of He and Kiesler`s signature schemes,” IEE Proceedings-Computers and Digital Techniques 142.5: 370-372, 1995.
[19] J. Li and G. Xiao, “Remarks on new signature scheme based on two hard problems,” Electronics letters 34.25: 2401, 1998.
[20] N. Y. Lee, “Security of Shao`s signature schemes based on factoring and discrete logarithms,” IEE Proceedings-Computers and Digital Techniques146.2: 119-121, 1999.
[21] M. S. Hwang, C. C. Yang, and S. F. Tzeng, “Improved digital signature scheme based on factoring and discrete logarithms,” Journal of Discrete Mathematical Sciences and Cryptography 5.2: 151-155, 2002.
[22] C. T. Wang, C. H. Lin, and C. C. Chang, “Signature schemes based on two hard problems simultaneously,” Advanced Information Networking and Applications, 2003. AINA 2003. 17th International Conference on. IEEE.
[23] Z. Shao, “Security of a new digital signature scheme based on factoring and discrete logarithms,” International Journal of Computer Mathematics 82.10: 1215-1219, 2005.
[24] H. Qian, Z. Cao, and H. Bao, “Cryptanalysis of Li–Tzeng–Hwang’s improved signature schemes based on factoring and discrete logarithms,” Applied mathematics and computation 166.3: 501-505, 2005.
[25] S. Vishnoi and V. Shrivastava, “A new Digital Signature Algorithm based on Factorization and Discrete Logarithm problem,” International Journal of Computer Trends and Technology (IJCTT) 3.4, 2012.

Keywords :— Digital signature, Discrete logarithm, Factorization, Cryptanalysis, Forge .