New Finding on Factoring Prime Power RSA Modulus N =pΥq

摘要

This paper proposes three new attacks.In the first attack we consider the class of the public exponents satisfying an equation eX-NY + (apΥ + bqΥ)Y =Z for suitably small positive integers a,b.Applying continued fractions we show that Y/X can be recovered among the convergents of the continued fraction expansion of e/N.Moreover,we show that the number of such exponents is at least N2/(r+1)-ε where ε ≥ 0 is arbitrarily small for large N.The second and third attacks works upon k RSA public keys (Ni,ei) when there exist k relations of the form eix-Niyi + (apΥi + bqΥi)yi =zi or of the form eixi-Niy + (apΥi + bqΥi)y =zi and the parameters x,xi,y,yi,zi are suitably small in terms of the prime factors of the moduli.We apply the LLL algorithm,and show that our strategy enables us to simultaneously factor k prime power RSA moduli.