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

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

История

Протокол Диффи — Хеллмана был впервые опубликован в 1976 году Уитфилдом Диффи и Мартином Хеллманом в статье «New Directions in Cryptography». Он стал первой практической реализацией концепции криптографии с открытым ключом. Однако классическая версия протокола, основанная на задаче дискретного логарифмирования в конечном поле, требовала длинных ключей (например, 2048 бит для стойкости, эквивалентной 128-битному симметричному шифру).

Идея использования эллиптических кривых в криптографии была независимо предложена Нилом Коблицем (1987) и Виктором Миллером (1985). Они показали, что группа точек эллиптической кривой над конечным полем может быть использована для построения криптографических систем, включая аналог протокола Диффи — Хеллмана. Первая стандартизация ECDH произошла в 1999 году в рамках стандарта ANSI X9.63, а затем в IEEE P1363 и NIST SP 800-56A. С 2000-х годов ECDH активно внедряется в Интернет-протоколы, такие как TLS (начиная с версии 1.2) и SSH.

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

Эллиптическая кривая

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

\[ y^2 = x^3 + ax + b \pmod{p}, \]

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

Операция сложения точек

Для двух точек \( P = (x_1, y_1) \) и \( Q = (x_2, y_2) \) на кривой (не равных \( \mathcal{O} \)) их сумма \( R = P + Q \) вычисляется по правилам:

• Если \( P \neq Q \), то наклон прямой \( \lambda = (y_2 - y_1) / (x_2 - x_1) \pmod{p} \);
• Если \( P = Q \), то наклон касательной \( \lambda = (3x_1^2 + a) / (2y_1) \pmod{p} \);
• Затем \( x_3 = \lambda^2 - x_1 - x_2 \pmod{p} \), \( y_3 = \lambda (x_1 - x_3) - y_1 \pmod{p} \).

Точка на бесконечности \( \mathcal{O} \) является нейтральным элементом: \( P + \mathcal{O} = P \).

Скалярное умножение

Скалярное умножение \( kP \) (где \( k \) — целое число, \( P \) — точка) определяется как \( k \)-кратное сложение точки с самой собой: \( kP = P + P + \dots + P \) (k раз). Эта операция вычисляется эффективно с помощью алгоритма «удвоение-сложение» (double-and-add) за \( O(\log k) \) шагов. Обратная задача — нахождение \( k \) по заданным \( P \) и \( kP \) — называется задачей дискретного логарифмирования на эллиптической кривой (ECDLP) и считается вычислительно сложной для правильно выбранных кривых.

Протокол ECDH

Описание

Пусть две стороны, Алиса и Боб, хотят установить общий секретный ключ. Они заранее договариваются о параметрах эллиптической кривой: конечном поле \( \mathbb{F}_p \), коэффициентах \( a \) и \( b \), а также о базовой точке \( G \) на кривой, имеющей большой простой порядок \( n \).

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

• Алиса выбирает случайное число \( d_A \) из интервала \( [1, n-1] \) (закрытый ключ) и вычисляет открытый ключ \( Q_A = d_A G \).
• Боб аналогично выбирает \( d_B \) и вычисляет \( Q_B = d_B G \).

1. Обмен открытыми ключами: Алиса и Боб отправляют друг другу свои открытые ключи \( Q_A \) и \( Q_B \) по открытому каналу.

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

• Алиса вычисляет \( S = d_A Q_B = d_A (d_B G) \).
• Боб вычисляет \( S = d_B Q_A = d_B (d_A G) \).

В силу коммутативности скалярного умножения обе стороны получают одну и ту же точку \( S \). Затем из координат точки \( S \) (обычно из \( x \)-координаты) с помощью хеш-функции извлекается общий секретный ключ для симметричного шифрования.

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

Безопасность ECDH основана на сложности ECDLP. Злоумышленник, перехвативший \( Q_A \) и \( Q_B \), не может вычислить \( d_A \) или \( d_B \) за разумное время, если кривая выбрана корректно (например, без аномалий, с большим простым порядком). Однако протокол уязвим для атаки «человек посередине» (MITM) без аутентификации сторон. Для защиты применяются цифровые подписи или сертификаты.

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

По полю

• ECDH над простым полем \( \mathbb{F}_p \): наиболее распространённый вариант, используемый в стандартах NIST (кривые P-256, P-384, P-521) и в Curve25519.
• ECDH над полем характеристики 2 (\( \mathbb{F}_{2^m} \)): используется в специализированных приложениях, но менее популярен из-за сложности реализации.

По кривой

• Кривые NIST: стандартизированы NIST (P-256, P-384, P-521), широко применяются в TLS и государственных системах США.
• Curve25519: кривая, предложенная Дэниелом Бернштейном (2006), с \( p = 2^{255} - 19 \). Отличается высокой производительностью и устойчивостью к side-channel атакам. Используется в протоколах X25519 (вариант ECDH).
• Curve448: кривая с \( p = 2^{448} - 2^{224} - 1 \), также предложена Бернштейном, обеспечивает более высокий уровень безопасности (224-битный эквивалент).

По протоколу

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

Применение

• TLS/SSL: ECDHE является основным алгоритмом обмена ключами в современных версиях протокола (TLS 1.2, 1.3). Например, в популярных наборах шифров TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256.
• SSH: протокол SSH использует ECDH для установления общего ключа при аутентификации.
• PGP и OpenPGP: ECDH применяется для шифрования сообщений и ключей.
• Мессенджеры: Signal Protocol (используется в WhatsApp, Signal, Telegram) основан на ECDH для генерации сеансовых ключей.
• Криптовалюты: в Bitcoin и Ethereum ECDH не используется напрямую, но применяется для генерации адресов и подписей (ECDSA). Однако в некоторых протоколах, таких как Lightning Network, ECDH применяется для создания каналов.
• VPN: протоколы IPsec и WireGuard используют ECDH для обмена ключами.

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

ECDH обеспечивает существенно меньшие размеры ключей и более высокую скорость вычислений при том же уровне безопасности. Однако оба протокола уязвимы для квантовых компьютеров, что стимулирует разработку постквантовых алгоритмов.

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

• Кривая Curve25519 была разработана так, чтобы избежать уязвимостей, связанных с небезопасными реализациями: она использует только \( x \)-координату точки, что упрощает вычисления и предотвращает side-channel атаки.
• В 2015 году Национальное агентство безопасности США (NSA) рекомендовало переход на кривые P-384 и P-521, но позже появились подозрения, что эти кривые могут содержать скрытые уязвимости (backdoors). Curve25519, будучи открытой и прозрачной, стала альтернативой.
• В России ECDH стандартизирован в ГОСТ Р 34.10-2012 (цифровая подпись) и ГОСТ Р 34.11-2012 (хеш-функция), но для обмена ключами применяется протокол VKO (ГОСТ Р 34.10-2012, раздел 7).

Критика

Основная критика ECDH связана с потенциальной уязвимостью к квантовым атакам. В 1994 году Питер Шор предложил алгоритм, который может решать задачу дискретного логарифмирования на эллиптических кривых за полиномиальное время на квантовом компьютере. Хотя крупные квантовые компьютеры пока не построены, это стимулирует разработку постквантовых криптосистем, таких как CRYSTALS-Kyber (обмен ключами на основе решёток).

Также существуют риски, связанные с неправильной реализацией: например, использование небезопасных кривых (с малым порядком, аномалиями) или отсутствие проверки точек на принадлежность кривой (что может привести к атакам с малым подгруппом). Стандарты, такие как RFC 7748, описывают безопасные кривые и методы их реализации.

Источники

• Diffie, W., Hellman, M. (1976). «New Directions in Cryptography». IEEE Transactions on Information Theory.
• Koblitz, N. (1987). «Elliptic Curve Cryptosystems». Mathematics of Computation.
• Miller, V. (1985). «Use of Elliptic Curves in Cryptography». CRYPTO.
• Bernstein, D. J. (2006). «Curve25519: New Diffie-Hellman Speed Records». PKC 2006.
• NIST SP 800-56A Rev. 3: «Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography».
• RFC 7748: «Elliptic Curves for Security».
• ГОСТ Р 34.10-2012: «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».