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

[摘要] In this paper, we propose two new attacks on RSA with modulus N = p2q using continued fractions. Our first attack is based on the RSA key equation ed - φ(N)k = 1 where φ(N) = p(p - 1)(q - 1). Assuming that and , we show that can be recovered among the convergents of the continued fraction expansion of . Our second attack is based on the equation eX - (N - (ap2+ bq2)) Y = Z where a,b are positive integers satisfying gcd(a,b) = 1, |ap2- bq2| 1/2and ap2+ bq2= N2/3+αwith 0 2q in polynomial time.

[发布机构] Al-Kindi Cryptography Research Laboratory, Institute for Mathematical Research, Universiti Putra Malaysia, Serdang; 43400, Malaysia^1;Department of Mathematics, Faculty of Sciences, Universiti Putra Malaysia, Serdang; 43400, Malaysia^2

[效力级别] 化学

[关键词] Continued fraction;Continued fraction expansion;Key equation;Polynomial-time;Positive integers