New Attacks on RSA with ModulusN=p2qUsing Continued Fractions
Muhammad Asyraf Asbullah, Muhammad Rezal Kamel Ariffin · Journal of Physics Conference Series · 2015
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 – ϕ ( 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 – ( ap 2 + bq 2 )) Y = Z where a,b are positive integers satisfying gcd( a,b ) = 1, | ap 2 – bq 2 | < N 1/2 and ap 2 + bq 2 = N 2/3+α with 0 < α < 1/3. Given the conditions , we show that one can factor N = p 2 q in polynomial time.