Research Article
Generalization of Boneh and Durfee’s Attack for Arbitrary Public Exponent RSA
|
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/7880-1190
|
R. Santosh Kumar, C. Narasimham, S. Pallam Setty . Generalization of Boneh and Durfee’s Attack for Arbitrary Public Exponent RSA. International Journal of Computer Applications. 49, 19 (July 2012), 39-42. DOI=10.5120/7880-1190
@article{ 10.5120/7880-1190,
author = { R. Santosh Kumar,C. Narasimham,S. Pallam Setty },
title = { Generalization of Boneh and Durfee’s Attack for Arbitrary Public Exponent RSA },
journal = { International Journal of Computer Applications },
year = { 2012 },
volume = { 49 },
number = { 19 },
pages = { 39-42 },
doi = { 10.5120/7880-1190 },
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 Generalization of Boneh and Durfee’s Attack for Arbitrary Public Exponent RSA%T
%J International Journal of Computer Applications
%V 49
%N 19
%P 39-42
%R 10.5120/7880-1190
%I Foundation of Computer Science (FCS), NY, USA
Abstract
In 2000, Boneh-Durfee extended the bound for low private exponent from 0. 25 (provided by wiener) to 0. 292 with public exponent size is same as modulus size. They have used powerful lattice reduction algorithm (LLL) with coppersmith's theory of polynomials. In this paper we generalize their attack to arbitrary public exponent.
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.
- 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