Первая система с открытым ключом — система Диффи-Хеллмана

Эта криптосистема была открыта в середине 70-х годов американскими учеными Диффи (Whitfield Diffie) и Хеллманом (Martin Hellman) и привела к настоящей революции в криптографии и ее практических применениях. Это первая система, которая позволяла защищать информацию без использования секретных ключей, передаваемых по защищенным каналам. Для того чтобы продемонстрировать одну из схем применения таких систем, рассмотрим сеть связи с %%N%% пользователями, где %%N%% — большое число.

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

$$С_N^2 = \frac{N(N-1)}{2} \approx \frac{N^2}{2} $$

Если абонентов 100, то требуется 5000 ключей, если же абонентов 104, то ключей должно быть %%5 \cdot 10^7%%. Мы видим, что при большом числе абонентов система снабжения их секретными ключами становится очень громоздкой и дорогостоящей. Диффи и Хеллман решили эту проблему за счет открытого распространения и вычисления ключей. Перейдем к описанию предложенной ими системы.

Пусть строится система связи для абонентов %%А, В, С,....%% У каждого абонента есть своя секретная и открытая информация. Для организации этой системы выбирается большое простое число р и некоторое число %%g%%, %%1 < g < p - 1%%, такое, что все числа из множества %%\{1, 2, ... ,p — 1\}%% могут быть представлены как различные степени %%g\, mod\, p%% (известны различные подходы для нахождения таких чисел %%g%%, один из них будет представлен ниже). Числа %%p%% и %%g%% известны всем абонентам.

Абоненты выбирают большие числа %%X_A,X_B,X_C%%, которые хранят в секрете (обычно такой выбор рекомендуется проводить случайно, используя датчики случайных чисел). Каждый абонент вычисляет соответствующее число %%Y%%, которое открыто передается другим абонентам:

$$Y_A = g^{X_A} mod\, p,$$

$$Y_B = g^{X_B} mod \,p, ~~~~~~~~(1)$$

$$Y_C = g^{X_C} mod \,p$$

В результате получаем следующую таблицу.

Таблица 2.2. Ключи пользователей в системе Диффи-Хеллмана

Абонент	Секретный ключ	Открытый ключ
А	%%Х_А %%	%%Y_A%%
В	%%Х_B%%	%%Y_B%%
С	%%Х_C%%	%%Y_C%%

Допустим, абонент %%А%% решил организовать сеанс связи с %%В%%, при этом обоим абонентам доступна открытая информация из табл. 2.2. Абонент А сообщает В по открытому каналу, что он хочет передать ему сообщение. Затем абонент А вычисляет величину

%%Z_{AB} = (Y_B)^{X_A} mod\, p~~~~~~~~~~~~~(2)%%

(никто другой кроме %%A%% этого сделать не может, так как число %%Х_A%% секретно). В свою очередь, абонент %%В%% вычисляет число

%%Z_{BA} = (Y_A)^{X_B} mod \,p. ~~~~~~~~~~~~~(3)%%

Доказательство. Действительно, %%Z_{AB} = (Y_B)^{X_A} mod\, p = (g^{Х_B})^{Х_A} mod\, p = g^{X_AX_B} = (Y_A)X_B mod \,p = Z_{BA}%% (Здесь первое равенство следует из (2), второе и четвертое — из (1), последнее — из (3).)

Отметим главные свойства системы:

1. абоненты А и В получили одно и то же число %%Z = Z_{AB} = Z_{BA}%%, которое не передавалось по открытой линии связи;
2. С не знает секретных чисел %%Х_A,Х_B,..%%, поэтому не может вычислить число %%Z_AB%% (вообще говоря, он мог бы попытаться найти секретное число %%Х_A%% по %%Y_A%% (см. (1)), однако при больших %%p%% это практически невозможно (требуются миллионы лет)).

Абоненты %%А%% и %%В%% могут использовать %%Z_{AB}%% в качестве секретного ключа для шифрования и дешифрования данных. Таким же образом любая пара абонентов может вычислить секретный ключ, известный только им. Остановимся теперь на упомянутой выше задаче выбора числа %%g%%.

При произвольно заданном р она может оказаться трудной задачей, связанной с разложением на простые множители числа %%p - 1%%. Дело в том, что для обеспечения высокой стойкости рассмотренной системы число %%p - 1%% должно обязательно содержать большой простой множитель. Поэтому часто рекомендуют использовать следующий подход. Простое число %%р%% выбирается таким, чтобы выполнялось равенство %%p=2q + 1%%, где %%q%% — также простое число. Тогда в качестве %%g%% можно взять любое число, для которого справедливы неравенства %%1<g<p - 1%% и $$g^q mod\, p \not=1.$$