Протокол Диффи – Хеллмана

20 
решала основную проблему классической криптографии – проблему 
распределения ключей. 
Алгоритм основан на трудности вычисления дискретных логарифмов. В 
этом алгоритме, как и во многих других алгоритмах с открытым ключом, 
вычисления выполняются по модулю некоторого большого простого числа Р. 
Сначала специальным образом подбирается некоторое натуральное число А, 
меньшее Р. Если нужно зашифровать значение X, то вычисляется
Y = A
x
mod P.
(1.1) 
При этом, имея Х, вычислить Y легко. Обратная задача вычисления X из 
Y является достаточно сложной. Экспонента X и называется дискретным 
логарифмом Y. Таким образом, зная о сложности вычисления дискретного 
логарифма, число Y можно открыто передавать даже по незащищенному 
каналу связи, так как при большом модуле P исходное значение Х подобрать 
будет практически невозможно. Алгоритм Диффи – Хеллмана для 
формирования ключа основан на этом математическом факторе. 
Пусть два пользователя, пользователь 1 и пользователь 2, желают 
сформировать общий ключ для алгоритма симметричного шифрования. 
Вначале они должны выбрать большое простое число Р и некоторое 
специальное число А, которое 1 < A < P-1, такое, что все числа из интервала [1, 
2, ..., Р-1] могут быть представлены как различные степени А mod Р. Всем 
абонентам системы эти числа должны быть известны и могут выбираться 
открыто. Это будут общие параметры[4]. 
Затем пользователь 1 выбирает число Х
1
, такое, что X
1
формировать с помощью генератора случайных чисел. Это будет закрытый 
ключ первого пользователя, и он должен храниться в секрете. На основе 
закрытого ключа пользователь 1 вычисляет число: 
(1.2) 
которое он отправляет второму пользователю. Второй абонент поступает 
аналогично, генерируя X
2 
и вычисляя 

21 
(1.3) 
Этот результат отправляется первому пользователю. 
После этого у пользователей есть следующая информация: 
Таблица 1 – Параметры ключей шифрования 
Общие параметры Открытый ключ 
Закрытый ключ 
1й пользователь 
P, A 
Y
1
X
1
2й пользователь 
Y
2
X
2
Из чисел Y
1
и Y
2
, а также из личных закрытых ключей каждый 
пользователь может сгенерировать общий секретный ключ Z для сеанса 
симметричного шифрования. Первый пользователь: 
(1.4) 
 
Никто, кроме первого пользователя, не может этого сделать, так как 
число Х
1
секретно. Второй пользователь может получить такое же число Z, 
используя свои закрытый ключ и открытый ключ пользователя 1:
(1.5) 
 
Если весь протокол формирования общего секретного ключа выполнен 
верно, значения Z у одного и второго абонента должны получиться 
одинаковыми. Причем, что самое важное, злоумышленник, не зная секретных 
чисел Х
1
и Х
2
, не сможет вычислить Z. Не зная Х
1
и Х
2
, он может попытаться 
вычислить Z, используя только передаваемые открыто значения Р, А, Y
1
и Y
2
. 
Безопасность формирования общего ключа в алгоритме Диффи - 
Хеллмана исходит из того факта, что, хотя относительно легко высчитать 
экспоненты по модулю простого числа, очень трудно вычислить дискретные 
логарифмы. Задача считается неразрешимой для больших простых чисел 
размером сотни и тысячи бит, так как требует колоссальных затрат 
вычислительных ресурсов. 
Первый и второй пользователи могут использовать число Z в качестве 
секретного ключа как для шифрования, так и для расшифрования данных. 

22 
Таким же образом любая пара абонентов может вычислить секретный ключ, 
известный только им. 

жүктеу/скачать 1,65 Mb.

Достарыңызбен бөлісу: