Протокол Диффи — Хеллмана

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

История

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

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

Протокол Диффи — Хеллмана опирается на сложность задачи дискретного логарифмирования в конечных полях. Основные математические компоненты:

• Циклическая группа: Работа протокола ведётся в мультипликативной группе поля Галуа \( \mathbb{F}_p^* \), где \( p \) — большое простое число. Группа состоит из чисел от 1 до \( p-1 \) с операцией умножения по модулю \( p \).
• Первообразный корень (генератор): Выбирается целое число \( g \), являющееся первообразным корнем по модулю \( p \). Это означает, что степени \( g \) по модулю \( p \) порождают всю группу \( \mathbb{F}_p^* \).
• Дискретное логарифмирование: Для заданных \( g^x \mod p \) и \( g \) вычислить \( x \) (дискретный логарифм) при больших \( p \) (например, 2048 бит) считается вычислительно сложной задачей. Именно эта сложность обеспечивает безопасность протокола.

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

Протокол работает в два этапа: предварительная договорённость о параметрах и непосредственный обмен.

Предварительная договорённость

Стороны (обычно Алиса и Боб) договариваются об открытых параметрах:

• \( p \) — большое простое число (например, 2048 бит).
• \( g \) — первообразный корень по модулю \( p \).

Эти значения могут быть общеизвестными и даже передаваться по незащищённому каналу.

Выполнение протокола

1. Алиса генерирует случайное секретное число \( a \) (закрытый ключ Алисы). Вычисляет \( A = g^a \mod p \) (открытый ключ Алисы). Отправляет \( A \) Бобу.
2. Боб генерирует случайное секретное число \( b \) (закрытый ключ Боба). Вычисляет \( B = g^b \mod p \) (открытый ключ Боба). Отправляет \( B \) Алисе.
3. Алиса получает \( B \) и вычисляет общий секрет: \( K = B^a \mod p = (g^b)^a \mod p = g^{ab} \mod p \).
4. Боб получает \( A \) и вычисляет общий секрет: \( K = A^b \mod p = (g^a)^b \mod p = g^{ab} \mod p \).

В результате обе стороны получают одно и то же число \( K \), которое может быть использовано в качестве симметричного ключа для дальнейшего шифрования данных. Злоумышленник, перехвативший \( p \), \( g \), \( A \) и \( B \), не сможет вычислить \( K \), не найдя \( a \) или \( b \), что требует решения задачи дискретного логарифмирования.

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

Базовый протокол Диффи — Хеллмана не обеспечивает аутентификации сторон. Это делает его уязвимым для атаки «человек посередине» (Man-in-the-Middle, MITM). Атака выглядит следующим образом:

1. Злоумышленник (Мэллори) перехватывает открытые ключи \( A \) и \( B \).
2. Мэллори генерирует свои собственные секретные числа \( m_1 \) и \( m_2 \).
3. Он отправляет Алисе свой открытый ключ \( M_1 = g^{m_1} \mod p \), выдавая себя за Боба.
4. Он отправляет Бобу свой открытый ключ \( M_2 = g^{m_2} \mod p \), выдавая себя за Алису.
5. Алиса и Мэллори устанавливают общий секрет \( K_1 = g^{a m_1} \mod p \). Боб и Мэллори устанавливают общий секрет \( K_2 = g^{b m_2} \mod p \).
6. Все сообщения от Алисы Мэллори расшифровывает ключом \( K_1 \), читает, затем зашифровывает ключом \( K_2 \) и отправляет Бобу (и наоборот). Стороны не подозревают о подмене.

Для защиты от этой атаки протокол Диффи — Хеллмана комбинируют с методами аутентификации:

• Цифровые подписи: Стороны подписывают свои открытые ключи с помощью асимметричного шифрования (например, RSA).
• Сертификаты: Использование инфраструктуры открытых ключей (PKI), где сертификаты удостоверяют принадлежность открытого ключа конкретной стороне.
• Протокол STS (Station-to-Station): Модификация, включающая обмен цифровыми подписями в процессе обмена ключами.

Варианты и модификации

Существует несколько модификаций протокола, адаптированных под разные задачи:

• Анонимный протокол Диффи — Хеллмана: Используется в протоколе TLS при установлении анонимного соединения (например, при использовании анонимных сертификатов). Не обеспечивает аутентификации.
• Эфемерный протокол Диффи — Хеллмана (DHE): Генерирует новые случайные секретные числа \( a \) и \( b \) для каждого сеанса связи. Обеспечивает свойство Perfect Forward Secrecy (PFS) — компрометация долговременного ключа не позволяет расшифровать прошлые сеансы. Используется в TLS (наборы шифров с DHE).
• Протокол Диффи — Хеллмана на эллиптических кривых (ECDH): Вместо группы \( \mathbb{F}_p^* \) использует группу точек эллиптической кривой. Обеспечивает аналогичную безопасность при значительно меньших размерах ключей (например, 256-битный ключ ECDH эквивалентен по стойкости 3072-битному ключу в классической версии). Широко применяется в современных протоколах (TLS 1.3, SSH, Signal Protocol).
• Многосторонний протокол Диффи — Хеллмана: Обобщение на случай \( n \) сторон. Каждая сторона вычисляет свой секретный вклад, и все обмениваются частичными результатами для получения общего группового ключа.

Применение

Протокол Диффи — Хеллмана является фундаментальным строительным блоком современной криптографии. Наиболее распространённые области применения:

• TLS/SSL: Используется в протоколе HTTPS для установления защищённого соединения между браузером и веб-сервером. В версии TLS 1.3 обязательным является использование ECDHE или DHE.
• SSH (Secure Shell): Применяется для аутентификации и установления защищённого канала при удалённом доступе к серверам.
• IPsec (Internet Protocol Security): Используется в протоколе IKE (Internet Key Exchange) для согласования ключей шифрования в VPN-соединениях.
• Signal Protocol: Криптографический протокол, используемый в мессенджерах Signal, WhatsApp, Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ) Messenger (Meta — организация признана экстремистской и запрещена в РФ) и других, основан на комбинации протокола Диффи — Хеллмана с асимметричным шифрованием и протоколом Double Ratchet.
• WireGuard: Современный протокол VPN, использующий Curve25519 (вариант ECDH) для обмена ключами.
• Криптовалюты: Протоколы типа Diffie-Hellman лежат в основе некоторых схем консенсуса и мультиподписей.

Безопасность и критика

Основные угрозы и ограничения протокола:

• Атака «человек посередине»: Как описано выше, без аутентификации протокол уязвим. Требуется дополнительная инфраструктура (PKI, сертификаты).
• Квантовые компьютеры: Задача дискретного логарифмирования, на которой основана безопасность протокола, может быть эффективно решена с помощью алгоритма Шора на достаточно мощном квантовом компьютере. Это делает классический протокол Диффи — Хеллмана уязвимым для квантовых атак. Ведутся разработки постквантовых криптосистем, устойчивых к таким атакам.
• Слабые параметры: Использование недостаточно больших простых чисел \( p \) или некачественных генераторов случайных чисел может сделать протокол уязвимым для атак. Например, известно, что некоторые реализации использовали фиксированные или предсказуемые значения \( p \), что позволяло злоумышленникам вычислить дискретный логарифм.
• Атака по сторонним каналам: Реализации протокола могут быть подвержены атакам, использующим время вычислений, потребление энергии или электромагнитное излучение для извлечения секретных ключей.

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

• В 1977 году Уитфилд Диффи, Мартин Хеллман и Ральф Меркль получили патент США № 4,200,770 на «Криптографический аппарат и метод», который описывал протокол Диффи — Хеллмана. Патент истёк в 1997 году.
• В 2015 году Уитфилд Диффи и Мартин Хеллман были удостоены премии Тьюринга за вклад в криптографию с открытым ключом.
• Протокол Диффи — Хеллмана часто называют «протоколом Диффи — Хеллмана — Меркля» (DHM), признавая вклад Ральфа Меркля в разработку концепции обмена ключами, хотя его метод (головоломки Меркля) был менее эффективным.

Источники

• Diffie, W., & Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644-654.
• Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
• Schneier, B. (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons.
• Stallings, W. (2017). Cryptography and Network Security: Principles and Practice. Pearson.
• Rescorla, E. (2018). The Transport Layer Security (TLS) Protocol Version 1.3. RFC 8446.
• Williamson, M. J. (1974). Non-secret encryption using a finite field. Communications-Electronics Security Group (CESG).