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$
投稿时间:2016-07-18  修订日期:2016-09-07
DOI:10.3770/j.issn:2095-2651.2017.04.003
中文关键词:  RSA prime power  factorization  LLL algorithm  simultaneous diophantine approximations  continued fraction
英文关键词:RSA prime power  factorization  LLL algorithm  simultaneous diophantine approximations  continued fraction
基金项目:
作者单位
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 
摘要点击次数: 2345
全文下载次数: 1962
中文摘要:
      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.
查看全文  查看/发表评论  下载PDF阅读器