New Finding on Factoring Prime Power RSA Modulus $N = p^r q$

中文关键词:  RSA prime power  factorization  LLL algorithm  simultaneous diophantine approximations  continued fraction

英文关键词:RSA prime power  factorization  LLL algorithm  simultaneous diophantine approximations  continued fraction

中文摘要:

      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.