New Attacks on RSA with Moduli N = p~rq

摘要

We present three attacks on the Prime Power RSA with modulus N = p~rq. In the first attack, we consider a public exponent e satisfying an equation ex - Φ(N)y = z where Φ(N) = p~(r-1)(p - l)(q - 1). We show that one can factor N if the parameters |x| and z satisfy xz ＜ N(r+1)~2/r(r-1) thereby extending the recent results of Sakar. In the second attack, we consider two public exponents e_1 and e_2 and their corresponding private exponents d_1 and d_2 We show that one can factor N when d_1 and d_2 share a suitable amount of their most significant bits, that is d_1 - d_2 ＜ N(r+1)~2/r(r-1). The third attack enables us to factor two Prime Power RSA moduli N_1 - p_1~rq_1 and N_2 = P_2~rq_2 when p_1 and P_2 share a suitable amount of their most significant bits, namely, |p_1 - P_2| ＜ 2rq_1q_2/p_1.