Открытое распределение ключей Диффи-Хеллмана

Под открытым распределением ключей понимают последовательность действий двух или более пользователей, в результате выполнения которой им становится доступна некоторая общая секретная информация (ключ). При этом любой другой пользователь, следящий за передаваемыми по каналу связи сообщениями, эту секретную информацию определить не в состоянии. В работе [DH. W.Diffie, M.E. Hellman. New directions in cryptography, IEEE Transactions on Information Theory, v.IT-22, N.6, November,1976, pp.644-654] был предложен так называемый экспоненциальный ключевой обмен, который в настоящее время называется схемой открытого распределения ключей Диффи-Хеллмана. Данная схема основана на использовании функции возведения в степень в мультипликативной группе простого поля: , где p – простое число, a – примитивный элемент поля GF(p), 1<x<p-1. Эта функция является кандидатом в однонаправленные. Действительно, она легко вычислима, так как, используя метод квадратов, значения этой функции можно вычислять с полиномиальной сложностью, оцениваемой величиной O((log p)³), в то время как обратная задача – задача инвертирования функции – является сложной. Для инвертирования функции f(x) необходимо уметь решать уравнение , то есть уметь решать задачу дискретного логарифмирования в мультипликативной группе простого поля. В настоящее время не известно достаточно эффективных (полиномиальных относительно logp) алгоритмов дискретного логарифмирования в мультипликативной группе GF(p)^* поля. Этот факт и лежит в основе стойкости данной схемы открытого распределения ключей. Опишем ее.

Пусть два пользователя A и B хотят выработать общий ключ. Для этого они заранее определяют элементы p и a, которые считаются общедоступными. Оба пользователя случайно выбирают по одному натуральному числу x_A и x_B: 1<x_A, x_B<p-1 и оставляют их в секрете. После этого выполняется следующая последовательность шагов.

1) A вычисляет элемент y_A = и посылает его B;

2) B вычисляет элемент y_B = и посылает его A;

3) A вычисляет элемент ;

4) B вычисляет элемент .

Таким образом, A и B получают общий элемент поля GF(p), равный , который и объявляется их общим ключом. Пассивный криптоаналитик получает в свое распоряжение величины p, a, , и хочет определить . Эта задача называется проблемой Диффи-Хеллмана. В настоящее время не найдено более эффективного решения этой проблемы, чем дискретное логарифмирование.

Глава 5.