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 Name  Affiliation  Sadiq SHEHU  AlKindi 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 
Abstract: 
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. 
Citation: 
DOI:10.3770/j.issn:20952651.2017.04.003 
View Full Text View/Add Comment Download reader 


