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 密码系统安全性来说不是很小。
原文始发于微信公众号（山石网科安全技术研究院）：论文精读系列：针对RSA小私钥与小素数差的攻击（三）
