Improved Results on Cryptanalysis of Prime Power RSA

详细信息    查看全文

• 关键词：Cryptanalysis ; Prime Power RSA ; Multiple private exponents ; Implicit factorization problem ; Coppersmith’s method
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10157
• 期：1
• 页码：287-303
• 丛书名：Information Security and Cryptology ?ICISC 2016
• ISBN：978-3-319-53177-9
• 卷排序：10157

文摘

Recently, Zheng and Hu (SCIENCE CHINA Information Sciences 58(11):1–8, 2015) proposed a cryptanalysis of Prime Power RSA with two private exponents, namely, for a Prime Power RSA modulus \(N=p^rq (r>1)\), there are two pairs of public and private exponents. According to their work, when the two private exponents are small enough, this variant of RSA is insecure and one can factor \(N=p^rq\) efficiently. Moreover, in C2SI 2015, Nitaj and Rachidi considered the implicit factorization problem. They showed that for two Prime Power RSA moduli \(N_1=p_1^rq_1\) and \(N_2=p_2^rq_2\), when \(p_1\) and \(p_2\) share a suitable amount of most significant bits, one can factor \(N_1\) and \(N_2\) in polynomial time. In this paper, we revisit these two works. More specifically, for Zheng-Hu’s work, by solving two modular univariate linear equations and modifying the Zheng-Hu’s selection of polynomials to construct lattice, we can further improve their result. For Nitaj-Rachidi’s work, based on an observation that a desired solution of a modular equation is a factor of Prime Power RSA modulus, we can also improve Nitaj-Rachidi’s bound. Our improved attacks are verified by experiments.