Cryptanalysis of a cubic Pell variant of RSA with primes sharing least significant bits
Nurul Nur Hanisah Adenan, Abderrahmane Nitaj, Muhammad Rezal Kamel Ariffin, Nur Azman Abu · Journal of Information and Optimization Sciences · 2024
In this paper, we push further the cryptanalysis of a cryptosystem of the RSA’s variant which utilized a cubic Pell equation with the key equation ed − k(p2 + p + 1)(q2 + q + 1) = 1 where N = pq is an RSA modulus, e, N are publicized, while d, p, q are kept private. We consider the case where the prime factors share an amount of their least significant bits (LSBs), that is p and q satisfy p – q = 2m u where m is known, and u is unknown. Through this work, we show that via Coppermith’s method and lattice basis reduction, it is feasible to retrieve the secret key d and factor N for larger values of d.