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

rozi

14.01.2023, 18:13

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?

596

0 + 0

атака

Рейтинг:5

Crypto

Samuel Neves

14.01.2023, 23:27

Метод Копперсмита, как обычно указывается в $\эпсилон$ фактор, находит корень многочлена $ф(х)$ степени $д$ по модулю $n$ размера $x \le n^{\frac{1}{d} - \epsilon}$, $0 < \epsilon \le 1/7$.

Атака HÃ¥stad с $е = 11$ в основном представляет собой применение метода Копперсмита с $ф(х)$ степени $11$ по модулю $n_0\cdot n_1 \cdot \dots n_{e-1}$. Если $\эпсилон = 1/8$, то приведенная выше оценка бесполезна, так как $\left( n_0\cdot n_1 \cdot \dots n_{e-1} \right)^{1/11 - 1/8} < 1$. Вот почему он работал без изменений до $е = 7$: $\влево(2^{2048\cdot 7}\вправо)^{1/7 - 1/8} \приблизительно 2^{256}$.

Тем не менее, уменьшение $\эпсилон$ делает работа: настройка $\эпсилон = 1/13$ мы уже найдем все корни ниже $\влево(2^{2048\cdot 11}\вправо)^{1/11 - 1/13} \приблизительно 2^{315}$, что достаточно для восстановления этого флага.

0 + 0

Admin

Этот вопрос на других языках:

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

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

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

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

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

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.