New Attacks on RSA with Modulus N = p2q Using Continued Fractions

In this paper, we propose two new attacks on RSA with modulus N = p(2)q using continued fractions. Our first attack is based on the RSA key equation ed - phi(N)k = 1 where phi(N) = p(p - 1)(q - 1). Assuming that q < p < 2q, 2p(5/3)vertical bar p(1/3) - q(1/3)vertical bar < 1/3N(beta) < and d < N1-beta/2, we show that k/d can be recovered among the convorgents of the continued fraction expansion of e/N-(2N2(/3)-N-1/3). Our second attack is based on the equation eX - (N - (ap(2) bq(2))) Y = Z whore a,b are positive integers satisfying gcd(a,b) = 1, vertical bar ap(2) - bq(2)vertical bar < N-1/2 and ap(2) bq(2) N2/3+alpha with 0 < alpha < 1/3. Given the conditions vertical bar Z vertical bar < 1/3N(1/3+alpha)Y and 1 <= Y <= X < 1/2 N1/6-alpha/2, we show that one can factor N - p(2)q in polynomial time