In certain variants of the RSA cryptosystem with a modulus N=pq, the public exponent e and the private exponent d are related by the equation ed≡1(modφn(N)) or ed≡1(modψn(N)), where φn(N)=(pn−1)(qn−1) and ψn(N)=(pn−1)(qn−1)(p−1)(q−1) are defined for a positive integer n≥1. In this paper, we introduce a new attack against the RSA variants when two public exponents e1 and e2 are given, satisfying eidi≡1(modφn(N)) or eidi≡1(modψn(N)) for i=1,2. Specifically, we show that when the prime factors of N share an amount of their least significant bits, and d1 and d2 share an amount of their most significant bits, the factorization of N can be computed in polynomial time. Our method is based on an extension of Coppersmith’s technique and lattice basis reduction and achieves improved bounds as the number of shared bits increases. The proposed attacks are heuristic in nature, relying on the standard assumption that the polynomials obtained after lattice reduction are algebraically independent.
Chnioune et al. (Sun,) studied this question.