Coppersmith's lattices and “focus groups”: An attack on small-exponent RSA
Coppersmith's lattices and “focus groups”: An attack on small-exponent RSA
复制标题
Coppersmith 的格子和“焦点小组”：对小指数 RSA 的攻击
DOI：
10.1016/j.jnt.2021.01.002
复制
发表时间：
2021
影响因子：
0.7
通讯作者：
Venkatesan, Ramarathnam
中科院分区：
文献类型：
--
作者：
Miller, Stephen D.;Narayanan, Bhargav;Venkatesan, Ramarathnam
我们提出了一个原则性的技术，减少格和矩阵的大小在某些应用中的Coppermith的格方法寻找模块多项式方程的根。它依赖于从Coppermith攻击的实际行为中推断出较小参数大小的模式，这可以被认为是“焦点小组”测试。当应用于小指数RSA问题时，我们的技术减少了格维数，从而减少了运行时间，因此可以应用于更广泛的指数。此外，在许多困难的例子中，我们的攻击不仅更快，而且更成功地恢复RSA密钥。我们包括一个讨论的微妙之处，是否现有的指标（如启用条件的界限）是决定性的，在预测的基础上，Coppermith的方法的攻击的真实效果。最后，给出的迹象表明，某些格基约简算法（如Nguyen-Stehlé的L2）可能特别适合于Coppermith的方法。
We present a principled technique for reducing the lattice and matrix size in some applications of Coppersmith's lattice method for finding roots of modular polynomial equations. It relies on extrapolating patterns from the actual behavior of Coppersmith's attack for smaller parameter sizes, which can be thought of as “focus group” testing. When applied to the small-exponent RSA problem, our technique reduces lattice dimensions and consequently running times, and hence can be applied to a wider range of exponents. Moreover, in many difficult examples our attack is not only faster but also more successful in recovering the RSA secret key. We include a discussion of subtleties concerning whether or not existing metrics (such as enabling condition bounds) are decisive in predicting the true efficacy of attacks based on Coppersmith's method. Finally, indications are given which suggest certain lattice basis reduction algorithms (such as Nguyen-Stehlé's L2) may be particularly well-suited for Coppersmith's method.