密码学|论文精读系列:针对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 中提到的:当 

  1. 《 Cryptanalysis of RSA with private key d less than N^0.292》 中使用了子群技术的第二个结果也可以被拓展

  2. 《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小私钥与小素数差的攻击(三)

版权声明:admin 发表于 2022年11月21日 上午10:57。
转载请注明:密码学|论文精读系列:针对RSA小私钥与小素数差的攻击(三) | CTF导航

相关文章

暂无评论

暂无评论...