Математические основы защиты информации. Ишмухаметов Ш.Т - 63 стр.

Методы, основанные на задаче дискретного логарифмирования                 64

4.1. Протокол Диффи-Хеллмана
Этот протокол предназначен для формирования общего секретного ключа
для двух удаленных пользователей, общающихся через открытые сети.
Обозначим этих пользователей буквами A и B .

        Алгоритм протокола Диффи-Хеллмана.
        I. Первая часть протокола состоит в генерации ключей – простого
числа p длины 1024 бита или более, и нахождения генератора группы по
умножению поля Fp . Напомним, что элемент a, 1 < a < p, называется
генератором (порождающим элементом), если любой другой ненулевой
элемент b ∈ Fp , b ̸= 0, является степенью элемента a.

        Пример. Пусть p = 13. Вычислим все степени элементов 2 и 3 в поле
F13 :
             k      1 2 3 4 5      6   7   8 9 10 11 12
        2k mod 13 2 4 8 3 6 12 11 9 5 10             7   1
        3k mod 13 3 9 1 3 9        1   3   9 1   3   9   1
        Таким образом, 2 является генератором поля, а 2 – нет. Для
поиска простого числа p можно воспользоваться тестом Миллера-Рабина.
Выбирается произвольное нечетное простое число t заданной длины,
проверяется условие t mod q ̸= 0 для всех небольших простых чисел, затем
выполняется несколько раундов проверок алгоритма Миллера-Рабина. Если
число не проходит этот тест, то рассмотрим следующее число t + 2 и т.д.
        Для поиска порождающего элемента можно проверять все элементы
подряд, начиная от 2, непосредственным возведением в степень, либо
используя тест Поклингтона.
        После того, как число p и генератор g поля Fp найдены, эти
параметры распространяются среди участников протокола. Параметры p и
a не являются секретными, и их передача выполняется по открытому каналу.
Эти параметры могут быть использованы многократно.

        II. Вторая часть состоит в выработке общего секретного ключа и
состоит из следующих шагов: