Research Article
Lattice based Attacks on Small Private Exponent of RSA: A Survey
|
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
|
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
Keywords