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

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

История

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

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

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

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

Вклад Ральфа Меркла

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

Последующее развитие

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

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

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

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

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

Безопасность протокола Диффи-Хеллмана опирается на вычислительную сложность задачи дискретного логарифмирования. Для простого числа \(p\) и целого числа \(g\) (первообразный корень по модулю \(p\)) задача заключается в нахождении такого числа \(x\), что \(g^x \equiv y \pmod{p}\), где \(y\) — известное значение. Для больших \(p\) (порядка 2048 бит и более) эта задача считается вычислительно неразрешимой при современном уровне развития вычислительной техники.

Эллиптические кривые

В варианте протокола на эллиптических кривых (ECDH) вместо модульной арифметики используется группа точек эллиптической кривой. Односторонней функцией является умножение точки на скаляр: зная точку \(G\) и результат \(Q = kG\), найти \(k\) (задача дискретного логарифмирования на эллиптической кривой) практически невозможно. ECDH обеспечивает эквивалентную стойкость при значительно меньшей длине ключа (например, 256-битный ключ на эллиптической кривой примерно эквивалентен 3072-битному ключу в классическом варианте).

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

Обозначения

• \(p\) — большое простое число (модуль).
• \(g\) — первообразный корень (генератор) по модулю \(p\).
• \(a\) — секретный ключ Алисы (случайное число).
• \(b\) — секретный ключ Боба (случайное число).
• \(A = g^a \mod p\) — открытый ключ Алисы.
• \(B = g^b \mod p\) — открытый ключ Боба.

Шаги протокола

1. Выбор общих параметров. Алиса и Боб заранее договариваются о значениях \(p\) и \(g\). Эти значения могут быть открытыми и известны всем, включая злоумышленника.
2. Генерация секретных ключей. Алиса выбирает случайное число \(a\) (секретный ключ), Боб выбирает случайное число \(b\).
3. Вычисление открытых ключей. Алиса вычисляет \(A = g^a \mod p\) и отправляет его Бобу. Боб вычисляет \(B = g^b \mod p\) и отправляет его Алисе.
4. Вычисление общего секрета. Алиса, получив \(B\), вычисляет \(K = B^a \mod p\). Боб, получив \(A\), вычисляет \(K = A^b \mod p\).
5. Результат. В силу свойств модульной арифметики \(K = g^{ab} \mod p\) — общий секретный ключ, который теперь могут использовать обе стороны для симметричного шифрования.

Почему злоумышленник не может вычислить ключ

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

Разновидности протокола

Статический (долговременный) Диффи-Хеллман

В этом варианте каждая сторона имеет фиксированную пару ключей (секретный и открытый), которая используется многократно. Открытые ключи могут быть опубликованы в сертификатах. Этот подход удобен для аутентификации, но уязвим к атаке «человек посередине» (Man-in-the-Middle, MITM), если не используется дополнительная аутентификация.

Эфемерный (сеансовый) Диффи-Хеллман (DHE, ECDHE)

В этом варианте для каждого сеанса связи генерируются новые, временные секретные ключи. После завершения сеанса эти ключи уничтожаются. Эфемерный вариант обеспечивает свойство Perfect Forward Secrecy (PFS) — даже если долговременный секретный ключ одной из сторон будет скомпрометирован, прошлые сеансы связи останутся защищёнными, так как их ключи были сгенерированы независимо и не хранятся. Протоколы TLS и SSH используют именно эфемерный вариант (DHE или ECDHE).

Многосторонний Диффи-Хеллман

Протокол может быть обобщён на случай трёх и более сторон. Например, для трёх участников (Алиса, Боб, Чарли) общий секрет вычисляется как \(g^{abc} \mod p\). Однако для большого числа участников схема становится громоздкой, и на практике чаще используются другие методы группового распределения ключей.

Применение

Протокол TLS (Transport Layer Security)

Протокол Диффи-Хеллмана (в эфемерном варианте ECDHE) является основным механизмом для установления общего секретного ключа при соединении по HTTPS. Он обеспечивает защиту веб-трафика, онлайн-банкинга, электронной почты и других интернет-сервисов.

SSH (Secure Shell)

Протокол SSH использует Диффи-Хеллмана для установления защищённого канала при удалённом доступе к серверам. Эфемерный вариант (diffie-hellman-group-exchange-sha256) обеспечивает PFS.

IPsec (Internet Protocol Security)

В протоколе IPsec, используемом для защиты VPN-соединений, Диффи-Хеллман применяется на этапе установления соединения (фаза I протокола IKE) для выработки общего ключа.

Протоколы электронной почты

Некоторые реализации PGP (Pretty Good Privacy) и S/MIME используют Диффи-Хеллмана для обмена ключами.

Критика и уязвимости

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

Классический протокол Диффи-Хеллмана не обеспечивает аутентификации сторон. Если злоумышленник (Мэллори) может перехватывать и подменять сообщения, он может установить два отдельных сеанса: один с Алисой, другой с Бобом. В результате Алиса и Боб будут думать, что общаются друг с другом, но на самом деле Мэллори будет читать и модифицировать все сообщения. Для защиты от MITM необходимо использовать аутентификацию (например, цифровые подписи или сертификаты), что реализовано в протоколах TLS, SSH и IPsec.

Слабая генерация простых чисел

Если используемое простое число \(p\) выбрано некачественно (например, является произведением двух простых чисел, что позволяет использовать атаку «золотой решётки»), безопасность протокола может быть нарушена. В 2015 году было показано, что некоторые реализации TLS использовали «слабые» простые числа, которые могли быть скомпрометированы.

Квантовые компьютеры

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

Атаки по побочным каналам

Реализации протокола могут быть уязвимы к атакам, использующим время выполнения операций, потребление энергии или электромагнитное излучение. Для защиты применяются методы «постоянного времени» (constant-time) и другие контрмеры.

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

• Диффи и Хеллман не патентовали свой протокол, так как считали, что криптография должна быть общедоступной. Однако в 1977 году они получили патент на изобретение, который был передан Стэнфордскому университету и затем лицензирован компании RSA Security.
• В 2015 году группа исследователей обнаружила, что некоторые реализации протокола Диффи-Хеллмана в TLS использовали «слабые» простые числа, которые могли быть вычислены с помощью предварительных вычислений. Это привело к уязвимости, известной как Logjam.
• Протокол Диффи-Хеллмана лёг в основу первой в мире системы электронной подписи, разработанной в 1976 году.

Источники

• Diffie, W., & Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644-654.
• Меркл, Р. (1978). Secure communications over insecure channels. Communications of the ACM, 21(4), 294-299.
• Шнайер, Б. (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons.
• Стандарт NIST SP 800-56A: Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography.
• RFC 2631: Diffie-Hellman Key Agreement Method.
• RFC 3526: More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE).