Paper 2026/2915

A New Cryptanalytic Attack on an RSA Variant Arising from Cubic Pell Curves

Brahim Chnioune, Mohammed I University
Mohammed Rahmani, Mohammed I University
Abderrahmane Nitaj, Université de Caen Normandie
Mhammed Ziane, Mohammed I university
Abstract

In 2024, Nitaj and Seck introduced an RSA-like cryptosystem defined by a public key $(N,e)$ and a corresponding private key $(N,d)$ satisfying $ ed-1 \equiv 0 \pmod{p^{2(a-1)} q^{2(b-1)} (p-1)^2 (q-1)^2}, $ where $N=p^aq^b.$ More recently, Seck and Tchapgnouo (DAM 2026) proposed a partial key exposure attack against the same scheme for the case where $N = pq$, assuming partial knowledge of one prime factor. Using a lattice-based method, they showed that, under some constraints, the private parameters $(d,p,q)$ can be recovered in polynomial time. In this paper, we further investigate the security of this construction by considering a dual-key scenario. Specifically, in the presence of two encryption exponents $e_1$ and $e_2$, with corresponding private exponents $d_1$ and $d_2$ satisfying $ e_i d_i - 1 \equiv 0 \pmod{(p-1)^2(q-1)^2}, $ for $i \in \{1,2\}$, we prove that if the prime factors of $N$ share a certain number of least significant bits, and if $d_1$ and $d_2$ share an amount of their most significant bits, then the private parameters $(d_1,d_2,p,q)$ can be computed in polynomial time. Our method combines an extension of Coppersmith's small-root technique with lattice basis reduction, leading to improved bounds compared to existing single-key attacks.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. Minor revision. DAM 2026
Keywords
RSACubic Pell equationInteger factorizationCoppersmith's methodLLL reduction algorithm
Contact author(s)
brahim chnioune d24 @ ump ac ma
mohammed rahmani @ ump ac ma
abderrahmane nitaj @ unicaen fr
m ziane @ ump ac ma
History
2026-11-21: approved
2026-11-16: received
See all versions
Short URL
https://ia.cr/2026/2915
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2915,
      author = {Brahim Chnioune and Mohammed Rahmani and Abderrahmane Nitaj and Mhammed Ziane},
      title = {A New Cryptanalytic Attack on an {RSA} Variant Arising from Cubic Pell Curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2915},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2915}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.