Указание к работе

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

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

Предположим, что двум абонентам необходимо провести конфиденциальную переписку, а в их распоряжении нет первоначально оговоренного секретного ключа. Однако между ними существует канал, защищенный от модификации, то есть данные, передаваемые по нему, могут быть прослушаны, но не изменены (такие условия имеют место довольно часто). В этом случае две стороны могут создать одинаковый секретный ключ, ни разу не передав его по сети, по следующему алгоритму.

Рис. Обмен ключами по схеме Диффи - Хеллмана.

Алгоритм заключается в следующем:

1. Глобальные открытые элементы:
q - простое число
a - первообразный корень q

2. Вычисление ключа абонентом A:

· выбирается секретное число X_A (X_A < q)

· вычисление открытого значения Y_A:

3. Вычисление ключа абонентом B:

· выбирается секретное число X_B (X_B < q)

· вычисление открытого значения Y_B:

4. Вычисление секретного ключа абонентом A:

5. Вычисление секретного ключа абонентом B:

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

Пример:

Пусть q = 97 и a = 5

Абонент A: Сгенерировал случайное число X_A = 36

Абонент B: Сгенерировал случайное число X_B = 58

Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент: ,

Потом они обмениваются этими элементами по каналу связи. Теперь абонент A, получив Y_B и зная свой секретный элемент X_A, вычисляет общий ключ: .

Аналогично поступает абонент B: