Cryptanalysis of RSA with Multiple Small Secret Exponents
Cryptanalysis of RSA with Multiple Small Secret Exponents
复制标题
DOI：
10.1007/978-3-319-08344-5_12
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Atsushi Takayasu;N. Kunihiro
中科院分区：
文献类型：
--
作者：
Atsushi Takayasu;N. Kunihiro
本文研究了当存在多个具有相同公模N的公/密指数（e1，d1），...，（en，dn）时RSA的安全性。我们假设所有的秘密指数都小于坦恩β。当n = 1时，Boneh和Durfee提出了一个多项式时间算法来分解公共模N。算法的工作前提是。到目前为止，已经提出了几种推广的攻击任意。然而，这些攻击并没有达到Boneh和Durfee的n = 1的界限。本文提出了一种算法，它是Boneh和Durfee算法的精确推广。我们的算法在。当alln≥ 2时，我们的界优于以往的结果.我们通过收集尽可能多的有用多项式来构造格。集合减少了格的体积，使我们能够提高边界。
In this paper, we study the security of RSA when there are multiple public/secret exponents (e1,d1), …, (en,dn) with the same public modulusN. We assume that all secret exponents are smaller thanNβ. Whenn= 1, Boneh and Durfee proposed a polynomial time algorithm to factor the public modulusN. The algorithm works provided that. So far, several generalizations of the attacks for arbitrarynhave been proposed. However, these attacks do not achieve Boneh and Durfee’s bound forn= 1. In this paper, we propose an algorithm which is the exact generalization of Boneh and Durfee’s algorithm. Our algorithm works when. Our bound is better than all previous results for alln≥ 2. We construct the lattices by collecting as many helpful polynomials as possible. The collections reduce the volume of the lattices and enable us to improve the bound.