logo search
Коды и шифры

Система ключевого обмена Диффи-Хеллмана

Изящное решение задачи ключевого обмена было предложено Диффи и Хеллманом в 1976 году (см. [12.6]). Чтобы воспользоваться этим методом, пользователям X и Y необходимо выполнить следующее:

  1. X и Y договариваются об использовании двух целых чисел (например, p и m), где p - большое простое число, а m заключено между 1 и (p1). Значения p и m не нужно держать в секрете.

  2. Пользователь X случайно выбирает секретное число x, а пользователь Y случайно выбирает секретное число y. Числа x и y лежат в диапазоне от 1 до (p1), и ни одно их них не должно иметь общих делителей с (p1). В частности, поскольку (p1) четно, то ни x, ни y не могут быть четными. Ни X, ни Y не сообщают свои секретные числа ни друг другу, ни кому-либо еще.

  3. Пользователь X вычисляет выражение

kx = mx(mod p)

и посылает его пользователю Y, который возводит его в степень y, при этом получается число (kx)y.

Пользователь Y вычисляет выражение

ky = my(mod p)

и посылает его пользователю X, который возводит его в степень x, при этом получается число (ky)x.

  1. Поскольку (kx)y = (ky)x  mxy(mod p), то получившееся число K = mxy(mod p) может быть использовано как пользователем X, так и пользователем Y в качестве общего ключа, хотя ни один из них не знает секретного ключа другого.

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

В реальных условиях простое число p должно быть очень большим, но суть метода можно проиллюстрировать с помощью простого числа средней величины.

Пример 12.1

Пусть для системы Диффи-Хеллмана p=59, m=3, x=7 и y=11. Каковы будут значения kx, ky и K?

Решение

  1. Во-первых, заметим, что (p1)=58=229, и это число не имеет общих делителей ни с x, ни с y.

  2. Пользователь X вычисляет значение 37(mod 59), а пользователь Y вычисляет значение 311(mod 59). Эти вычисления можно производить по-разному, некоторые способы эффективнее других (см. приложение М22). В нашем случае числа достаточно маленькие, и возведение в степень можно произвести на карманном калькуляторе. Итак,

37=2187=3759+4,

311=177147=593002+29,

поэтому kx=4, а ky=29.

  1. Значение общего ключа K получится, если вычислить либо выражение 411(mod 59), либо 297(mod 59). Оба выражения должны дать один и тот же результат; если это не так, то мы сделали ошибку. Поэтому для проверки вычислим оба значения. Теперь числа получаются довольно большие, поэтому вычислим их, приводя по модулю 59 после каждого возведения в степень:

  1. 45=1024=1759+2121(mod 59),

поэтому

410441=759+2828(mod 59),

и следовательно,

411428=112=159+5353(mod 59).

Приходим к выводу, что общий ключ K равен 53.

  1. Производим проверку, вычисляя значение 297(mod 59).

292=841=1459+1515(mod 59),

поэтому

2932915=435=759+2222(mod 59).

Возводим в квадрат:

296484=859+1212(mod 59).

Окончательно,

2972912=348=559+5353(mod 59),

и мы получаем подтверждение, что в данном случае K=53.

Причина ограничения на отсутствие у чисел x и y общих делителей с (p1) заключается в том, что, если например, x имеет такой общий делитель, то значение kx, а следовательно, и значение общего ключа K, может оказаться равным 1 вне зависимости от значения y, что неприемлемо с криптографической точки зрения. Например, если p=31 и m=2, то ни x, ни y не должны иметь общих делителей с числом 30. Если бы X выбрал, например, число x=5, то

kx=25=321(mod 31),

и следовательно, kx=1, а с ним и K=1 независимо от того, какое значение y выберет пользователь Y.