Регистрация Войти
Рейтинг:0
avatar Crypto

Безопасность схемы подписи Эль-Гамаля с генератором малого порядка

флаг cn
amycandyit

За $р$ 1024-битное простое число, у нас есть 1021-битный элемент $g \in \mathbb{Z}_p^*$, где порядок $г$ намного меньше порядка $\mathbb{Z}_p^*$. Как этот небольшой заказ $г$ влияет на безопасность подписи?

51
0 + 0
Рейтинг:1
Ievgeni avatar Crypto
флаг cn
Ievgeni

Размер $р$ влияет только на стоимость групповых операций (которая мала даже для 1024-битного числа). Многие известные атаки на Dlog, такие как baby-step-giant-step, находятся в стадии разработки. $\mathcal{O}(\sqrt{o(g)})$ групповые операции с $ о (г) $, получатель чего-то $г$. Вот почему важно, чтобы $г$ имеет такой же порядок $\mathbb{Z}^{*}_p$ (тогда это должен быть генератор). Иначе, если $ о (г) $ мал, вы легко сломаете Dlog, а значит и ElGamal.

0 + 0
fgrieu avatar
флаг ng
fgrieu
Дополнение: Необязательно, чтобы $g$ имел тот же порядок, что и $\mathbb Z_p^*$, \[что $g$ является генератором\], или даже половину того, \[что принято для простого порядка\]; и это не практикуется в исходной подписи Шнорра или в более позднем DSA. Достаточно, чтобы порядок $g$ содержал как минимум в два раза больше битов, чем целевой уровень безопасности \[эта граница следует из ответа $\mathcal{O}(\sqrt{\operatorname{ord}(g)}\, )$ \] и является простым. Таким образом, 256-битного простого порядка $g$ вполне достаточно для 1024-битного $p$ \[что довольно низко, 2048-битный был бы современным базовым уровнем\].
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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