Обмен ключами Диффи-Хеллмана

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

Definition

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

Scope

Эта тема охватывает протокол обмена ключами Диффи-Хеллмана и проблему дискретного логарифмирования, лежащую в основе его безопасности, вычислительные и десизионные предположения Диффи-Хеллмана, шифрование Эль-Гамаля, построенное на той же структуре, эфемерный обмен ключами для обеспечения прямой секретности, а также угрозу атаки «человек посередине», которая мотивирует аутентификацию. Она исключает RSA (основанный на факторизации) и реализацию Диффи-Хеллмана на эллиптических кривых, которая рассматривается в разделе криптографии на эллиптических кривых.

Core questions

• Как две стороны могут договориться об общем секрете, если перехватчик видит все сообщения?
• Почему проблема дискретного логарифмирования затрудняет восстановление обмениваемого секрета?
• В чем разница между вычислительными и десизионными предположениями Диффи-Хеллмана?
• Как эфемерный Диффи-Хеллман обеспечивает прямую секретность?
• Почему неаутентифицированный Диффи-Хеллман уязвим для атаки «человек посередине»?

Key concepts

• согласование общего секрета
• генератор и циклическая группа
• приватные и публичные экспоненты
• проблема дискретного логарифмирования
• вычислительный Диффи-Хеллман (CDH)
• десизионный Диффи-Хеллман (DDH)
• эфемерный обмен ключами и прямая секретность
• атака «человек посередине»
• шифрование Эль-Гамаля

Key theories

Стойкость дискретного логарифмирования

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

Вычислительные и десизионные предположения Диффи-Хеллмана

Безопасность формализуется с помощью предположения CDH (вычисление общего секрета является сложной задачей) и более сильного предположения DDH (общий секрет неотличим от случайного), последнее лежит в основе доказуемо безопасного шифрования в стиле Эль-Гамаля.

Mechanisms

В циклической группе с публичным генератором g Алиса выбирает секретное значение a и отправляет g^a, Боб выбирает b и отправляет g^b; каждый вычисляет общий секрет g^(ab), возводя полученное значение в свою собственную экспоненту. Перехватчик видит g, g^a и g^b, но должен решить проблему дискретного логарифмирования или проблему Диффи-Хеллмана, чтобы найти g^(ab). Использование свежих (эфемерных) экспонент для каждой сессии обеспечивает прямую секретность: компрометация долгосрочных ключей позднее не раскрывает ключи прошлых сессий.

Clinical relevance

Диффи-Хеллман является основой установления ключей в TLS, IPsec/IKE, SSH, Signal и WireGuard. Эфемерные варианты (DHE и эллиптическая кривая ECDHE) обеспечивают прямую секретность, которая защищает записанный трафик от будущей компрометации ключей. Аутентификация обмена (с помощью сертификатов или подписей) предотвращает атаку «человек посередине», которой подвержен простой Диффи-Хеллман.

Evidence & guidelines

Параметры Диффи-Хеллмана для конечных полей указаны в RFC 7919 (безопасные именованные группы); NIST SP 800-56A стандартизирует установление ключей. Передовая практика использует эфемерные ключи для прямой секретности и хорошо проверенные группы. Атака Logjam (2015) показала, что слабые 512-битные экспортные и повторно используемые 1024-битные группы уязвимы, что привело к переходу на 2048-битные группы или эллиптические кривые.

History

Диффи и Хеллман опубликовали протокол обмена ключами в своей статье 1976 года, которая положила начало криптографии с открытым ключом, основываясь на более ранней идее головоломки Меркла. (Малкольм Уильямсон обнаружил эквивалентный метод в GCHQ в 1974 году.) Эль-Гамаль обобщил эту конструкцию в схему шифрования и подписи с открытым ключом в 1985 году. Протокол перешел от групп конечных полей к эллиптическим кривым и стал стандартным средством установления сессионных ключей в интернете.

Key figures

• Whitfield Diffie
• Martin Hellman
• Ralph Merkle
• Taher ElGamal
• Malcolm Williamson

Seminal works

• diffie1976
• katz2020
• menezes1996

Frequently asked questions

Аутентифицирует ли Диффи-Хеллман стороны сам по себе?

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

Что такое прямая секретность и как Диффи-Хеллман ее обеспечивает?

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