Diffie-Hellman

Diffie-Hellman (протокол Диффи — Хеллмана) — это криптографический протокол, позволяющий двум или более сторонам установить общий секретный ключ по незащищённому каналу связи. Протокол был впервые опубликован в 1976 году Уитфилдом Диффи и Мартином Хеллманом и стал одним из первых практических методов обмена ключами, на котором основана современная асимметричная криптография. Основное свойство протокола — стойкость к пассивному перехвату: даже если злоумышленник перехватывает все сообщения между сторонами, он не может вычислить общий секретный ключ без решения сложной математической задачи (дискретного логарифмирования).

История

Предпосылки создания

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

Публикация и признание

В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали статью «New Directions in Cryptography» (Новые направления в криптографии), где впервые описали принцип асимметричного шифрования и конкретный протокол обмена ключами. Работа была выполнена в Стэнфордском университете. Позднее выяснилось, что аналогичная идея была независимо разработана в 1974 году британским криптографом Малкольмом Уильямсоном из Центра правительственной связи (GCHQ), но оставалась засекреченной до 1997 года.

Патент и коммерциализация

В 1977 году Диффи и Хеллман получили патент США на протокол (US Patent 4,200,770), который был выдан в 1980 году. Патент истёк в 1997 году, что способствовало широкому внедрению протокола в открытые стандарты, такие как SSL/TLS, SSH и IPsec.

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

Задача дискретного логарифмирования

Безопасность протокола основана на вычислительной сложности задачи дискретного логарифмирования в конечных полях. Для простого числа \( p \) и первообразного корня \( g \) (генератора мультипликативной группы \( \mathbb{Z}_p^* \)) задача состоит в нахождении целого числа \( a \) по известным \( g^a \mod p \). Для больших \( p \) (например, 2048 бит) эта задача считается практически неразрешимой при современном уровне вычислительной техники.

Односторонняя функция

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

Алгоритм работы

Базовый протокол (две стороны)

1. Выбор общих параметров: стороны договариваются о большом простом числе \( p \) и генераторе \( g \) (обычно \( g = 2 \) или \( g = 5 \)). Эти параметры могут быть открытыми.
2. Генерация секретных ключей: каждая сторона (Алиса и Боб) выбирает случайное секретное число:

• Алиса выбирает \( a \) (секретный ключ Алисы).
• Боб выбирает \( b \) (секретный ключ Боба).

1. Вычисление открытых ключей:

• Алиса вычисляет \( A = g^a \mod p \) и отправляет Бобу.
• Боб вычисляет \( B = g^b \mod p \) и отправляет Алисе.

1. Вычисление общего секрета:

• Алиса вычисляет \( s = B^a \mod p = (g^b)^a \mod p = g^{ab} \mod p \).
• Боб вычисляет \( 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 \).
• Общий секрет: \( s = 2 \).

Многосторонний протокол

Протокол может быть расширен на \( n \) сторон. Например, для трёх сторон (Алиса, Боб, Кэрол) требуется три раунда обмена. Однако на практике для групповой связи чаще используются другие методы (например, протоколы на основе дерева ключей).

Виды и модификации

Статический Diffie-Hellman

Одна из сторон использует фиксированный секретный ключ (например, сертифицированный в инфраструктуре открытых ключей). Это позволяет проверять подлинность стороны, но снижает стойкость к компрометации ключа.

Эфемерный Diffie-Hellman (DHE)

Каждая сторона генерирует новый секретный ключ для каждого сеанса связи. Это обеспечивает свойство совершенной прямой секретности (PFS): даже если долговременный ключ будет скомпрометирован, прошлые сеансы остаются защищёнными. Используется в протоколах TLS (DHE-RSA, DHE-DSS).

Elliptic-curve Diffie–Hellman (ECDH)

Вариант протокола, использующий эллиптические кривые вместо конечных полей. Обеспечивает аналогичную безопасность при меньших размерах ключей (например, 256-битная эллиптическая кривая эквивалентна 3072-битному модулю). Широко применяется в современных протоколах (TLS 1.3, SSH, Signal).

Анонимный Diffie-Hellman

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

Применение

Защищённые протоколы передачи данных

• TLS/SSL: протоколы защиты веб-трафика (HTTPS) активно используют DHE и ECDH для установления сеансовых ключей. В версии TLS 1.3 обязательным является использование ECDHE.
• SSH: протокол безопасного удалённого доступа к серверам использует Diffie-Hellman для обмена ключами при установлении соединения.
• IPsec: набор протоколов для защиты IP-трафика (VPN) включает Diffie-Hellman в рамках IKE (Internet Key Exchange).

Шифрование сообщений

• Signal Protocol: протокол сквозного шифрования, используемый в мессенджерах Signal, WhatsApp (принадлежит организации Meta, признанной экстремистской и запрещённой в РФ) и Skype, основан на тройном Diffie-Hellman (X3DH) для установления начального ключа.
• PGP/GPG: системы шифрования электронной почты могут использовать Diffie-Hellman для обмена ключами (в режиме ElGamal).

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

• Bitcoin: протокол использует ECDH для создания общих секретов при мультиподписных транзакциях и в Lightning Network.
• Ethereum: аналогичное применение в смарт-контрактах для безопасного обмена данными.

Безопасность и уязвимости

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

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

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

Если \( p \) выбрано неудачно, злоумышленник может манипулировать значениями так, чтобы общий секрет оказался в малой подгруппе, что упрощает его вычисление. Для защиты используются безопасные простые числа (safe primes) или проверки принадлежности к группе.

Квантовая угроза

Протокол уязвим для атак с использованием квантового компьютера: алгоритм Шора эффективно решает задачу дискретного логарифмирования. Это стимулирует разработку постквантовых криптосистем (например, на основе решёток).

Уязвимости реализации

• Logjam (2015): атака на протоколы TLS, использующие Diffie-Hellman с экспортными (512-битными) модулями. Позволяла снизить стойкость до 512 бит и взломать сеанс.
• Heartbleed (2014): уязвимость в OpenSSL, позволявшая извлекать секретные ключи из памяти сервера, что компрометировало обмен ключами.

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

• Протокол был запатентован в США, но патент истёк в 1997 году, что способствовало его широкому внедрению в открытые стандарты.
• В 2015 году АНБ (Агентство национальной безопасности США) рекомендовало переход на эллиптические кривые, что привело к массовому внедрению ECDH в TLS 1.3.
• Алгоритм назван в честь авторов, но аналогичная идея была независимо открыта в GCHQ на два года раньше.

Источники

• Diffie, W., Hellman, M. (1976). «New Directions in Cryptography». IEEE Transactions on Information Theory.
• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). «Handbook of Applied Cryptography».
• Boneh, D., Shoup, V. (2020). «A Graduate Course in Applied Cryptography».
• RFC 2631: Diffie-Hellman Key Agreement Method.
• RFC 8446: The Transport Layer Security (TLS) Protocol Version 1.3.