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

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

История

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

Первая реализация протокола Диффи-Хеллмана на эллиптических кривых (ECDH) была предложена в 1990-х годах. В 1999 году ECDH был включён в стандарт ANSI X9.62 (США) для цифровых подписей, а затем в 2000 году — в стандарт IEEE P1363 (США). В 2005 году Национальный институт стандартов и технологий США (NIST) рекомендовал ECDH для использования в правительственных и коммерческих системах. В настоящее время ECDH широко применяется в протоколах TLS (Transport Layer Security), SSH (Secure Shell), IPsec (Internet Protocol Security) и других системах защиты информации.

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

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

Эллиптическая кривая над конечным полем \(F_p\) (где \(p\) — простое число) задаётся уравнением: \[ y^2 = x^3 + ax + b \mod p, \] где \(a, b \in F_p\) и \(4a^3 + 27b^2 \neq 0 \mod p\) (условие отсутствия особых точек). Множество точек \((x, y)\), удовлетворяющих этому уравнению, вместе с бесконечно удалённой точкой \(O\) (нейтральным элементом) образует абелеву группу. Операция сложения точек определяется геометрически (через проведение прямой) и алгебраически (через формулы).

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

Безопасность ECDH основана на вычислительной сложности задачи дискретного логарифмирования на эллиптической кривой (ECDLP). Для заданных точек \(P\) и \(Q = kP\) на кривой (где \(k\) — целое число) задача состоит в нахождении \(k\). На сегодняшний день не известно эффективных алгоритмов решения ECDLP для правильно выбранных кривых. Наиболее известные атаки (например, алгоритм Полларда — \(\rho\)) имеют экспоненциальную сложность, что делает ECDH устойчивым к взлому при достаточной длине ключа.

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

Протокол ECDH работает следующим образом:

1. Выбор параметров: Стороны (Алиса и Боб) договариваются об эллиптической кривой \(E\) над конечным полем \(F_p\) и базовой точке \(G\) на этой кривой. Параметры \((E, p, G)\) являются открытыми.

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

• Алиса выбирает случайное целое число \(a\) (секретный ключ) и вычисляет точку \(A = aG\) (открытый ключ).
• Боб выбирает случайное целое число \(b\) (секретный ключ) и вычисляет точку \(B = bG\) (открытый ключ).

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

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

• Алиса вычисляет точку \(S = aB = a(bG) = abG\).
• Боб вычисляет точку \(S = bA = b(aG) = abG\).

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

Злоумышленник, перехвативший \(A\) и \(B\), не может вычислить \(S\) без знания \(a\) или \(b\), так как это требует решения ECDLP.

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

По типу эллиптической кривой

• Кривые над простыми полями (\(F_p\)): наиболее распространённые, рекомендуемые NIST (например, P-256, P-384, P-521).
• Кривые над полями характеристики 2 (\(F_{2^m}\)): используются в некоторых стандартах (например, K-163, B-163), но менее популярны из-за сложности реализации.
• Кривые Монтгомери (например, Curve25519): оптимизированы для скорости и устойчивости к атакам по сторонним каналам. Используются в протоколе X25519.
• Кривые Эдвардса (например, Ed25519): обеспечивают высокую производительность и простоту реализации.

По способу формирования общего секрета

• Классический ECDH: общий секрет вычисляется как \(x\)-координата точки \(S\).
• X25519: вариант ECDH на кривой Curve25519, где общий секрет вычисляется с использованием только \(x\)-координаты, что исключает необходимость проверки принадлежности точки кривой.

Применение

Протоколы защищённой связи

• TLS: ECDH используется для установления общего сеансового ключа при соединении HTTPS. В версии TLS 1.3 ECDH является обязательным алгоритмом для обмена ключами.
• SSH: применяется для аутентификации и установления защищённого канала.
• IPsec: используется в протоколе IKE (Internet Key Exchange) для согласования ключей.

Криптовалюты и блокчейн

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

Смарт-карты и устройства с ограниченными ресурсами

ECDH широко применяется в смарт-картах, RFID-метках и устройствах Интернета вещей (IoT) благодаря низким вычислительным затратам и малому размеру ключей.

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

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

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

Атаки по сторонним каналам

Реализации ECDH могут быть подвержены атакам по времени, анализу энергопотребления или электромагнитному излучению. Для защиты используются методы маскирования, рандомизации и постоянного времени выполнения.

Выбор кривых

Некоторые кривые, рекомендованные NIST, критикуются за возможное наличие скрытых уязвимостей (например, встроенных «чёрных ходов»). В ответ на это были разработаны кривые с открытыми параметрами, такие как Curve25519 (автор — Дэниел Бернстайн, США).

Проблемы с реализацией

Некорректная реализация ECDH (например, непроверка принадлежности точки кривой) может привести к атакам, таким как атака с использованием малых подгрупп или атака с возвратом к нулю.

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

• ECDH является основой для протокола X25519, который используется в современных версиях TLS и SSH.
• В 2013 году Агентство национальной безопасности США (NSA) было заподозрено во внедрении уязвимости в стандарт NIST P-256, что привело к росту популярности кривых с открытыми параметрами.
• ECDH позволяет достичь 128-битного уровня безопасности при длине ключа 256 бит, тогда как классический DH требует ключа длиной 3072 бита для того же уровня.

Источники

• 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». Advances in Cryptology — CRYPTO '85.
• National Institute of Standards and Technology (NIST). (2005). «Recommendation for Key Management».
• Bernstein, D. J. (2006). «Curve25519: New Diffie-Hellman Speed Records». Public Key Cryptography — PKC 2006.
• IEEE Standard 1363-2000. «Standard Specifications for Public-Key Cryptography».