Протокол Диффи — Хеллмана на эллиптических кривых

Протокол Диффи — Хеллмана на эллиптических кривых (Elliptic Curve Diffie — Hellman, ECDH) — это криптографический протокол, позволяющий двум сторонам, не имеющим предварительно согласованного секрета, установить общий секретный ключ по незащищённому каналу связи. Является вариантом классического протокола Диффи — Хеллмана, в котором вместо мультипликативной группы конечного поля используется группа точек эллиптической кривой над конечным полем. ECDH обеспечивает эквивалентный уровень безопасности при значительно меньшей длине ключа, что делает его основой современных систем асимметричного шифрования, включая TLS, SSH и Signal Protocol.

История

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

Практическая реализация ECDH стала возможной после стандартизации эллиптических кривых Национальным институтом стандартов и технологий США (NIST) в 2000 году (стандарт FIPS 186-2). В 2010-х годах протокол получил широкое распространение в интернет-протоколах: в 2018 году более 80% HTTPS-соединений использовали ECDH для согласования ключей.

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

Эллиптическая кривая над конечным полем

Эллиптическая кривая над конечным полем \( \mathbb{F}_p \) (где \( p \) — простое число, большее 3) задаётся уравнением Вейерштрасса:

\[ y^2 = x^3 + ax + b \mod p, \]

где коэффициенты \( a, b \in \mathbb{F}_p \) удовлетворяют условию \( 4a^3 + 27b^2 \not\equiv 0 \mod p \) (отсутствие сингулярностей). Множество точек кривой \( E(\mathbb{F}_p) \) состоит из всех пар \( (x, y) \), удовлетворяющих уравнению, а также бесконечно удалённой точки \( \mathcal{O} \), играющей роль нейтрального элемента.

Группа точек

На множестве \( E(\mathbb{F}_p) \) определена операция сложения точек, превращающая его в абелеву группу. Правила сложения:

• Для любой точки \( P \): \( P + \mathcal{O} = P \).
• Для точки \( P = (x, y) \) обратная точка \( -P = (x, -y) \).
• Сумма двух точек \( P \) и \( Q \) вычисляется по правилу хорд и касательных: если \( P \neq Q \), проводится прямая через \( P \) и \( Q \); третья точка пересечения с кривой отражается относительно оси \( x \). Если \( P = Q \), используется касательная в точке \( P \).

Порядок группы \( |E(\mathbb{F}_p)| \) приблизительно равен \( p \), но точное значение определяется теоремой Хассе: \( |E(\mathbb{F}_p)| = p + 1 - t \), где \( |t| \leq 2\sqrt{p} \).

Задача дискретного логарифмирования на эллиптической кривой (ECDLP)

Пусть \( G \) — базовая точка кривой простого порядка \( n \). Задача ECDLP состоит в нахождении целого числа \( k \) по известным точкам \( G \) и \( Q = kG \). Стойкость ECDH основана на вычислительной сложности ECDLP: для кривой размера 256 бит решение требует около \( 2^{128} \) операций, что эквивалентно сложности взлома RSA с ключом 3072 бита.

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

Параметры системы

До начала работы стороны договариваются об общих параметрах:

• Простое число \( p \), задающее конечное поле \( \mathbb{F}_p \).
• Коэффициенты \( a \) и \( b \) эллиптической кривой.
• Базовая точка \( G \) порядка \( n \), где \( n \) — простое число.
• Кофактор \( h = |E(\mathbb{F}_p)| / n \) (обычно \( h = 1 \) или малое число).

Эти параметры могут быть взяты из стандартизированных кривых, например, Curve25519 (определена в RFC 7748) или P-256 (NIST).

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

1. Генерация ключей:

• Алиса выбирает случайное секретное число \( a \in [1, n-1] \).
• Вычисляет открытый ключ \( A = aG \) (точка на кривой).
• Боб аналогично выбирает \( b \) и вычисляет \( B = bG \).

1. Обмен открытыми ключами:

• Алиса отправляет Бобу \( A \), Боб отправляет Алисе \( B \). Передача происходит по незащищённому каналу.

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

• Алиса вычисляет \( S = aB = a(bG) \).
• Боб вычисляет \( S = bA = b(aG) \).
• В результате обе стороны получают одну и ту же точку \( S \). Обычно из координат точки \( S \) извлекается \( x \)-координата, которая хешируется для получения симметричного ключа.

Пример на малой кривой

Рассмотрим кривую \( y^2 = x^3 + x + 1 \) над \( \mathbb{F}_{23} \). Пусть базовая точка \( G = (0, 1) \), порядок \( n = 7 \). Алиса выбирает \( a = 2 \), вычисляет \( A = 2G = (5, 19) \). Боб выбирает \( b = 3 \), вычисляет \( B = 3G = (13, 7) \). Общий секрет: \( S = 2B = 3A = 6G = (17, 3) \).

Классификация и варианты

По типу кривой

• Кривые NIST (P-256, P-384, P-521): стандартизированы, широко используются, но критикуются за возможное наличие бэкдоров (параметры получены из SHA-1).
• Curve25519 (X25519): предложена Дэниелом Бернштейном, использует кривую Монтгомери \( y^2 = x^3 + 486662x^2 + x \). Отличается высокой скоростью, защитой от атак по побочным каналам и отсутствием патентных ограничений.
• Curve448 (X448): аналог Curve25519 с 224-битным уровнем безопасности.
• Кривые SM2: китайский стандарт (GB/T 32918), обязателен для использования в государственных системах КНР.

По режиму работы

• Статический ECDH: одна из сторон использует долговременный ключ. Применяется для аутентификации, но не обеспечивает совершенную прямую секретность (PFS).
• Эфемерный ECDH (ECDHE): обе стороны генерируют новые ключи для каждого сеанса. Обеспечивает PFS: компрометация долговременного ключа не раскрывает прошлые сеансы.

Комбинированные протоколы

• ECMQV (Elliptic Curve Menezes-Qu-Vanstone): вариант с взаимной аутентификацией на основе статических и эфемерных ключей.
• X25519Kyber768: гибрид ECDH и постквантового алгоритма CRYSTALS-Kyber, предложенный Google для защиты от квантовых атак.

Применение

Транспортный уровень безопасности (TLS)

Начиная с версии TLS 1.3 (RFC 8446, 2018), ECDHE является обязательным для согласования ключей. При установке HTTPS-соединения клиент и сервер обмениваются эфемерными открытыми ключами на кривых X25519 или P-256. Полученный общий секрет используется для шифрования сеанса.

SSH (Secure Shell)

Протокол SSH-2 поддерживает обмен ключами по ECDH (RFC 5656). Популярные реализации (OpenSSH) по умолчанию используют Curve25519.

Signal Protocol

Мессенджер Signal и его производные (WhatsApp, Facebook Messenger) используют ECDH в комбинации с протоколом X3DH (Extended Triple Diffie-Hellman) для установления асинхронных сеансов с совершенной прямой секретностью.

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

В Bitcoin и Ethereum ECDH не используется напрямую, но применяется алгоритм ECDSA (Elliptic Curve Digital Signature Algorithm), основанный на той же кривой secp256k1. В некоторых блокчейнах (например, Monero) ECDH применяется для создания одноразовых ключей.

Безопасность

Стойкость к атакам

• Атака «человек посередине» (MITM): ECDH без аутентификации уязвим. Злоумышленник может подменить открытые ключи. Для защиты используются цифровые подписи или сертификаты.
• Атаки по побочным каналам: реализация ECDH должна быть защищена от атак по времени выполнения, энергопотреблению и электромагнитному излучению. Curve25519 спроектирована с учётом этих требований.
• Квантовая угроза: алгоритм Шора позволяет решить ECDLP за полиномиальное время на квантовом компьютере. Для защиты разрабатываются постквантовые гибридные схемы.

Критика стандартов NIST

В 2013 году Эдвард Сноуден раскрыл информацию, что АНБ США могло внедрить бэкдоры в генератор случайных чисел Dual_EC_DRBG, связанный с криптографией на эллиптических кривых. Это привело к снижению доверия к кривым NIST и росту популярности Curve25519.

Реализации

ECDH реализован во всех основных криптографических библиотеках:

• OpenSSL: поддерживает кривые NIST, X25519, X448.
• Libsodium: высокоуровневая библиотека с реализацией X25519.
• Bouncy Castle: для Java и C#.
• WolfSSL: для встраиваемых систем.
• Go stdlib: пакет crypto/ecdh.

Перспективы

С развитием квантовых вычислений ECDH постепенно вытесняется гибридными схемами, сочетающими классическую криптографию с постквантовыми алгоритмами. В 2024 году Национальный институт стандартов и технологий США (NIST) начал стандартизацию гибридных механизмов, включая ML-KEM (CRYSTALS-Kyber) в комбинации с ECDH. Тем не менее, на 2025 год ECDH остаётся доминирующим протоколом согласования ключей в интернете.

Источники

• Diffie W., Hellman M. New Directions in Cryptography // IEEE Transactions on Information Theory. — 1976. — Vol. 22, № 6. — P. 644–654.
• Koblitz N. Elliptic Curve Cryptosystems // Mathematics of Computation. — 1987. — Vol. 48, № 177. — P. 203–209.
• Miller V. Use of Elliptic Curves in Cryptography // CRYPTO 1985. — LNCS 218. — Springer, 1986. — P. 417–426.
• National Institute of Standards and Technology. FIPS PUB 186-5: Digital Signature Standard (DSS). — 2023.
• Bernstein D. Curve25519: New Diffie-Hellman Speed Records // PKC 2006. — LNCS 3958. — Springer, 2006. — P. 207–228.
• RFC 7748: Elliptic Curves for Security. — Internet Engineering Task Force, 2016.
• RFC 8446: The Transport Layer Security (TLS) Protocol Version 1.3. — IETF, 2018.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. — Chapter 7.