Paper 2014/035

A new attack on RSA with a composed decryption exponent

Abderrahmane Nitaj and Mohamed Ould Douh

Abstract

In this paper, we consider an RSA modulus $N=pq$, where the prime factors $p$, $q$ are of the same size. We present an attack on RSA when the decryption exponent $d$ is in the form $d=Md_1+d_0$ where $M$ is a given positive integer and $d_1$ and $d_0$ are two suitably small unknown integers. In 1999, Boneh and Durfee presented an attack on RSA when $d<N^{0.292}$. When $d=Md_1+d_0$, our attack enables one to overcome Boneh and Durfee's bound and to factor the RSA modulus.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. International Journal on Cryptography and Information Security (IJCIS), Vol.3, No. 4, December 2013
Keywords
RSACryptanalysisFactorizationLLL algorithmCoppersmith's method
Contact author(s)
abderrahmane nitaj @ unicaen fr
History
2014-01-12: received
Short URL
https://ia.cr/2014/035
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/035,
      author = {Abderrahmane Nitaj and Mohamed Ould Douh},
      title = {A new attack on RSA with a composed decryption exponent},
      howpublished = {Cryptology ePrint Archive, Paper 2014/035},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/035}},
      url = {https://eprint.iacr.org/2014/035}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.