New Finding on Factoring Prime Power RSA Modulus $N = p^r q$
Received:July 18, 2016  Revised:September 07, 2016
Key Word: RSA prime power   factorization   LLL algorithm   simultaneous diophantine approximations   continued fraction
Fund ProjectL:
 Author Name Affiliation Sadiq SHEHU Al-Kindi Cryptography Research Laboratory, Institute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia Muhammad Rezal Kamel ARIFFIN Department of Mathematics, Faculty of Science, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia
Hits: 1120
This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation $e X - N Y + (a p^r + b q^r)Y = Z$ for suitably small positive integers $a,b$. Applying continued fractions we show that $\frac{Y}{X}$ can be recovered among the convergents of the continued fraction expansion of $\frac{e}{N}$. Moreover, we show that the number of such exponents is at least $N^{\frac{2}{(r+1)}-\varepsilon}$ where $\varepsilon \geq 0$ is arbitrarily small for large $N$. The second and third attacks works upon $k$ RSA public keys $(N_i,e_i)$ when there exist $k$ relations of the form $e_i x - N_i y_i + (a p_i^r + b q_i^r) y_i = z_i$ or of the form $e_i x_i - N_i y + (a p_i^r + b q_i^r) y = z_i$ and the parameters $x$, $x_i$, $y$, $y_i$, $z_i$ 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.