Система распределения ключей Диффи-Хелмана.

Эта система позволяет пользоателям обмениваться секретными ключами по незащищенным каналам связи. Разработана в 1976г и основана на задаче о дискретном логарифмировании.

Пусть N - некоторое большое целое число, а G - другое целое, такое что

Рассмотрим процедуру обмена ключами по шагам.

Вначале Алекс и Юстас достигают соглашения о значениях N и G (как правило, эти значения являются стандартными для всех пользователей системы).

Затем Алекс выбирает некоторое большое целое число X и вычисляет
XX = G^X MOD N.
Аналогичным образом Юстас выбирает число Y и вычисляет
YY = G^Y MOD N.
После этого Алекс и Юстас обмениваются значениями XX и YY. (Мы считаем, что все данные, которые передаются по каналу связи, могут быть перехвачены злоумышленником - стариной Мюллером). Числа X и Y Алекс и Юстас хранят в секрете.

Получив от Юстаса число YY, Алекс вычисляет
K(1) = YY^X MOD N,
а Юстас -
K(2) = XX^Y MOD N.

Но (!)

YY^XMODN = G^(X*Y) MODN = XX^YMODN,
а следовательно,

K(1) = K(2) = K.

Это значение K и является ключом, который используется для шифрования сообщений.

Злоумышленник, перехвативший G, N, XX и YY, тоже должен определить значение ключа K.Вычислении значение X по G, N, XX и есть задача дискретного логарифмирования в чистом виде, которая считается неразрешимой.

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

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

Рассмотрим, как же используются системы с открытым ключом.

Пользователь Алекс имеет в своем распоряжении два алгоритма: E для шифрования и D для расшифровки сообщений. При этом алгоритм E делается общедоступным, например, через использование каталога ключей, а алгоритм D хранится Алексом в секрете Расшифровать сообщение сможет только тот, укого есть алгоритм D.

D(E(M)) = M,

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

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