New Attacks on RSA with Moduli N = prq

We present three attacks on the Prime Power RSA with modulus N = p(r) q. In the first attack, we consider a public exponent e satisfying an equation ex - phi(N)y = z where phi(N) = p(r-1) (p - 1)(q - 1). We show that one can factor N if the parameters vertical bar x vertical bar and vertical bar z vertical bar satisfy vertical bar xz vertical bar < Nr(r-1)/(r+1)2 thereby extending the recent results of Sakar [16]. 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 vertical bar d(1) - d(2)vertical bar < Nr(r-1)/(r+1) 2. The third attack enables us to factor two Prime Power RSA moduli N-1 = p(1)(r)q(1) and N-2 = p(2)(r)q(2) when p(1) and p(2) share a suitable amount of their most significant bits, namely, vertical bar p(1) - p(2)vertical bar < p(1)/2rq(1)q(2).