论文精读系列：针对RSA小私钥与小素数差的攻击（三）

是这篇论文的最后一部分内容了，之所以 3.2 一小节和第 4 节放在一起，是因为这两部分的内容在论文中只是理论层面地带过了一下，另外笔者也是能力有限，所以暂时还不能够进行 coding 与复现。因此只是简单地将论文翻译后贴了出来，希望能够给到读者一些启发。

3.2 根据分解

这一节，我们仍然设定较小，设为的比特数，并定义。

定理 3 设，其中是较小的正整数。继续沿用 引理 2 的定义，，假设较小，并且存在正整数使得满足，那么当并且，那么可以在多项式时间（）内被分解。

证明：首先，我们考虑的界。

因为，所以

令，因为，并且

所以

根据引理 2，并结合上述不等关系有我们得到

因为，并且，所以我们与

如果，那么就有。

因此，会出现在的连分数展开上。然后由，我们可以计算出的一个大约值。而误差项。因为较小，所以，其中是某个常数。通过枚举几个比特，我们可以恢复大部分的的高位值，随后利用 Coppersmith 方法即可在多项式时间内分解。

笔者注：关于连分数中的应用基础是 Legendre’s theorem，这里进行一个简单的证明：详细可以去看一看知乎这篇文章：Wiener's Attack Ride(维纳攻击法驾驭)
若且，设，则，规定，可证
证明：选择一个n，满足，
由三角不等式可得：
又因为，所以，并且，所以
又因为，于是，
并且
所以有

4. Weger 对 Boneh Durfee 攻击的拓展

针对 RSA 小私钥的 Boneh Durfee attack，在素数差较小的时候，Weger将的界提升到了。这一章，我们将证明这对小的也同样成立。

假设公钥指数和比特数相同，设，记，且。于是我们有。注意到我们假设，从而。再设。根据第三节的计算，我们有

我们的目标是找到二元多项式的解，其中，并且

在 Boneh 和 Durfee 的《 Cryptanalysis of RSA with private key d less than N^0.292》中提到，其中是固定后需要进以步优化的参数。并且其他与无关的数都整合到误差项中了。

我们注意到我们攻击的渐进边界为，

等效形式为

取，则条件变为

根据《 Cryptanalysis of RSA with private key d less than N^0.292》，如果 LLL 算法求出的规约基的前两个元素是线性独立的，则我们可以解出，此时

就是，那么就可以分解了。

注意到这里的上界大于我们定理 2 中提到的：当，。

注
《 Cryptanalysis of RSA with private key d less than N^0.292》中使用了子群技术的第二个结果也可以被拓展
《Revisiting Wiener’s attack–new weak keys in RSA》中的 2.1和3中提到，需要很小，但是我们注意到这样并不能保证条件成立。在我们早些的示例中，是 164比特的数，比起其并不能被忽略。事实上，设，则根据的定义我们有。

5. 总结

这篇论文中，我们讨论了 RSA 中与参数相关的安全问题，我们指出，当时可以被高效的分解。并且我们还考虑了一般情况以获得其他结果。此外，我们研究了基于 Coppersmith 方法的 Boneh 和 Durfee 攻击，并修正了 Cryptanalysis of RSA with private key d less than N^0.292》中的界。因此，我们建议，在选择 RSA 密码系统的素因子时，必须保证对于 RSA 密码系统安全性来说不是很小。