Sadiq SHEHU,Muhammad Rezal Kamel ARIFFIN.New Finding on Factoring Prime Power RSA Modulus $N = p^r q$[J].数学研究及应用,2017,37(4):404~418
New Finding on Factoring Prime Power RSA Modulus $N = p^r q$
New Finding on Factoring Prime Power RSA Modulus $N = p^r q$

DOI：10.3770/j.issn:2095-2651.2017.04.003

 作者 单位 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

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.

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.