Задача распределения ключей

Ситуация такова: X и Y хотят связываться друг с другом с помощью оговоренной системы шифрования. Третьему лицу, Z, известна эта их оговоренная система шифрования, он в состоянии перехватывать сообщения и желает иметь возможность читать их. X и Y могут знать, а могут и не знать о существовании Z, но они хотят быть уверены в том, что их сообщения должны быть непонятны всем, кроме них самих. Они обязаны допускать, что данная система шифрования известна как Z, так и всем окружающим. Система требует использования одного или более ключей, которые необходимо держать в секрете, и которые могут меняться время от времени (возможно, для каждого сообщения, а возможно, и реже). Каждый, кто получит доступ к ключам, и кто знает метод шифрования, сможет расшифровать их сообщения, поэтому необходимо сохранение этих ключей втайне. Каким образом X и Y могут сообщить друг другу свои ключи, не опасаясь того, что Z их перехватит и сможет воспользоваться ими?

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

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

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

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

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

k_x = m^x(mod p)

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

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

k_y = m^y(mod p)

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

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

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

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

Пример 12.1

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

Решение

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

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

3⁷=2187=3759+4,

3¹¹=177147=593002+29,

поэтому k_x=4, а k_y=29.

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

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

поэтому

4¹⁰441=759+2828(mod 59),

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

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

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

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

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

поэтому

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

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

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

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

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

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

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

k_x=2⁵=321(mod 31),

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