Цифровая подпись ECDSA: как устроена и как проверяется

Цифровая подпись ECDSA (Elliptic Curve Digital Signature Algorithm) - это алгоритм электронной подписи, перенесённый из классической схемы DSA в группу точек эллиптической кривой. Он позволяет владельцу приватного ключа подписать сообщение так, что любой обладатель публичного ключа сможет убедиться в авторстве и целостности данных, но не сможет подделать подпись. ECDSA даёт ту же стойкость, что и RSA, при кратно меньшей длине ключа, поэтому он лежит в основе TLS-сертификатов, протокола Bitcoin (кривая secp256k1) и SSH-ключей. В этой статье разберём математику эллиптических кривых под подписью, пошаговую генерацию и проверку пары $(r, s)$, критическую роль случайного nonce $k$, выбор кривой и характерные ошибки, на которых студенты теряют баллы на экзамене по криптографии.

Что такое цифровая подпись ECDSA

Цифровая подпись решает три задачи сразу: подтверждает авторство (аутентификация), гарантирует, что сообщение не изменили (целостность), и не даёт автору отказаться от подписанного (неотказуемость). В отличие от обмена ключами, где стороны вырабатывают общий секрет, подпись асимметрична по ролям: приватным ключом подписывают, а публичным - проверяют.

ECDSA строится на эллиптической кривой над конечным полем. Приватный ключ - это случайное целое число $d$, публичный ключ - точка $Q = dG$, где $G$ - заранее фиксированная базовая точка (генератор) группы. Перейти от $d$ к $Q$ легко, а восстановить $d$ по $Q$ - это задача дискретного логарифма на эллиптической кривой (ECDLP), для которой не известно эффективного алгоритма. Именно на этой односторонности и держится стойкость подписи.

Чтобы увидеть, как из приватного ключа и хэша сообщения рождается конкретная пара чисел $(r, s)$ и как проверяющая сторона подтверждает её, удобно прогнать алгоритм пошагово. Воспользуйтесь конструктором ниже.

Математическая основа: эллиптические кривые

Под подписью лежит эллиптическая кривая в форме Вейерштрасса над конечным полем $\mathbb{F}_p$: $y^2 = x^3 + ax + b \pmod p,$ где коэффициенты $a$, $b$ и простой модуль $p$ заданы стандартом. Точки кривой вместе с «бесконечно удалённой» точкой $\mathcal{O}$ образуют конечную абелеву группу относительно операции сложения точек. Сложение определяется геометрически (через секущую и касательную), но в поле $\mathbb{F}_p$ вычисляется по явным формулам с модульной арифметикой.

Ключевая операция - скалярное умножение точки: $kG = G + G + \dots + G$ ($k$ слагаемых). Его считают быстро методом удвоения-сложения за $O(\log k)$ операций. Обратная задача - найти $k$ по известным $G$ и $kG$ - это и есть ECDLP. Порядок базовой точки обозначают $n$: это наименьшее число, для которого $nG = \mathcal{O}$. Все вычисления показателей в подписи идут по модулю $n$.

Генерация подписи: пара (r, s)

Пусть нужно подписать сообщение $m$ приватным ключом $d$. Алгоритм генерации цифровой подписи ECDSA укладывается в несколько шагов.

1. Вычислить хэш сообщения $e = \text{HASH}(m)$ (например, SHA-256) и взять его как целое число (при необходимости усечь до длины $n$).
2. Сгенерировать криптографически случайный nonce $k$ из диапазона $[1, n-1]$ - свежий для каждой подписи.
3. Вычислить точку $kG = (x_1, y_1)$ и положить $r = x_1 \bmod n$. Если $r = 0$ - выбрать другой $k$.
4. Вычислить $s = k^{-1}(e + r d) \bmod n$. Если $s = 0$ - выбрать другой $k$.
5. Подпись - пара $(r, s)$.

Здесь $k^{-1}$ - это обратный элемент к $k$ по модулю $n$. Приватный ключ $d$ входит в формулу для $s$, поэтому без него вычислить корректную $s$ нельзя, а сам $d$ из подписи извлечь не получается - он «спрятан» под умножением на $r$ и сложением с $e$.

Проверка подписи публичным ключом

Проверяющий знает публичный ключ $Q$, параметры кривой, сообщение $m$ и подпись $(r, s)$. Алгоритм проверки:

1. Убедиться, что $r$ и $s$ лежат в диапазоне $[1, n-1]$ - иначе подпись недействительна.
2. Вычислить хэш $e = \text{HASH}(m)$.
3. Вычислить $w = s^{-1} \bmod n$.
4. Вычислить два коэффициента: $u_1 = e\,w \bmod n$ и $u_2 = r\,w \bmod n$.
5. Вычислить точку $(x_1, y_1) = u_1 G + u_2 Q$.
6. Подпись верна тогда и только тогда, когда $x_1 \bmod n = r$.

Почему это работает? Подставим $Q = dG$ и распишем точку через скаляр при $G$: $u_1 G + u_2 Q = (u_1 + u_2 d) G = (e w + r w d) G = w(e + r d) G.$ Так как $s = k^{-1}(e + rd)$, то $w = s^{-1} = k(e + rd)^{-1}$, и выражение схлопывается: $w(e + rd) G = k G.$ А координата $x$ точки $kG$ как раз и есть $r$ по построению. Совпадение $x_1 \bmod n = r$ доказывает, что подпись сделана владельцем $d$, причём проверяющему сам $d$ не нужен.

Выбор эллиптической кривой

Стойкость ECDSA напрямую зависит от параметров кривой - их не придумывают, а берут из стандартов.

• secp256k1 - кривая $y^2 = x^3 + 7$ над $\mathbb{F}_p$ с особым простым $p$. Используется в Bitcoin и Ethereum; даёт 128-битный уровень стойкости при 256-битном ключе.
• secp256r1 (P-256, NIST) - самая распространённая в TLS и сертификатах кривая, тоже 256 бит и ~128 бит стойкости.
• Ed25519 - формально это EdDSA (схема Эдвардса), не ECDSA, но решает ту же задачу подписи; её часто выбирают за детерминированность и устойчивость к ошибкам реализации.

Общее правило: 256-битная кривая ECDSA по стойкости соответствует примерно 3072-битному ключу RSA. Эта компактность - главное преимущество эллиптической криптографии. Сама идея переноса в группу точек кривой роднит ECDSA с протоколом обмена ключами Диффи-Хеллмана, у которого есть эллиптический вариант ECDH на тех же кривых.

Стойкость и квантовая угроза

Безопасность ECDSA опирается на сложность ECDLP: восстановить приватный $d$ по публичному $Q = dG$ классическими методами (например, $\rho$-методом Полларда) требует порядка $\sqrt{n}$ операций - для 256-битной кривой это около $2^{128}$, что недостижимо. Однако алгоритм Шора на достаточно большом квантовом компьютере решает ECDLP за полиномиальное время, поэтому ECDSA, как и RSA, считается квантово-уязвимым. На смену ему готовят постквантовые схемы подписи - об этом подробнее в материале про квантово-устойчивую криптографию.

Частые ошибки

• Повтор или предсказуемый nonce $k$. Самая опасная ошибка: два сообщения с одним $k$ раскрывают приватный ключ. Решение - использовать детерминированный $k$ по RFC 6979 или криптографически стойкий генератор.
• Путают приватный и публичный ключ. Подписывают приватным $d$, проверяют публичным $Q = dG$. Передавать наружу можно только $Q$.
• Не проверяют диапазон $r$ и $s$. Значения вне $[1, n-1]$ должны отвергаться; иначе возможны атаки на реализацию.
• Подписывают само сообщение вместо его хэша. В формулу для $s$ входит хэш $e = \text{HASH}(m)$, а не сырой текст; длина сообщения произвольна, а $e$ фиксированной длины.
• Берут модуль $n$ и модуль поля $p$ за одно и то же. Координаты точек считаются по модулю $p$, а показатели $k$, $s$, $d$ - по модулю порядка группы $n$; это разные числа.

FAQ

Чем ECDSA отличается от RSA-подписи? RSA-подпись строится на сложности факторизации больших чисел, ECDSA - на сложности дискретного логарифма на эллиптической кривой. При одинаковой стойкости ECDSA использует кратно более короткие ключи (256 бит против 3072 у RSA), поэтому подписи и ключи компактнее, а операции на современных устройствах часто быстрее.

Зачем подпись состоит из двух чисел $(r, s)$? $r$ - это координата $x$ случайной точки $kG$, она «привязывает» подпись к конкретному nonce $k$. $s$ связывает хэш сообщения $e$, приватный ключ $d$ и тот же $k$ в одно соотношение. Проверка восстанавливает точку $kG$ из $(r, s)$, публичного ключа и хэша и сверяет её координату $x$ с $r$.

Можно ли подделать подпись, зная только публичный ключ? Нет. Для корректной $s$ нужен приватный ключ $d$, а вычислить его из публичного $Q = dG$ - это ECDLP, неразрешимая за разумное время для стандартных кривых. Поэтому публичный ключ безопасно распространять открыто.

Коротко

Цифровая подпись ECDSA подписывает хэш сообщения приватным ключом $d$, выдавая пару $(r, s)$, где $r = (kG)_x \bmod n$, а $s = k^{-1}(e + rd) \bmod n$. Проверка восстанавливает точку $u_1 G + u_2 Q = kG$ из публичного ключа и сверяет её $x$-координату с $r$. Стойкость держится на сложности дискретного логарифма на эллиптической кривой, безопасность реализации - на уникальном непредсказуемом nonce $k$ и правильно выбранной стандартной кривой вроде secp256k1.