A Novel Cryptanalysis of the Cubic Pell RSA Variant

A new RSA variant based on the cubic Pell curve operates with a modulus N=pq where the encryption and the decryption exponents e and d are linked by the congruence ed≡1 (mod(p−1)2(q−1)2). At Africacrypt 2025, Rahmani and Nitaj demonstrated that this scheme is susceptible to lattice-based attacks when the secret exponent d is small. In this work, we present a refined attack on the same scheme when the prime factors p and q share a sufficient portion of their least significant bits (LSBs). Our new method extends the former results, and yields improved bounds on the decryption exponents. Leveraging a combination of Coppersmith-type techniques and lattice methods, our approach is capable of recovering the RSA prime factors in polynomial time.