3.2Алгоритм Диффи-Хеллмана – протокол генерации секретного ключа.

Диффи и Хелман предложили для создания криптографических систем с открытым ключом функцию дискретного возведения в степень.

Необратимость преобразования в этом случае обеспечивается тем, что достаточно легко вычислить показательную функцию в конечном поле Галуа состоящим из p элементов. (p - либо простое число, либо простое в любой степени, конечное поле Галуа – числа от 0 до р-1). Вычисление же логарифмов в таких полях - значительно более трудоемкая операция. Операция «остаток от деления» позволяет оставаться в заданном диапазоне чисел, то есть в поле Галуа.

Если y=^x,, 1<x<p-1, где - фиксированный элемент поля GF(p), то x=log_ y над GF(p). Имея x, легко вычислить y. Для этого потребуется log₂(x) операций умножения. Все операции выполняются по модулю р.

Обратная задача вычисления x из y будет достаточно сложной. Если p выбрано достаточно правильно (простое число или число, равное произведению двух простых чисел), то извлечение логарифма потребует количества операций:

L(p) = exp { (ln p ln ln p)^0.5 }

Для обмена информацией первый пользователь выбирает случайное число x1, равновероятное из целых 1...p-1. Это число он держит в секрете, а другому пользователю посылает число

y₁ = ^x mod p

Аналогично поступает и второй пользователь, генерируя x2 и вычислив y2, отправляя его первому пользователю. В результате этого они могут вычислять k12 = ^x1x2 mod p.

Для того чтобы вычислить k12, первый пользователь возводит y2 в степень x1. То же делает и второй пользователь. Таким образом, у обоих пользователей оказывается общий ключ k12, который можно использовать для шифрования информации обычными алгоритмами.

В отличие от алгоритма RSA, данный алгоритм не позволяет шифровать собственно информацию.

Не зная x1 и x2, злоумышленник может попытаться вычислить k12, зная только перехваченные y1 и y2. Эквивалентность этой проблемы проблеме вычисления дискретного логарифма есть главный и открытый вопрос в системах с открытым ключом. Простого решения до настоящего времени не найдено.

Алгоритм Диффи-Хелмана не имеет гарантированной нижней оценки трудоемкости раскрытия ключа.

Кроме того, хотя описанный алгоритм позволяет обойти проблему скрытой передачи ключа, необходимость аутентификации остается. Без дополнительных средств, один из пользователей не может быть уверен, что он обменялся ключами именно с тем пользователем, который ему нужен. Опасность имитации в этом случае остается. Рассмотрим схему, при которой злоумышленнику удается не просто прослушивать, а контролировать весь трафик между первым и вторым пользователем. Тогда первый пользователь посылает число у1, злоумышленник выбирает число х2_з, вычисляет у2_з и отправляет его первому пользователю. В результате первый вычислит общий ключ для злоумышленника и первого пользователя. Аналогично злоумышленник поступает со вторым пользователем, то есть посылает ему у2_з, а получив ответ, вычисляет общий для них ключ. Такая атака называется «человек посередине».

Пример: пусть р=31, а=3. Первый пользователь пусть задумал число 7. Он вычисляет 3^7 mod 31=17 и посылает результат второму пользователю. Второй пользователь, в свою очередь, задумывает число 13, вычисляет 3^13 mod 31=24, отправляет результат первому пользователю. Сам же на основании полученного числа 17 вычисляет 17^13 mod 31=3. Первый же пользователь, получив число 24, вычисляет 24^7 mod 31 =3. Как видите, они оба сформировали один и тот же ключ: 3.