Требование к генератору G быть примитивным корнем по модулю p в алгоритме Диффи-Хеллмана

Question

Обыскав, меня смутило использование P и G в алгоритме Диффи-Хеллмана.Существует требование, что P является простым, а G является примитивным корнем P.

Я понимаю, что безопасность основана на сложности факторизации результата двух очень больших простых чисел, поэтому у меня нет проблем с этим,Однако, по-видимому, имеется мало доступной информации о том, что G является примитивным корнем P. Может ли кто-нибудь ответить, почему существует это требование (со ссылками, если это возможно)?Это только увеличивает безопасность?Учитывая, что общие ключи могут быть созданы, очевидно, с любой комбинацией p и g, даже если они не простые, я нахожу это интригующим.Это может быть только для безопасности?Если да, то как его увеличить?

Заранее спасибо

Даниэль

Answer 1

Если g не является примитивным корнем из p , g будет генерировать только подгруппу из GF _p . Это имеет последствия для свойств безопасности системы: безопасность системы будет пропорциональна порядку g в GF _p вместо пропорциональной полный заказ GF _p .

Чтобы взять небольшой пример: выберите p = 13 и g = 3.

Порядок 3 в GF_13 равен 3 (3 ^ 1 = 3, 3 ^ 2 = 9, 3 ^ 3 = 1).

Следуя обычным шагам Диффи-Хеллмана, Алиса и Боб должны выбрать целые числа a , b между 1 и p -1 и вычислить соотв. A = г ^a и B = g ^b . Чтобы перебить это, злоумышленник должен попытаться использовать все возможные значения a (или b ) в диапазоне от 1 до p -1, пока не найдет значение, которое дает A (или B ). Но поскольку g не был примитивным корнем по модулю p , ему нужно всего лишь попробовать значения 1, 2 и 3, чтобы найти решение a ', поэтому что A = g ^{a '}. И секрет в с = г ^ab = (г ^a ) ^b = (г ^{a '}) ^b = г ^a'b = (г ^b ) ^{a '} = B ^a' , который теперь может вычислить атакующий.

Answer 2

Нет требования, чтобы генератор g, используемый для Диффи-Хеллмана, был примитивным корнем, и это даже не распространенный выбор. Гораздо более популярным является выбор g таким, чтобы он генерировал подгруппу простого порядка. То есть порядок g - это простое число q, которое является большим простым множителем для p-1.

Например, группы Диффи-Хеллмана, предложенные для IKE , были выбраны так, что p - безопасное простое число, а g генерирует подгруппу порядка (p-1) /2.

.

Одной из причин выбора g в качестве генератора большой подгруппы простого порядка является то, что это позволяет предположение Диффи-Хеллмана . Это предположение не выполняется, если g является примитивным корнем, и это несколько усложняет анализ реализованных протоколов.

Answer 3

Безопасность Диффи-Хеллмана , а не в зависимости от сложности факторинга.Он основан на (предполагаемой) сложности вычисления общих дискретных логарифмов.

g должен быть корнем примитива p , чтобы алгоритм был корректным и применимым.Он гарантирует, что для каждого числа 0 <= x <p </strong> имеется отдельное значение g ^x mod p .Это значит, что g может «генерировать» каждое значение в конечном поле.