breaking RSA with linear padding using Hastads attack with e>=11

Question

I have been playing around with Hastad's broadcast attack on RSA with linear padding. Using the implementation and the test function from here: https://github.com/0n5/CTF-Crypto/blob/master/RSA/hastads.sage

The test function and the attack work perfectly well with e=3,5,7. However, with e>=11 the attack does not find a solution. I tried playing around with the values of eps and modifying the attack to use more inputs (which shouldn't be needed), but the attack still fails.

Is there any reason for why the attack fails with a slightly larger e?

Answer 1

The Coppersmith method, as usually stated with the $\epsilon$ factor, finds a root of a polynomial $f(x)$ of degree $d$ modulo $n$ of size $x \le n^{\frac{1}{d} - \epsilon}$, $0 < \epsilon \le 1/7$.

The Håstad attack with $e = 11$ is fundamentally an application of the Coppersmith method with $f(x)$ of degree $11$ modulo $n_0\cdot n_1 \cdot \dots n_{e-1}$. If $\epsilon = 1/8$, then the above bound is useless, seeing that $\left( n_0\cdot n_1 \cdot \dots n_{e-1} \right)^{1/11 - 1/8} < 1$. This is also why it worked without modification up to $e = 7$: $\left(2^{2048\cdot 7}\right)^{1/7 - 1/8} \approx 2^{256}$.

However, decreasing $\epsilon$ does work: setting $\epsilon = 1/13$ we will already find all roots below $\left(2^{2048\cdot 11}\right)^{1/11 - 1/13} \approx 2^{315}$, which is enough to recover this flag.