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
-
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}, url = {https://eprint.iacr.org/2014/035} }