To improve the security and the efficiency of the RSA cryptosystem, several variants have been proposed such as CRT-RSA, KMOV, Multiprime-RSA, Takagi-RSA, and Multiprime-power-RSA. Some variants use an RSA modulus \(N=pq\) with a public exponent e and a private exponent d satisfying \(ed\equiv 1\pmod {\left( p^2-1\right) \left( q^2-1\right) }\) or \(ed\equiv 1\pmod {\left( p^2+p+1\right) \left( q^2+q+1\right) }\) . In these variants, e is in the form \(e\equiv \frac{1}{d}\pmod {\left( p^2-1\right) \left( q^2-1\right) }\) or \(e\equiv \frac{1}{d}\pmod {\left( p^2+p+1\right) \left( q^2+q+1\right) }\) with a small d. In this paper, we present a new attack on the former variants whenever the public exponent e has the form \(e\equiv \frac{z}{u}\pmod {\left( p^2-1\right) \left( q^2-1\right) }\) or the form \(e\equiv \frac{z}{u}\pmod {\left( p^2+p+1\right) \left( q^2+q+1\right) }\) with small |z| and u. As a consequence, our class of weak exponents is much larger than the class in the former attacks. Our new method is based on Coppersmith’s method and lattice basis reduction, and breaks the variants in polynomial time when u and |z| are suitably small. Moreover, our method retrieves all the results of the former known attacks on such variants.
