General Bounds for Small Inverse Problems and Its Applications to Multi-Prime RSA
General Bounds for Small Inverse Problems and Its Applications to Multi-Prime RSA
复制标题
DOI：
10.1007/978-3-319-15943-0_1
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Atsushi Takayasu;N. Kunihiro
中科院分区：
文献类型：
--
作者：
Atsushi Takayasu;N. Kunihiro
1999年，Boneh和Durfee引入了求解二元模方程x(N+y)≡1（模态）的小逆问题。xandyy解的绝对值分别以x =NδandY=Nβ为界。他们在RSA小秘密指数攻击的背景下解决了β=1/2的问题，并提出了一个多项式时间算法，当δ<(7-2√7)/6≈0.284时有效。在同样的工作中，结合进一步提高到δ<1-1/≈2≈0.292。到目前为止，我们还分析了任意β的小逆问题。推广Boneh和Durfee晶格得到更强的界，得到界δ<1-≈β。但只有当β≥1/4时，算法才有效。当0<β<1/4时，已经有几篇文章的作者声称他们的结果是最好的。在本文中，我们重新讨论了任意β的问题。首先，我们对0<β<1/4的结果进行了总结。我们揭示了一些结果是无效的，并表明Weger算法提供了最好的界。接下来，我们提出了一种改进算法来解决0<β<1/4的问题。我们的算法在δ<1-2(≈β(3+4β)-β)/3时有效。我们的算法构建是基于Boneh和Durfee的两种形式的格的组合，与之前的工作相比，它更加自然。对于密码学应用，我们引入了对具有小素数差的多素数RSA的小秘密指数攻击。
In 1999, Boneh and Durfee introduced thesmall inverse problem, which solves the bivariate modular equationx(N+y)≡1(mode. Absolute values of solutions forxandyare bounded above byX=NδandY=Nβ, respectively. They solved the problem for β=1/2 in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when δ<(7-2√7)/6≈0.284. In the same work, the bound was further improved to δ<1-1/≈2≈0.292. Thus far, the small inverse problem has also been analyzed for an arbitrary β. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound δ<1-≈β. However, the algorithm works only when β≥1/4. When 0<β<1/4, there have been several works where the authors claimed their results are the best. In this paper, we revisit the problem for an arbitrary β. At first, we summarize the previous results for 0<β<1/4. We reveal that there are some results that are not valid and show that Weger's algorithms provide the best bounds. Next, we propose an improved algorithm to solve the problem for 0<β<1/4. Our algorithm works when δ<1-2(≈β(3+4β)-β)/3. Our algorithm construction is based on the combinations of Boneh and Durfee's two forms of lattices and it is more natural compared with previous works. For the cryptographic application, we introduce small secret exponent attacks on Multi-Prime RSA with small prime differences.