### Exponential Increment of RSA Attack Range via Lattice Based Cryptanalysis

##### 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.

Available format(s)
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
Short URL
https://ia.cr/2021/1630

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},
note = {\url{https://eprint.iacr.org/2021/1630}},
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.