Криптографический алгоритм Диффи — Хеллмана

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

История

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

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

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

Работа Диффи и Хеллмана была новаторской, однако она не содержала полной реализации асимметричного шифрования. Вскоре после этого, в 1977 году, Рональд Ривест, Ади Шамир и Леонард Адлеман разработали алгоритм RSA, который решал задачу шифрования с открытым ключом. Тем не менее, протокол Диффи — Хеллмана остаётся фундаментальным для установления общего секрета. В 2015 году Диффи и Хеллман были удостоены премии Тьюринга за вклад в криптографию.

Предшественники

Позднее выяснилось, что в 1974 году британский криптограф Джеймс Эллис из Центра правительственной связи (GCHQ) независимо сформулировал идею асимметричной криптографии, а его коллега Клиффорд Кокс в 1973 году открыл алгоритм, аналогичный RSA. Однако эти работы были засекречены и не повлияли на открытое развитие криптографии.

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

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

Основные понятия

Циклическая группа — множество элементов с операцией, обладающей свойством замкнутости, ассоциативности, наличия нейтрального элемента и обратного элемента. Для DH используется мультипликативная группа целых чисел по модулю простого числа \( p \).
Первообразный корень (генератор) — элемент \( g \) группы, степени которого \( g^a \) порождают все ненулевые элементы группы.
Дискретное логарифмирование — задача нахождения показателя \( a \) по известным \( g \) и \( g^a \) в группе. Для больших простых чисел эта задача считается вычислительно неразрешимой за полиномиальное время.

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

Пусть Алиса и Боб хотят получить общий секретный ключ \( K \). Они договариваются о публичных параметрах: простом числе \( p \) и генераторе \( g \). Эти параметры могут быть известны всем, включая злоумышленника.

Алиса выбирает случайное секретное число \( a \) (1 < \( a \) < \( p-1 \)), вычисляет \( A = g^a \mod p \) и отправляет \( A \) Бобу.
Боб выбирает случайное секретное число \( b \), вычисляет \( B = g^b \mod p \) и отправляет \( B \) Алисе.
Алиса вычисляет \( K = B^a \mod p = (g^b)^a \mod p = g^{ab} \mod p \).
Боб вычисляет \( K = A^b \mod p = (g^a)^b \mod p = g^{ab} \mod p \).

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

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

Классический протокол Диффи — Хеллмана

Использует мультипликативную группу целых чисел по модулю простого числа \( p \). Размер \( p \) обычно составляет 2048 или 4096 бит для обеспечения безопасности.

Эллиптический вариант (ECDH)

Вместо группы целых чисел по модулю \( p \) используется группа точек на эллиптической кривой. ECDH обеспечивает эквивалентную безопасность при значительно меньших размерах ключей (например, 256-битная эллиптическая кривая даёт защиту, сравнимую с 3072-битным DH). Этот вариант широко применяется в современных протоколах, таких как TLS 1.3.

Анонимный протокол

В базовой версии DH не предусматривает аутентификации сторон, что делает его уязвимым для атаки «человек посередине» (MITM). Для устранения этого недостатка используется аутентифицированный вариант, например, при подписи открытых ключей сертификатами (как в TLS).

Применение

Протокол TLS/SSL

DH и ECDH используются для установления общего секрета при установке HTTPS-соединений. В современных версиях TLS (1.2 и 1.3) применяется эфемерный DH (DHE/ECDHE), где параметры генерируются заново для каждого сеанса, обеспечивая свойство совершенной прямой секретности (PFS): даже при компрометации долговременного ключа сервера прошлые сеансы остаются защищёнными.

VPN и IPsec

Протокол IKE (Internet Key Exchange) в IPsec использует DH для согласования ключей между узлами. Это обеспечивает защиту корпоративных сетей и удалённого доступа.

SSH

Протокол Secure Shell (SSH) применяет DH для аутентификации и установления защищённого канала при удалённом управлении серверами.

Мессенджеры и PGP

В системах сквозного шифрования (например, Signal, WhatsApp) DH используется для генерации сеансовых ключей. В PGP (Pretty Good Privacy) протокол применяется для обмена ключами между пользователями.

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

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

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

Выбор параметров

Использование слабых простых чисел \( p \) (например, 512-битных) делает задачу дискретного логарифмирования разрешимой с помощью современных вычислительных мощностей. Рекомендуется использовать \( p \) размером не менее 2048 бит.

Атаки на эллиптические кривые

Для ECDH существуют атаки, связанные с выбором небезопасных кривых (например, кривых с малым порядком подгруппы). Стандарты, такие как NIST P-256 или Curve25519, прошли тщательный криптоанализ.

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

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

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

В 1997 году правительство Великобритании рассекретило документы, показывающие, что Джеймс Эллис из GCHQ сформулировал концепцию обмена ключами в 1970 году, а Малкольм Уильямсон в 1974 году независимо открыл протокол, идентичный DH. Однако их работа оставалась секретной до 1997 года.
Протокол Диффи — Хеллмана не требует, чтобы стороны когда-либо встречались лично или обменивались ключами по защищённому каналу. Это революционное свойство стало основой для электронной коммерции и безопасного интернета.
В 2015 году в протоколах TLS была обнаружена уязвимость Logjam, позволявшая понижать стойкость DH-обмена до 512-битных ключей, что делало возможным перехват трафика. После этого были ужесточены требования к минимальной длине ключей.

Источники

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.
National Institute of Standards and Technology (NIST). «Recommendation for Key Management» (SP 800-57).
Ellis, J. H. (1997). «The History of Non-Secret Encryption». GCHQ.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →