Однако может ли кто-нибудь объяснить мне простыми словами, почему в этом контексте нам понадобится большой порядок G и как это поможет сделать g^ab более безопасным?
Предыстория (которую вы, вероятно, уже знаете) у Эль Гамаля зашифрованным текстом является пара $g^r, ч^r \cdot m$ (куда $ч$ является открытым ключом и $г$ случайное значение); если бы мы могли выяснить, какое значение $г$ мы могли бы восстановить $м$ (потому что мы предполагаем, что знаем значение $ч$).
Итак, одна из вещей, в которой мы должны убедиться, заключается в том, что, учитывая значение $g^r$, мы не можем сделать вывод, что $г$ является; это известно как «проблема дискретного логарифма».
Имея это в виду, вот некоторые математические расчеты за кулисами:
Мы определяем «порядок G» как наименьшее значение $к > 0$ для которого $G^k = 1$. Это интересно, потому что $G^r$ может взять на себя только $к$ разные значения, $G^1, G^2, ..., G^{k-1}, G^k = 1$. Если мы продолжим, мы закончим повторением, начиная с $G^1$, так что это нам не поможет.
Если есть только $к$ различные значения $г$ которые дают нам разные значения $G^r$, то если $к$ невелик, злоумышленник может просто попробовать все $к$ различные значения $г$ и посмотреть, работает ли один; если он может это сделать, он может восстановить правильное значение $г$ [1]. На самом деле получается, что если атакующий проявит смекалку, он может выполнить этот поиск примерно за $\sqrt{к}$ умножения; следовательно, если мы хотим убедиться, что злоумышленник должен выполнить $2^{128}$ операции по атаке системы (что является текущим стандартом для «выше чьего-либо потенциала»), то нам нужен $к$ по меньшей мере $2^{256}$.
И, оказывается, нужно сделать еще одно наблюдение: если $к$ является составным и имеет простой множитель $s$, злоумышленник может вычислить $r \bmod s$ с $\sqrt{s}$ операции (используя такую же хитрость); это снижает прочность такого $G$.
использование p = 2q+1 означает, что порядок группы G равен 2, а q и что «g иногда выбирается для порождения подгруппы порядка q группы G, а не G, так что символ Лежандра группы g^a никогда не раскрывает нижнюю заказ немного а.
Это говорит об общем методе борьбы с вышеуказанными атаками (не единственный метод, учтите).
Оказывается, если $p = 2q+1$ премьер, где $q$ также является простым, и если $р\mod 8 = 7$ (то, что Википедия забыла упомянуть), то значение $г=2$ всегда есть порядок $q$; это большое простое число. Что особенного в 2? Ну, это немного упрощает вычисление возведения в степень (поскольку умножение на 2 по модулю p довольно дешево).
И когда речь идет о символе Лежандра, раскрывающем что-то о $г^а$ну, это специальный метод поиска $а \bmod 2$; по сути, это тот же подход, о котором я упоминал выше, для восстановления $а \bмод с$ за $s=2$; работает только при заказе $г$ имеет 2 в качестве множителя. Потому что мы выбрали $г$ что имеет нечетный порядок $q$, это не работает.
[1]: Вы можете спросить: даже если $G^r$ то же самое, не может быть, чтобы $H^r$ принимать разные значения? Оказывается, нет, этого не может быть - если мы найдем какое-либо значение $г$ что дает ему наблюдаемое значение $G^r$, он может использовать это для расшифровки.
