Improved Cryptanalysis of Some RSA Variants

Several RSA variants enforce a constraint between their public and private keys through the relation ed≡1(mod(p2−1)(q2−1)), where p and q are the prime factors of their RSA modulus N=pq. In this paper, we introduce a novel attack on RSA variant schemes where the public exponent satisfies an equation of the form eu≡z(mod(p2−1)(q2−1)), with sufficiently small |z|, |u|, in a scenario where the attacker has access to an approximation of one of the prime factors. Our new attack utilizes Coppersmith’s method, combined with lattice basis reduction techniques, to efficiently recover the prime factors of the RSA modulus in these scenarios. This method offers a significant improvement over prior attacks on RSA variants with small private exponents or partial prime information.