Research Article

Lattice based Attacks on Small Private Exponent of RSA: A Survey

by  R. Santosh Kumar, C. Narasimham, S. Pallam Setty
journal cover
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 49 - Issue 19
Published: July 2012
Authors: R. Santosh Kumar, C. Narasimham, S. Pallam Setty
10.5120/7878-1187
PDF

R. Santosh Kumar, C. Narasimham, S. Pallam Setty . Lattice based Attacks on Small Private Exponent of RSA: A Survey. International Journal of Computer Applications. 49, 19 (July 2012), 28-31. DOI=10.5120/7878-1187

                        @article{ 10.5120/7878-1187,
                        author  = { R. Santosh Kumar,C. Narasimham,S. Pallam Setty },
                        title   = { Lattice based Attacks on Small Private Exponent of RSA: A Survey },
                        journal = { International Journal of Computer Applications },
                        year    = { 2012 },
                        volume  = { 49 },
                        number  = { 19 },
                        pages   = { 28-31 },
                        doi     = { 10.5120/7878-1187 },
                        publisher = { Foundation of Computer Science (FCS), NY, USA }
                        }
                        %0 Journal Article
                        %D 2012
                        %A R. Santosh Kumar
                        %A C. Narasimham
                        %A S. Pallam Setty
                        %T Lattice based Attacks on Small Private Exponent of RSA: A Survey%T 
                        %J International Journal of Computer Applications
                        %V 49
                        %N 19
                        %P 28-31
                        %R 10.5120/7878-1187
                        %I Foundation of Computer Science (FCS), NY, USA
Abstract

Lattice basis reduction algorithms have contributed a lot to cryptanalysis of RSA crypto system. With coppersmith's theory of polynomials, these algorithms are searching for the weak instances of Number-theoretic cryptography, mainly RSA. In this paper we present several lattice based attacks on low private exponent of RSA.

References
  • Cohen, H. 1995. A Course in Computational Algebraic Number Theory. Springer-Verlag. Second edition.
  • Menezes, A. J, Van Oorschot P. C, and Vanstone. 1997. Hand book of Applied Cryptography. CRC Press.
  • Lenstra A. K, Lenstra Jr. H. W, Lovasz L. 1982. "Factoring polynomials with rational coefficients". Mathematische A1nnalen, volume 261(4): pages 515-534.
  • Rivest R. L, Shamir A, Adleman L. 1978. "A method for obtaining digital signatures and public key cryptosystems". Commun. of the ACM, 21: 120-126.
  • Coppersmith D. 1997. "Small solution to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology", 10(4):233-260.
  • Howgrave-Graham N. 1997. Finding small roots of univariate modular equations revisited. Proceedings of Cryptography and Coding, Springer-LNCS, vol. 1355, Springer-Verlag, pp. 13-142.
  • Wiener M. J. 1990. Cryptanalysis of short RSA secret exponents. IEEE Trans. In formation Theory, 36(3):553:559.
  • Boneh. D, and Durfee,G. 2000. Cryptanalysis of RSA with private key d less than N^0. 292. IEEE Transactions on information Theory, 46(4):1339-1349.
  • D. Boneh, G. Durfee,Y. Frankel. 1998 An attack on RSA given fraction of the private key bits. Proceeding of Asiacypt'98. Springer-Verlag, LNCS 1514:25-34.
  • M. Ernst, E. Jochemsz, A,May, and D. Weger 2005. Partial key exposure attacks on RSA upto full size exponents. Advances in Cryptology –Eurocrypt 2005. Springer-Verlag, LNCS 3494:371-386.
  • P. Schnorr and M. Euchner. 1994. Lattice basis reduction: Improved practical algorithms and solving subset sum problems Math. Prog. 66: 181- 199.
  • Blomer, May. 2001. Low Secret Exponent RSA Revisited. Cryptography and Lattice Conference (CaLC 2001). Springer Lecture Notes in Computer Science Volume 2146 .
  • Santosh kumar R, Narasimham C, Pallam setty S. 2012 Lattice based tools for cryptanalysis in various applications. Springer-LNICST, 84:530-537.
  • Boneh. ,D. 1999. Twenty Years of Attacks on the RSA Cryptosystem. Notices the AMS 46(2), 203-213.
  • Durfee, G, Nguyen, P. Q. 2000. Crtptanalysis of the RSA schemes with short exponent from Asiacrypt '99. Proceedings of cryptography-ASIACRYPT, LNCS 1976, Springer-Verlag, pp 1-11.
  • H. M. Sun, W. C Yang, C. S. Laih. 1999. On the design of RSA with short secret exponent. Proceedings of Cryptology –ASIACRYPT'99,LNCS 1716, Springer-Verlag, pp. 120-126,1978.
  • Verhaul, E. , van Tilborg. 1997. "Cryptanalysis of less short RSA secret exponents". Applicable Algebra of Engineering, Communication and Computing, Vol. 8, Springer-Verlag, pp. 425-435.
  • Aono,Y. 2009. Simplification of the lattice based attack of Boneh and Durfee for RSA cryptoanalysis. Proceedings of joint conference of ASCM and MACS.
  • Victor Shoup. NTL: A library for doing Number Theory, online available at http://shoup. net/ntl.
Index Terms
Computer Science
Information Sciences
No index terms available.
Keywords

Lattices Lattice basis reduction RSA Cryptanalysis

Powered by PhDFocusTM