CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Generalization of Boneh and Durfee’s Attack for Arbitrary Public Exponent RSA

by R. Santosh Kumar, C. Narasimham, S. Pallam Setty
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 49 - Number 19
Year of Publication: 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 },
issue_date = { July 2012 },
volume = { 49 },
number = { 19 },
month = { July },
year = { 2012 },
issn = { 0975-8887 },
pages = { 39-42 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume49/number19/7880-1190/ },
doi = { 10.5120/7880-1190 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:46:40.058613+05:30
%A R. Santosh Kumar
%A C. Narasimham
%A S. Pallam Setty
%T Generalization of Boneh and Durfee’s Attack for Arbitrary Public Exponent RSA
%J International Journal of Computer Applications
%@ 0975-8887
%V 49
%N 19
%P 39-42
%D 2012
%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
  1. Cohen, H. 1995. A Course in Computational Algebraic Number Theory. Springer-Verlag. Second edition.
  2. Menezes, A. J, Van Oorschot P. C, and Vanstone. 1997. Hand book of Applied Cryptography. CRC Press.
  3. Lenstra A. K, Lenstra Jr. H. W, Lovasz L. 1982. "Factoring polynomials with rational coefficients". Mathematische A1nnalen, volume 261(4): pages 515-534.
  4. 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.
  5. Coppersmith D. 1997. "Small solution to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology", 10(4):233-260.
  6. 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.
  7. Wiener M. J. 1990. Cryptanalysis of short RSA secret exponents. IEEE Trans. In formation Theory, 36(3):553:559.
  8. 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.
  9. 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.
  10. 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.
  11. P. Schnorr and M. Euchner. 1994. Lattice basis reduction: Improved practical algorithms and solving subset sum problems Math. Prog. 66: 181- 199.
  12. Santosh kumar R, Narasimham C, Pallam setty S. 2012 Lattice based tools for cryptanalysis in various applications. Springer-LNICST, 84:530-537.
  13. Boneh. ,D. 1999. Twenty Years of Attacks on the RSA Cryptosystem. Notices the AMS 46(2), 203-213.
  14. 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.
  15. 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.
  16. 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.
  17. Aono,Y. 2009. Simplification of the lattice based attack of Boneh and Durfee for RSA cryptoanalysis. Proceedings of joint conference of ASCM and MACS.
  18. Victor Shoup. NTL: A library for doing Number Theory, online available at http://shoup. net/ntl.
Index Terms

Computer Science
Information Sciences

Keywords

Lattices LLL RSA Cryptanalysis Boneh-Durfee

Powered by PhDFocusTM