Схема обмена ключами Диффи — Хеллмана была изобретёна в 1976 году американскими учеными В. Диффи и М. Хеллманом. Прообразом представленного алгоритма послужила работа Р. Меркле, в которой автор представил новаторскую идею о системе распространения публичных ключей. Алгоритм Диффи-Хеллмана стал первым практическим методом для получения общего секретного ключа при общении через незащищенный канал связи. В качестве трудноразрешимой задачи была использована задача нахождения дискретного логарифма.

Предположим, что обоим абонентам известны некоторые два числа g и p. Данные числа известны и всем остальным заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба Корреспондента генерируют большие случайные числа: Корреспондент 1 — число a, Корреспондент 2 — число b. Затем Корреспондент 1 вычисляет значение A = g^a mod p и пересылает его второму, а второй вычисляет B = g^b (mod p) и передаёт первому. Злоумышленник получает оба этих значения, но модифицировать их (вмешаться в процесс передачи) не может. На втором этапе Корреспондент 1 на основе имеющегося у него a и полученного по сети B вычисляет значение B^a (mod p) = g^ab (mod p), а Корреспондент 2 на основе имеющегося у него b и полученного по сети A вычисляет значение A^b (mod p) = g^ab (mod p). Нетрудно видеть, у обоих Корреспондентов получилось одно и то же число: K = g^ab (mod p). Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления g^ab (mod p) по перехваченным g^a (mod p) и g^b (mod p), если числа g, p, a, b выбраны достаточно большими.

Рис1. Схема обмена ключами Диффи - Хеллмана

При работе алгоритма, каждый Корреспондент выполняет следующие действия:

• генерирует случайное натуральное число a / b — закрытый ключ;
• совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где p является случайным простым числом, g является первообразным корнем по модулю p;
• вычисляет открытый ключ A / B, используя преобразование над закрытым ключом:

A = g^a (mod p) / B=g^b (mod p);

• обменивается открытыми ключами с удалённой стороной;
• вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B/A и свой закрытый ключ a/b:

K = B^a (mod p) / K = A^b (mod p)

К получается равным с обоих сторон, поскольку:

B^a (mod p) = (g^b (mod p))^a (mod p) = g^ab (mod p) = (g^a (mod p))^b (mod p) = A^b (mod p).

В практических реализациях, для a и b используются числа порядка 10¹⁰⁰ и p порядка 10³⁰⁰. Число g не должно быть большим и обычно имеет значения 2 или 5.

Криптографическая стойкость алгоритма Диффи - Хеллмана (то есть сложность вычисления K=g^ab (mod p) по известным p, g, A=g^a (mod p) и B=g^b (mod p), основана на предполагаемой сложности проблемы дискретного логарифмирования.

Алгоритм применим в случае, если необходимо провести конфиденциальную переписку, при которой:

• в распоряжении абонентов нет первоначально оговорённого секретного ключа;
• существует канал, защищенный от модификации, то есть данные, передаваемые по нему, могут быть прослушаны, но не изменены (такие условия имеют место довольно часто).

Необходимо еще раз отметить, что алгоритм Диффи - Хеллмана работает только на линиях связи, надёжно защищённых от модификации. Если бы он был применим на любых открытых каналах, то давно снял бы проблему распространения ключей и, возможно, заменил собой всю асимметричную криптографию. Однако, в тех случаях, когда в канале возможна модификация данных, появляется очевидная возможность вклинивания в процесс генерации ключей «злоумышленника-посредника» по той же самой схеме, что и для асимметричной криптографии.