A Unified Framework for Small Secret Exponent Attack on RSA
A Unified Framework for Small Secret Exponent Attack on RSA
复制标题
DOI：
10.1007/978-3-642-28496-0_16
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
N. Kunihiro;N. Shinohara;T. Izu
中科院分区：
文献类型：
--
作者：
N. Kunihiro;N. Shinohara;T. Izu
本文提出了一种基于格的RSA小秘密指数攻击方法。Boneh和Durfee将攻击归结为求二元模方程x（N+1+y）+1 0（模）的小根，其中N是RSA模，d是RSA公钥，并提出了一种基于格的算法来解决这个问题。当秘密指数小于N0.292时，他们的方法破坏了RSA方案。由于分析中使用的格不是满秩的，所以分析并不容易。Blömer和May提出了一个使用满秩格的替代算法，尽管它给出的界（d≤N0.290）比Boneh-Durfee更差。然而，他们的界限的证明仍然是复杂的。Herrmann和May给出了Boneh-Durfee界的初等证明：d≤N0.292。本文首先给出Blömer-May界d≤ N 0.290的初等证明。我们的证明采用解开线性化技术介绍了赫尔曼和梅，而不是简单的Blömer-May的证明。然后，我们提供了一个统一的框架-其中包括两个以前的方法，赫尔曼-梅和Blömer-May的方法，作为一个特殊的情况-构造一个格，可以用来解决这个问题。此外，我们还证明了Boneh-Durfee界：d≤ N0.292在我们的统一框架下仍然是最优的.
In this paper, we present a lattice based method on small secret exponent attack on the RSA scheme. Boneh and Durfee reduced the attack to finding the small roots of the bivariate modular equation:x(N+1+y)+1 ≡ 0 (mode), whereNis an RSA modulus andeis the RSA public key and proposed a lattice based algorithm for solving the problem. When the secret exponentdis less thanN0.292, their method breaks the RSA scheme. Since the lattice used in the analysis is not full-rank, the analysis is not easy. Blömer and May proposed an alternative algorithm that uses a full-rank lattice, even though it gives a bound (d≤N0.290) that is worse than Boneh-Durfee. However, the proof for their bound is still complicated. Herrmann and May, however, have given an elementary proof for the Boneh-Durfee's bound:d≤N0.292. In this paper, we first give an elementary proof for achieving Blömer-May's bound:d≤N0.290. Our proof employs the unravelled linearization technique introduced by Herrmann and May and is rather simpler than that of Blömer-May's proof. We then provide a unified framework — which subsumes the two previous methods, the Herrmann-May and the Blömer-May methods, as a special case — for constructing a lattice that can be are used to solve the problem. In addition, we prove that Boneh-Durfee's bound:d≤N0.292is still optimal in our unified framework.