Partial Prime Exposure Attack on the Cubic Pell RSA Cryptosystem.

Abstract

A recent contribution by Rahmani and Nitaj (AfricaCrypt 2025) investigates the cryptanalysis of an RSA-inspired scheme derived from the cubic Pell curve $t_1^3 + f t_2^3 + f^2 t_3^3 - 3 f t_1 t_2 t_3 \equiv 1 \pmod{\mathtt{N}}$, where $\mathtt{N} = \mathtt{p}\mathtt{q}$ is a standard RSA modulus and the public–private exponent pair satisfies $ed-1 \equiv 0 \pmod{(\mathtt{p}-1)^2 (\mathtt{q}-1)^2}$. In this paper, we revisit their attack showing that when an approximation of one prime factor is known, the scheme becomes significantly more vulnerable. Using a variant of Coppersmith's method, one can factor $\mathtt{N}$ in polynomial time under explicit bounds, which improve previous results.