Алгоритм обмена ключами Diffie-Hellman

Алгоритм обмена ключами Diffie-Hellman — это криптографический протокол, позволяющий двум сторонам, не имеющим предварительно установленного общего секрета, получить идентичный секретный ключ, используя незащищённый канал связи. Алгоритм, предложенный в 1976 году, стал первой практической реализацией концепции асимметричной криптографии, хотя сам по себе не является шифром, а служит для выработки общего ключа, который впоследствии может быть использован для симметричного шифрования.

История

Идея открытого распределения ключей была впервые опубликована Уитфилдом Диффи и Мартином Хеллманом в 1976 году в статье «New Directions in Cryptography». Однако, как стало известно позже, аналогичный алгоритм был разработан сотрудниками Центра правительственной связи Великобритании (GCHQ) Джеймсом Эллисом, Клиффордом Коксом и Малкольмом Уильямсоном ещё в 1969–1975 годах, но оставался засекреченным до 1997 года.

Публикация алгоритма произвела революцию в криптографии, поскольку до этого считалось, что для защищённой связи стороны обязательно должны заранее обменяться секретным ключом по надёжному каналу. Диффи и Хеллман показали, что можно безопасно договориться о ключе через открытую сеть, используя математические свойства модульной арифметики и задачи дискретного логарифмирования.

Математические основы

Алгоритм основан на сложности вычисления дискретного логарифма в конечном поле. Для его работы необходимы два общеизвестных параметра:

• p — большое простое число (обычно длиной от 1024 до 4096 бит);
• g — примитивный элемент (генератор) мультипликативной группы по модулю p, то есть число, степени которого по модулю p порождают все ненулевые элементы поля.

Безопасность протокола обеспечивается тем, что, зная \( g^a \mod p \) и \( g^b \mod p \), вычислить \( g^{ab} \mod p \) без знания a или b практически невозможно для достаточно больших p.

Описание протокола

Протокол работает в два этапа. Пусть Алиса и Боб хотят получить общий секретный ключ.

Этап 1: Генерация и обмен открытыми ключами

1. Алиса выбирает случайное секретное число a (закрытый ключ) и вычисляет открытый ключ \( A = g^a \mod p \).
2. Боб выбирает случайное секретное число b (закрытый ключ) и вычисляет открытый ключ \( B = g^b \mod p \).
3. Алиса и Боб обмениваются значениями A и B по открытому каналу.

Этап 2: Вычисление общего секрета

1. Алиса, получив B, вычисляет \( S = B^a \mod p = (g^b)^a \mod p = g^{ab} \mod p \).
2. Боб, получив A, вычисляет \( S = A^b \mod p = (g^a)^b \mod p = g^{ab} \mod p \).

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

Пример

Для наглядности рассмотрим малые числа (небезопасные в реальном применении):

• Пусть p = 23, g = 5.
• Алиса выбирает a = 6: \( A = 5^6 \mod 23 = 8 \).
• Боб выбирает b = 15: \( B = 5^{15} \mod 23 = 19 \).
• Алиса вычисляет \( S = 19^6 \mod 23 = 2 \).
• Боб вычисляет \( S = 8^{15} \mod 23 = 2 \).

Общий секрет — 2.

Классификация и варианты

Анонимный протокол Diffie-Hellman (DH)

Базовая версия, описанная выше. Не обеспечивает аутентификации сторон, поэтому уязвим для атаки «человек посередине» (MITM). Злоумышленник может перехватить открытые ключи и подменить их, установив два отдельных сеанса с каждой стороной.

Аутентифицированный протокол Diffie-Hellman

Для защиты от MITM используется цифровая подпись открытых ключей или сертификаты. Примеры:

• Station-to-Station (STS) — протокол, в котором стороны обмениваются подписанными ключами.
• IKE (Internet Key Exchange) — часть протокола IPsec, использующая аутентифицированный DH.

Эллиптический вариант (ECDH)

Вместо модульной арифметики используется эллиптическая криптография. ECDH обеспечивает эквивалентную стойкость при меньшей длине ключа. Например, 256-битный ключ ECDH по стойкости сопоставим с 3072-битным классическим DH.

Статический и эфемерный DH

• Статический DH: одна из сторон использует долговременный (статический) закрытый ключ. Применяется для долгосрочных сеансов.
• Эфемерный DH (DHE): обе стороны генерируют новые случайные ключи для каждого сеанса. Обеспечивает совершенную прямую секретность (PFS) — даже при компрометации долговременного ключа прошлые сеансы остаются защищёнными.

Применение

Протоколы безопасности

• TLS/SSL: используется для защиты веб-трафика (HTTPS). В современных версиях (TLS 1.3) применяется ECDHE (эллиптический DH с эфемерными ключами).
• IPsec: протокол IKE использует DH для выработки ключей шифрования.
• SSH: при установке соединения стороны обмениваются ключами по DH.
• WireGuard: современный VPN-протокол, использующий Curve25519 (вариант ECDH).

Системы электронной почты

• OpenPGP: для шифрования сообщений может применяться DH, хотя чаще используется RSA или ECC.

Криптовалюты

• Биткоин: для создания мультиподписных адресов и некоторых видов транзакций используется ECDH.

Криптоанализ и уязвимости

Атака «человек посередине»

Как упоминалось, базовая версия DH не защищена от MITM. Решение — использование цифровых сертификатов или предварительно согласованных секретов.

Атаки на малые подгруппы

Если параметр p выбран так, что порядок группы имеет малые делители, злоумышленник может подменить открытый ключ так, чтобы общий секрет оказался в малой подгруппе. Защита: использование простых чисел safe prime (p = 2q + 1, где q — простое) или проверка, что полученное значение не равно 1 и не принадлежит малой подгруппе.

Атаки с использованием квантового компьютера

Задача дискретного логарифмирования эффективно решается на квантовом компьютере с помощью алгоритма Шора. Это означает, что классический DH и ECDH уязвимы для квантового криптоанализа. В ответ разрабатываются постквантовые алгоритмы, такие как CRYSTALS-Kyber (для обмена ключами) и другие.

Logjam-атака (2015)

Атака на DH-обмены с использованием 512-битных простых чисел. Показала, что многие серверы используют слабые параметры. В результате были повышены минимальные требования к длине p (до 2048 бит).

Интересные факты

• Алгоритм Диффи-Хеллмана является первым в истории криптографическим протоколом с открытым ключом, хотя сама идея асимметричной криптологии была предложена ранее.
• В 2015 году за вклад в криптографию Уитфилд Диффи и Мартин Хеллман получили премию Тьюринга.
• Параметры p и g для DH часто стандартизированы (например, в RFC 3526 описаны «модульные группы» для IPsec).
• В некоторых реализациях (например, в OpenSSL) для ускорения вычислений используются предварительно вычисленные таблицы степеней g.

Источники

• Diffie, W., Hellman, M. (1976). «New Directions in Cryptography». IEEE Transactions on Information Theory.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography».
• Schneier, B. (1996). «Applied Cryptography: Protocols, Algorithms, and Source Code in C».
• RFC 2631 — Diffie-Hellman Key Agreement Method.
• RFC 3526 — More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE).
• Стинсон, Д. (2005). «Криптография: теория и практика».