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

Phương pháp Coppersmith, như thường được nêu với $\epsilon$ thừa số, tìm nghiệm của đa thức $f(x)$ bằng cấp $d$ modulo $n$ kích thước $x \le n^{\frac{1}{d} - \epsilon}$, $0 < \epsilon \le 1/7$.

HÃ¥stad tấn công với $e = 11$ về cơ bản là một ứng dụng của phương pháp Coppersmith với $f(x)$ bằng cấp $11$ modulo $n_0\cdot n_1 \cdot \dots n_{e-1}$. Nếu $\epsilon = 1/8$, thì giới hạn trên là vô ích, thấy rằng $\left( n_0\cdot n_1 \cdot \dots n_{e-1} \right)^{11/1 - 1/8} < 1$. Đây cũng là lý do tại sao nó hoạt động mà không cần sửa đổi cho đến $e = 7$: $\left(2^{2048\cdot 7}\right)^{1/7 - 1/8} \approx 2^{256}$.

Tuy nhiên, giảm $\epsilon$ làm công việc: thiết lập $\epsilon = 1/13$ chúng tôi sẽ tìm thấy tất cả các gốc bên dưới $\left(2^{2048\cdot 11}\right)^{11/1 - 1/13} \approx 2^{315}$, đủ để khôi phục cờ này.