Группы Диффи Хеллмана
Я видел, что неотрицательные целые числа с операцией сложения не могут быть группой Диффи Хеллмана. Мне сложно понять, почему это не может быть группа DHKE. Чтобы быть группой DHKE, необходимо владеть пятью объектами собственности:
- Оператор закрыт
- ассоциативность
- элемент идентичности существует
- обратный элемент существует
- коммутативность
Я пробовал с группой {0,1,2,3,4,5,6} и p = 7, и все вышеуказанные свойства были сохранены. Мне не удалось найти подходящий пример, чтобы показать, что вышеуказанные свойства не выполняются. Какие еще примеры могут показать, что неотрицательные целые числа с оператором сложения не входят в одну из ключевых групп Диффи-Хеллмана?
Ответы
Чтобы быть группой DHKE, необходимо владеть пятью объектами собственности:
Это правда; однако, чтобы быть безопасной группой DHKE, должно быть дополнительное свойство:
- «Проблема дискретного журнала» должна быть сложной; то есть, учитывая общественную ценность$xG$ (где $G$ идентификатор публичной группы, $x$ ваша личная ценность, и $xG$ действует ли генератор на себя $x$ раз) трудно восстановить $x$.
В случае сложения имеем $xG = \underbrace{G + G + … + G}_{x \text{ times}} = x \times G$., где $\times$ это целочисленное умножение.
Если мы знаем $x \times G$ и мы знаем $G$, то легко восстановить $x$ путем простого деления (модульное деление, если мы делаем сложение по модулю $p$, что не намного сложнее), и, следовательно, метод Диффи-Хеллмана был бы тривиально небезопасным.
Фактически, одной проблемы с безопасным дискретным журналом недостаточно; проблема "Диффи-Хеллмана" также должна быть сложной, то есть с учетом$G$, $xG$ и $yG$, должно быть трудно восстановить $xyG$ (это известно как вычислительная проблема Диффи-Хеллмана) или заданная $G$, $xG$, $yG$, $zG$, должно быть трудно определить, $xy = z$(это известно как решающая проблема Диффи Хеллмана). Любая из этих проблем может быть проще, чем «проблема дискретного журнала» для любой группы; однако, к тому же, ни одна из этих проблем не является сложной.