Paper 2026/2915
A New Cryptanalytic Attack on an RSA Variant Arising from Cubic Pell Curves
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
-
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}
}