用e>=11 Hastad攻击破坏线性填充RSA

Question

我一直在玩弄哈斯塔德对RSA的线性填充广播攻击。使用这里的实现和测试函数：https://github.com/0n5/CTF-Crypto/blob/master/RSA/hastads.sage

测试功能和攻击在e=3,5,7中都能很好地工作，但是对于e>=11，攻击没有找到解决方案。我试着玩弄eps的值，并修改攻击以使用更多的输入(这不应该是必需的)，但攻击仍然失败。

有什么理由可以解释为什么这次攻击会以稍微大一点的e失败？

Answer 1

Coppersmith方法，正如通常用\epsilon因子描述的那样，找到了一个多项式f(x)的根，该多项式D1的次d模n的大小为x \le n^{\frac{1}{d} - \epsilon}，0 < \epsilon \le 1/7。

e = 11的H stad攻击本质上是f(x) of 11模n_0\cdot n_1 \cdot \dots n_{e-1}的Coppersmith方法的一种应用。如果是\epsilon = 1/8，那么上面的界限是无用的，看到那个\left( n_0\cdot n_1 \cdot \dots n_{e-1} \right)^{1/11 - 1/8} < 1。这也是为什么它在不修改e = 7：\left(2^{2048\cdot 7}\right)^{1/7 - 1/8} \approx 2^{256}的情况下工作。

但是，减少\epsilon确实有效:设置\epsilon = 1/13时，我们已经找到了\left(2^{2048\cdot 11}\right)^{1/11 - 1/13} \approx 2^{315}下面的所有根，这足以恢复此标志。