Paper 2021/1630

Exponential Increment of RSA Attack Range via Lattice Based Cryptanalysis

Abderahmanne Nitaj, Muhammad Rezal Kamel Ariffin, Nurul Nur Hanisah Adenan, Domenica Stefania Merenda, and Ali Ahmadian

Abstract

The RSA cryptosystem comprises of two important features that are needed for encryption process known as the public parameter $e$ and the modulus $N$. In 1999, a cryptanalysis on RSA which was described by Boneh and Durfee focused on the key equation $ed-k\phi(N)=1$ and $e$ of the same magnitude to $N$. Their method was applicable for the case of $d<N^{0.292}$ via Coppersmith’s technique. In 2012, Kumar et al. presented an improved Boneh-Durfee attack using the same equation which is valid for any e with arbitrary size. In this paper, we present an exponential increment of the two former attacks using the variant equation $ea-\phi(N)b=c$. The new attack breaks the RSA system when $a$ and $|c|$ are suitably small integers. Moreover, the new attack shows that the Boneh-Durfee attack and the attack of Kumar et al. can be derived using a single attack. We also showed that our bound manage to improve the bounds of Ariffin et al. and Bunder and Tonien.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Multimedia Tools and Applications
DOI
10.1007/s11042-021-11335-8
Keywords
encryptionRSAcryptanalysisCoppersmith’s techniqueinteger factorization
Contact author(s)
abderrahmane nitaj @ unicaen fr
History
2021-12-17: received
Short URL
https://ia.cr/2021/1630
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1630,
      author = {Abderahmanne Nitaj and Muhammad Rezal Kamel Ariffin and Nurul Nur Hanisah Adenan and Domenica Stefania Merenda and Ali Ahmadian},
      title = {Exponential Increment of {RSA} Attack Range via Lattice Based Cryptanalysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1630},
      year = {2021},
      doi = {10.1007/s11042-021-11335-8},
      url = {https://eprint.iacr.org/2021/1630}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.