Алгоритм цифровой подписи на эллиптических кривых

Алгоритм цифровой подписи на эллиптических кривых (Elliptic Curve Digital Signature Algorithm, ECDSA) — это криптографический алгоритм, используемый для создания и проверки электронных цифровых подписей, основанный на математическом аппарате эллиптических кривых над конечными полями. ECDSA является вариантом алгоритма цифровой подписи DSA (Digital Signature Algorithm), адаптированным для использования в группах точек эллиптической кривой, что позволяет достичь эквивалентного уровня безопасности при значительно меньшей длине ключа по сравнению с алгоритмами, основанными на факторизации целых чисел или дискретном логарифмировании в мультипликативных группах полей.

История

Разработка алгоритмов цифровой подписи на эллиптических кривых стала возможной благодаря независимым предложениям Нила Коблица и Виктора Миллера, которые в 1985 году впервые предложили использовать эллиптические кривые для построения криптографических систем. В 1992 году Скотт Ванстон, Скотт Ванстон и Альфред Менезес предложили первый практический протокол цифровой подписи на эллиптических кривых — EC-DSA.

В 1998 году ECDSA был принят в качестве стандарта ANSI X9.62 (США) для финансовой индустрии. В 2000 году алгоритм был включен в стандарт IEEE P1363. В 2005 году Национальный институт стандартов и технологий США (NIST) опубликовал рекомендации по использованию ECDSA в рамках стандарта FIPS 186-2, а затем и в последующих версиях (FIPS 186-3, FIPS 186-4, FIPS 186-5). В России аналогом ECDSA является алгоритм, описанный в ГОСТ Р 34.10-2012 и ГОСТ Р 34.10-2021, который также использует эллиптические кривые, но имеет отличия в параметрах и процедурах.

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

ECDSA базируется на сложности задачи дискретного логарифмирования на эллиптической кривой (ECDLP). Эллиптическая кривая в криптографии задается уравнением вида:

\[ y^2 = x^3 + ax + b \ (\text{mod } p) \]

где \(p\) — большое простое число, а \(a\) и \(b\) — коэффициенты, удовлетворяющие условию \(4a^3 + 27b^2 \neq 0\) (отсутствие сингулярностей). Точки на кривой вместе с бесконечно удаленной точкой (нейтральным элементом) образуют абелеву группу с операцией сложения точек.

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

1. Выбирается эллиптическая кривая \(E\) над конечным полем \(F_p\) и базовая точка \(G\) на ней, имеющая простой порядок \(n\).
2. Генерируется случайное число \(d\) в интервале \([1, n-1]\) — закрытый ключ.
3. Вычисляется открытый ключ \(Q = d \cdot G\) (скалярное умножение точки на число).

Создание подписи

Для подписи сообщения \(m\):

1. Вычисляется хеш-значение \(h = H(m)\), где \(H\) — криптографическая хеш-функция (например, SHA-256).
2. Генерируется случайное число \(k\) в интервале \([1, n-1]\).
3. Вычисляется точка \((x_1, y_1) = k \cdot G\).
4. Вычисляется \(r = x_1 \mod n\). Если \(r = 0\), выбирается другое \(k\).
5. Вычисляется \(s = k^{-1} \cdot (h + r \cdot d) \mod n\). Если \(s = 0\), выбирается другое \(k\).
6. Подпись состоит из пары \((r, s)\).

Проверка подписи

Для проверки подписи \((r, s)\) для сообщения \(m\):

1. Проверяется, что \(r\) и \(s\) находятся в интервале \([1, n-1]\).
2. Вычисляется хеш-значение \(h = H(m)\).
3. Вычисляется \(w = s^{-1} \mod n\).
4. Вычисляется \(u_1 = h \cdot w \mod n\) и \(u_2 = r \cdot w \mod n\).
5. Вычисляется точка \((x_1, y_1) = u_1 \cdot G + u_2 \cdot Q\).
6. Подпись считается верной, если \(x_1 \mod n = r\).

Криптографическая стойкость

Безопасность ECDSA основана на предполагаемой вычислительной сложности решения задачи дискретного логарифмирования на эллиптической кривой. Для достижения уровня безопасности, эквивалентного 128-битному симметричному шифрованию, требуется длина ключа около 256 бит. Для сравнения, алгоритм RSA требует для этого ключа длиной 3072 бита.

Известные атаки

• Атака на генератор случайных чисел: если злоумышленник может предсказать или восстановить значение \(k\) (nonce), он может вычислить закрытый ключ. Именно из-за этой уязвимости в 2010 году была взломана подпись прошивки Sony PlayStation 3, где использовалось фиксированное значение \(k\).
• Атака по сторонним каналам: анализ времени выполнения, энергопотребления или электромагнитного излучения может позволить восстановить закрытый ключ.
• Квантовые атаки: алгоритм Шора теоретически позволяет решать задачу дискретного логарифмирования на эллиптических кривых за полиномиальное время, что делает ECDSA уязвимым перед квантовыми компьютерами достаточной мощности.

Применение

ECDSA широко применяется в различных областях, где требуется аутентификация данных и обеспечение целостности:

• Криптовалюты: Bitcoin, Ethereum и большинство других криптовалют используют ECDSA для подписи транзакций. В Bitcoin используется эллиптическая кривая secp256k1.
• Протоколы TLS/SSL: ECDSA используется для аутентификации серверов и клиентов в защищенных соединениях.
• Электронная подпись: в государственных и коммерческих системах электронного документооборота, в том числе в России по ГОСТ Р 34.10-2012/2021.
• Смарт-карты и аппаратные токены: благодаря малому размеру ключей и высокой производительности ECDSA эффективен для устройств с ограниченными ресурсами.
• Мессенджеры и системы шифрования: Signal, WhatsApp (продукт Meta, признанной экстремистской и запрещённой в РФ) и другие используют ECDSA для аутентификации ключей.

Стандартизация

Международные стандарты

• ANSI X9.62 — стандарт для финансовой индустрии.
• IEEE P1363 — стандарт для криптографических систем на эллиптических кривых.
• FIPS 186-5 — стандарт цифровой подписи США, включающий ECDSA.
• NIST SP 800-186 — рекомендации по выбору эллиптических кривых.

Российские стандарты

• ГОСТ Р 34.10-2012 — «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи». Использует эллиптические кривые, но с отличными от ECDSA параметрами (кривые над полем характеристики 2 и простым полем).
• ГОСТ Р 34.10-2021 — актуализированная версия стандарта, введенная в действие с 1 июня 2022 года.

Критика и ограничения

• Зависимость от качества случайных чисел: как уже отмечалось, уязвимость к атакам на nonce является критической. Для решения этой проблемы применяются детерминированные схемы (RFC 6979), где \(k\) вычисляется на основе закрытого ключа и хеша сообщения.
• Отсутствие доказательства безопасности: в отличие от некоторых других схем (например, схемы Шнорра), ECDSA не имеет строгого доказательства безопасности в стандартной модели.
• Патентные ограничения: в прошлом существовали патентные споры, связанные с использованием ECDSA, однако большинство ключевых патентов на эллиптические кривые истекли к 2010-м годам.

Сравнение с другими алгоритмами

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

• В 2020 году исследователи из компании Kudelski Security обнаружили уязвимость в реализации ECDSA в некоторых аппаратных кошельках для криптовалют, позволяющую восстановить закрытый ключ по неполным данным о nonce.
• Алгоритм ECDSA используется в системе цифровых подписей для программного обеспечения Apple (внутренние компоненты macOS и iOS).
• В 2013 году была опубликована спецификация RFC 6979, описывающая детерминированную версию ECDSA, устраняющую проблему с генерацией случайных чисел.

Источники

• Национальный институт стандартов и технологий США. FIPS 186-5: Digital Signature Standard (DSS). — 2023.
• Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography. — Springer, 2004.
• ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. — М.: Стандартинформ, 2012.
• Pornin T. RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). — IETF, 2013.
• Koblitz N. Elliptic Curve Cryptosystems // Mathematics of Computation. — 1987. — Vol. 48, No. 177. — P. 203–209.