New Finding on Factoring Prime Power RSA Modulus $N = p^r q$
Received:July 18, 2016  Revised:September 07, 2016
Key Words: RSA prime power   factorization   LLL algorithm   simultaneous diophantine approximations   continued fraction  
Fund Project:
Author NameAffiliation
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: 2213
Download times: 1870
      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.
View Full Text  View/Add Comment  Download reader