International Journal of Computer
Trends and Technology

Research Article | Open Access | Download PDF

Volume 3 | Issue 4 | Year 2012 | Article Id. IJCTT-V3I4P125 | DOI : https://doi.org/10.14445/22312803/IJCTT-V3I4P125

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

Sushila Vishnoi, Vishal Shrivastava

Citation :

Sushila Vishnoi, Vishal Shrivastava, "A new Digital Signature Algorithm based on Factorization and Discrete Logarithm problem," International Journal of Computer Trends and Technology (IJCTT), vol. 3, no. 4, pp. 510-513, 2012. Crossref, https://doi.org/10.14445/22312803/IJCTT-V3I4P125

Abstract

Generally, digital signature algorithms are based on a single hard problem like prime factorization problem, discrete logarithm problem, elliptic curve problem. If one finds solution of this single hard problem then these digital signature algorithms will no longer be secured and due to large computational power, this may be possible in future. There are many other algorithms which are based on the hybrid combination of prime factorization and discrete logarithms problem but different weaknesses and attacks have been developed against those algorithms. This paper also presents a new variant of digital signature algorithm which is based on two hard problems, prime factorization and discrete logarithm.

Keywords

Digital Signature; Discrete logarithm; Factorization; Cryptanalysis.

References

[1]. D. Boneh and D. Brumley. Remote timing attacks are practical. Proceedings of 12th USENIX Security Symposium, 2003.
[2]. D. Boneh, G. Durfee, and Y. Frankel. Exposing an RSA private key given a small fraction of its bits. Full version of the work from Asiacrypt, 98, 1998. International Journal of Computer Trends and Technology- volume3Issue4- 2012
[3]. D. Boneh and H. Shacham. Fast variants of RSA. CryptoBytes (RSA Laboratories), 5:1-9, 2002.
[4]. B. De Weger. Cryptanalysis of RSA with small prime difference. Applicable Algebra in Engineering, Communication and Computing, 13(1):17-28, 2002.
[5]. W. Di_e and M. Hellman. New directions in cryptography. Information Theory, IEEE Transactions on, 22(6):644-654, 2002.
[6]. T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. Information Theory, IEEE Transactions on, 31(4):469- 472, 2002.
[7]. D. M. Gordon. Discrete Logarithms in GF(P) Using the Number Field Sieve. SIAM Journal on Discrete Mathematics, 6(1):124-138, 1993.
[8]. L. Harn. Public-key cryptosystem design based on factoring and discrete logarithms. In IEE Proc.-Compul. Digit. Tech, volume 141, pages 193195. IET, 1994.
[9]. L. Harn. Comment: Enhancing the security of El Gamal's signature scheme. IEE Proceedings-Computers and Digital Techniques, 142:376, 1995.
[10]. T. Hayashi, N. Shinohara, L. Wang, S. Matsuo, M. Shirase, and T. Takagi. Solving a 676-Bit Discrete Logarithm Problem in GF (3 6n). Public Key Cryptography-PKC 2010, pages 351-367, 2010.
[11]. J. He and T. Kiesler. Enhancing the security of El Gamal's signature scheme. In Computers and Digital Techniques, IEE Proceedings-, volume 141, pages 249-252. IET, 1994.
[12]. W. H. He. Digital signature scheme based on factoring and discrete loga- rithms. Electronics Letters, 37(4):220-222, 2002.
[13]. M.J. Hinek. Cryptanalysis of RSA and its variants. Chapman & Hall/CRC, 2009.
[14]. ES Ismail, NMF Tahat, and RR Ahmad. A New Digital Signature Scheme Based on Factoring and Discrete Logarithms. Journal of Mathematics and Statistics, 4(4):222-225, 2008.
[15]. B.Kaliski. TWIRL and RSA Key Size. http://www.rsa.com/rsalabs/node.asp?id=2004, 2003, Accessed on Nov. 2010.
[16]. P. Kocher. Timing attacks on implementations of Di_e-Hellman, RSA, DSS, and other systems. In Advances in CryptologyCRYPTO96, pages 104-113. Springer, 1996.
[17]. 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.
[18]. NY Lee. Security of Shao's signature schemes based on factoring and discrete logarithms. In Computers and Digital Techniques, IEE Proceedings-,volume 146, pages 119-121. IET, 2002.
[19]. ] N.Y. Lee and T. Hwang. Modi_ed Harn signature scheme based on factorizing and discrete logarithms. In Computers and Digital Techniques, IEE Proceedings-, volume 143, pages 196-198. IET, 2002.
[20]. N.Y. Lee and T. Hwang. The security of He and Kiesler's signature schemes. In Computers and Digital Techniques, IEE Proceedings-, volume 142, pages 370-372. IET, 2002.
[21]. J. Li and G. Xiao. Remarks on new signature scheme based on two hard problems. Electronics Letters, 34(25):2401, 2002.
[22]. P.L. Montgomery. A survey of modern integer factorization algorithms. CWI quarterly, 7(4):337-365, 1994.
[23]. M.A. Morrison and J. Brillhart. A Method of Factoring and the Factorization of F 7. Mathematics of Computation, 29(129):183-205, 1975.
[24]. J.M. Pollard and C.P. Schnorr. An efficient solution of the congruence x2+ ky2= m (mod n). IEEE Transactions on Information Theory, 33(5):702- 709, 1987.
[25]. C. Pomerance. A tale of two sieves. Biscuits of Number Theory, page 85, 2008. [26]. D. Poulakis. A variant of Digital Signature Algorithm. Designs, Codes and Cryptography, 51(1):99-104, 2009.
[27]. R.L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120-126, 1978.
[28]. Z. Shao. Signature schemes based on factoring and discrete logarithms. In Computers and Digital Techniques, IEE Proceedings-, volume 145, pages 33-36. IET, 2002.
[29]. 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.
[30]. 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.
[31]. S. Wei. A New Digital Signature Scheme Based on Factoring and Discrete Logarithms. Progress on Cryptography, pages 107-111, 2004. [32]. S. Wei. A New Digital Signature Scheme Based on Factoring and Discrete Logarithms. Progress on Cryptography, pages 107-111, 2004.