A new attack on RSA with a composed decryption exponent

Abderrahmane Nitaj; Mohamed Ould Douh

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 = p q$ , 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 = M d_{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 = M d_{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: RSA Cryptanalysis Factorization LLL algorithm Coppersmith'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}
}