Paper 2021/1160

Classical Attacks on a Variant of the RSA Cryptosystem

Abderrahmane Nitaj, Muhammad Rezal Kamel Ariffin, Nurul Nur Hanisah Adenan, and Nur Azman Abu

Abstract

Let N = pq be an RSA modulus with balanced prime factors. In 2018, Murru and Saettone presented a variant of the RSA cryptosystem based on a cubic Pell equation in which the public key (N, e) and the private key (N, d) satisfy ed \equiv 1 mod (p^2+p+1)(q^2+q+1)). They claimed that the classical small private attacks on RSA such as Wiener's continued fraction attack do not apply to their scheme. In this paper, we show that, on the contrary, Wiener's method as well as the small inverse problem technique of Boneh and Durfee can be applied to attack their scheme. More precisely, we show that the proposed variant of RSA can be broken if d < N^{0:5694}. This shows that their scheme is in reality more vulnerable than RSA, where the bound of vulnerability is d < N^{0.292}.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
RSAFactorizationContinued fractionsSmall inverse problemCoppersmith's method
Contact author(s)
rezal @ upm edu my
History
2021-09-14: received
Short URL
https://ia.cr/2021/1160
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1160,
      author = {Abderrahmane Nitaj and Muhammad Rezal Kamel Ariffin and Nurul Nur Hanisah Adenan and Nur Azman Abu},
      title = {Classical Attacks on a Variant of the RSA Cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1160},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1160}},
      url = {https://eprint.iacr.org/2021/1160}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.