Алгоритм Диффи-Хеллмана

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

История

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

Принцип работы

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

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

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

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

Безопасность алгоритма Диффи-Хеллмана опирается на две математические проблемы:

• Задача дискретного логарифмирования (DLP): для данного \( g \) и \( g^x \mod p \) вычислить \( x \) при больших \( p \) считается вычислительно сложным.
• Проблема Диффи-Хеллмана (CDH): зная \( g^a \) и \( g^b \), вычислить \( g^{ab} \). Считается, что CDH не легче DLP.

Для практической реализации используются простые числа \( p \) длиной не менее 2048 бит (рекомендация NIST). Генератор \( g \) обычно выбирается равным 2 или 5, но может быть и другим.

Разновидности

Анонимный (классический) Диффи-Хеллман

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

Аутентифицированный Диффи-Хеллман

Для предотвращения атаки «человек посередине» используется цифровая подпись или сертификаты. Примеры:

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

Диффи-Хеллман на эллиптических кривых (ECDH)

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

Эфемерный Диффи-Хеллман (DHE/ECDHE)

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

Применение

Алгоритм Диффи-Хеллмана широко используется в различных протоколах и системах:

• TLS/SSL: для установления защищённого соединения между браузером и сервером (HTTPS).
• SSH: для безопасного удалённого доступа к серверам.
• IPsec: для защиты сетевого трафика на уровне IP.
• VPN: для создания защищённых туннелей.
• Bitcoin и другие криптовалюты: для создания ключей в схемах мультиподписи.
• Мессенджеры: Signal, WhatsApp (продукт Meta, признанной экстремистской и запрещённой в РФ), Telegram (в части протокола MTProto) используют варианты DH для шифрования переписки.

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

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

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

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

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

Слабые параметры

Использование недостаточно больших простых чисел \( p \) или неправильный выбор генератора \( g \) может сделать алгоритм уязвимым. Например, использование \( p \) длиной менее 1024 бит считается небезопасным с 2015 года.

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

• Алгоритм Диффи-Хеллмана стал первым в истории криптографии методом, позволяющим двум сторонам безопасно обменяться ключами без предварительного согласования секрета.
• В 1997 году рассекреченные документы GCHQ показали, что британские криптографы опередили Диффи и Хеллмана на несколько лет, но их работа не была опубликована.
• В 2015 году Уитфилд Диффи и Мартин Хеллман получили премию Тьюринга за «фундаментальный вклад в современную криптографию».
• Алгоритм лёг в основу протокола SSL 3.0 (1996), который впоследствии эволюционировал в TLS.

Источники

• Diffie, W., Hellman, M. E. (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».
• NIST Special Publication 800-56A Rev. 3: «Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography».
• Стинсон, Д. (2003). «Криптография: теория и практика».