Протокол Diffie-Hellman

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

История

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

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

Публикация 1976 года

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

Роль Ральфа Меркла

Независимо от Диффи и Хеллмана, Ральф Меркл (Калифорнийский университет в Беркли) в 1974 году предложил концепцию «головоломки Меркла» — протокол распределения ключей, основанный на сложности перебора. Однако его работа была опубликована позже. Диффи и Хеллман признали вклад Меркла, и в некоторых источниках протокол называют «Диффи — Хеллмана — Меркла» (DHM). Тем не менее, исторически закрепилось название «протокол Диффи — Хеллмана».

Современное развитие

Протокол DH лёг в основу многих более сложных криптосистем, включая протоколы TLS (HTTPS), SSH, IPsec, а также алгоритм шифрования Эль-Гамаля. В 2010-х годах были разработаны варианты на основе эллиптических кривых (ECDH), которые обеспечивают ту же стойкость при меньших размерах ключей. В 2020-х годах протокол DH остаётся одним из ключевых элементов современной криптографии, хотя его классическая версия (на основе простых чисел) постепенно вытесняется ECDH из-за соображений производительности.

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

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

Определения

• p — большое простое число (обычно длиной не менее 2048 бит).
• g — первообразный корень (генератор) по модулю p (целое число, меньшее p, такое, что его степени по модулю p порождают все числа от 1 до p-1).
• a — секретный ключ стороны A (случайное целое число, обычно от 1 до p-2).
• b — секретный ключ стороны B (случайное целое число, аналогичное a).
• A = g^a mod p — открытый ключ стороны A.
• B = g^b mod p — открытый ключ стороны B.
• K = (B)^a mod p = (A)^b mod p = g^(ab) mod p — общий секретный ключ.

Сложность

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

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

Базовая версия (две стороны)

1. Выбор параметров: Стороны A и B заранее согласовывают (или одна сторона генерирует и передаёт) два числа: большое простое число p и генератор g. Эти числа могут быть открытыми.
2. Генерация секретов: Каждая сторона генерирует свой секретный случайный ключ: a (для A) и b (для B).
3. Вычисление открытых ключей:

• A вычисляет A = g^a mod p и отправляет B.
• B вычисляет B = g^b mod p и отправляет A.

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

• A получает B и вычисляет K = B^a mod p = g^(ab) mod p.
• B получает A и вычисляет K = A^b mod p = g^(ab) mod p.

1. Результат: Обе стороны получили одинаковое число K, которое может быть использовано как ключ для симметричного шифрования (например, AES).

Многосторонний вариант (групповой DH)

Протокол может быть расширен на любое количество участников. Например, для трёх сторон (A, B, C):

1. A, B, C выбирают p, g.
2. A генерирует a, B — b, C — c.
3. A отправляет B: g^a mod p.
4. B отправляет C: (g^a)^b mod p = g^(ab) mod p.
5. C отправляет A: (g^(ab))^c mod p = g^(abc) mod p.
6. A, B, C вычисляют общий секрет K = g^(abc) mod p.

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

Аутентифицированная версия (ECDH)

Базовая версия DH уязвима для атаки «человек посередине» (MITM), так как не аутентифицирует участников. Для защиты используется аутентифицированный вариант:

• DH с цифровыми подписями (DH-DSS).
• DH с сертификатами (в TLS).
• DH на эллиптических кривых (ECDH), где открытые ключи подписываются.

В аутентифицированном протоколе стороны обмениваются не только открытыми ключами DH, но и подписями к ним, подтверждающими их подлинность. Это предотвращает MITM-атаки.

Классификация и виды

По используемой математической группе

• Дискретно-логарифмический DH (DLP-DH): основан на задаче дискретного логарифмирования в мультипликативной группе поля простого числа (GF(p)). Классическая версия.
• DH на эллиптических кривых (ECDH): основан на задаче дискретного логарифмирования в группе точек эллиптической кривой. Обеспечивает ту же стойкость при меньших размерах ключей (например, 256-битный ключ ECDH эквивалентен 3072-битному DLP-DH).

По способу аутентификации

• Анонимный DH: без аутентификации (только обмен открытыми ключами). Уязвим для MITM.
• Аутентифицированный DH: с использованием сертификатов, подписей или предварительно согласованных секретов.

По режиму использования

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

Применение

Протокол TLS (HTTPS)

Протокол DH (обычно ECDHE) используется в современных версиях TLS для установления общего сеансового ключа между клиентом (браузером) и сервером. Это обеспечивает конфиденциальность и целостность данных в интернете. Использование ECDHE обеспечивает совершенную прямую секретность.

Протокол SSH

Протокол Secure Shell (SSH) использует DH (или ECDH) для установления ключа шифрования при подключении к удалённому серверу. Это позволяет безопасно передавать пароли и команды.

IPsec

В протоколе IPsec (Internet Protocol Security) DH применяется для установления ключей для шифрования трафика между сетевыми устройствами (например, между VPN-концентраторами).

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

В некоторых криптовалютах (например, в протоколах на основе схемы Эль-Гамаля) DH используется для создания общих секретов между участниками транзакций.

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

Протоколы шифрования электронной почты (например, OpenPGP) могут использовать DH для обмена ключами.

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

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

Базовая версия DH не защищена от MITM-атаки. Злоумышленник может перехватить открытые ключи A и B, подменить их на свои, и установить два отдельных сеанса с A и B. В результате злоумышленник будет знать оба общих секрета и сможет расшифровывать и модифицировать сообщения. Защита достигается аутентификацией сторон (сертификаты, подписи).

Атаки на параметры (Small subgroup attack)

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

Атаки на реализацию

• Timing attacks: злоумышленник может измерить время вычисления модульного возведения в степень и восстановить секретный ключ. Защита — использование константного времени выполнения.
• Side-channel attacks: атаки по побочным каналам (электромагнитное излучение, потребление энергии). Требуют физического доступа к устройству.

Атаки на дискретное логарифмирование

Для классического DH (DLP-DH) с ключами длиной 1024 бита и менее существуют эффективные алгоритмы дискретного логарифмирования (например, решето числового поля). Рекомендуемая длина ключа — не менее 2048 бит (для DLP-DH) или 256 бит (для ECDH).

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

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

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

• Протокол был изобретён в 1974 году Ральфом Мерклом, но его работа была опубликована позже, чем статья Диффи и Хеллмана. В 2002 году Меркл получил премию Тьюринга за вклад в криптографию, включая протокол DH.
• В 2015 году исследователи из Университета Джонса Хопкинса показали, что многие реализации DH в TLS использовали слабые случайные числа, что делало возможным восстановление ключей.
• Протокол DH лежит в основе протокола «Эль-Гамаля» для шифрования и цифровых подписей, разработанного Тахером Эль-Гамалем в 1985 году.
• В 2020 году Национальный институт стандартов и технологий США (NIST) рекомендовал прекратить использование 1024-битного DH и перейти на 2048-битный или ECDH.

Источники

• 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». CRC Press.
• Schneier, B. (1996). «Applied Cryptography: Protocols, Algorithms, and Source Code in C». John Wiley & Sons.
• NIST Special Publication 800-56A Rev. 3 (2018). «Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography».
• RFC 2631 (1999). «Diffie-Hellman Key Agreement Method».
• RFC 7748 (2016). «Elliptic Curves for Security».