Partial Exposure Attacks on a New RSA Variant

In 2022, Cotan and Teşeleanu presented a variant of the RSA cryptosystem where the modulus is of the form N=pq, and the private and the public exponents satisfy ed≡1(modψn(N)) with n≥2, and ψn(N)=pn−1qn−1(p−1)(q−1). This variant of RSA was recently cryptanalyzed by Nitaj, Adenan, and Ariffin at Africacrypt 2024. In this paper, we push further the cryptanalysis of the scheme of Cotan and Teşeleanu by presenting a method to solve the equation xH(y)+c≡0(mode) where c is a constant that is independent of x and y. This enables us to propose more attacks on the scheme, including a partial key exposure attack, an attack when the most significant bits of one of the prime factors are known, and an attack when the least significant bits of one of the prime factors are known.