ECDSA или RSA: какой алгоритм подписи и когда выбирать

Два алгоритма, одна задача

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

Практическое следствие того, что трудные задачи разные: атаки на факторизацию масштабируются лучше, чем атаки на дискретный логарифм на эллиптических кривых, поэтому ключи RSA для того же запаса стойкости приходится наращивать гораздо быстрее, чем EC-ключи. Один этот факт объясняет большую часть различий в размерах и производительности, о которых пойдёт речь ниже.

Размер: ключи и подписи при равной стойкости

В сравнении уровней стойкости NIST (см. SP 800-57 Part 1) 256-битный ключ на эллиптической кривой относится к тому же классу стойкости 128 бит, что и 3072-битный модуль RSA:

(*кодирование несжатой / сжатой точки.) На уровне 128 бит — сегодня это минимум для новых систем — подпись ECDSA P-256 занимает 64 байта, а подпись RSA-3072 — 384 байта, открытый ключ при этом меньше примерно в десять раз. Даже широко распространённый (и с меньшим запасом стойкости) RSA-2048 даёт 256-байтные подписи. Там, где важен каждый байт, — сертификаты в TLS-рукопожатии, токены в HTTP-заголовке, транзакции в блокчейне — эллиптические кривые неизменно выигрывают по размеру.

Обратите внимание на два размера подписи ECDSA: 64 байта в формате raw и ~70–72 байта в кодировке DER. У одной и той же математической подписи есть две распространённые кодировки для передачи, и их путаница — одна из самых частых причин ошибок «invalid signature». Этой теме посвящена отдельная статья.

Скорость: асимметрия подписи и проверки

Профили производительности у двух алгоритмов противоположны, и эту асимметрию стоит хорошо усвоить, потому что именно она определяет реальные архитектуры:

• Проверка подписи RSA очень быстрая. Проверить подпись — значит выполнить одно модульное возведение в степень с открытой экспонентой, которая почти всегда равна небольшому числу 65537. Поэтому RSA так долго удерживался в цепочках сертификатов: сертификат подписывают один раз, а проверяют миллиарды раз.
• Создание подписи RSA выполняется медленно, потому что требует возведения в степень с полноразмерной закрытой экспонентой по модулю длиной 2048–4096 бит. Генерация ключей RSA ещё медленнее: нужно найти большие случайные простые числа, а это может занимать заметные доли секунды, причём время непредсказуемо меняется.
• Создание подписи ECDSA выполняется быстро — это одно скалярное умножение в 256-битном поле, обычно в несколько раз, а то и на порядок быстрее подписи RSA-2048, а по сравнению с RSA-3072 разрыв гораздо больше. Генерация EC-ключа практически ничего не стоит (одно скалярное умножение), и это важно для эфемерных ключей и ключей, которые создаются для каждого устройства.
• Проверка подписи ECDSA медленнее, чем проверка RSA (примерно два скалярных умножения), хотя на современном оборудовании она всё равно быстрая в абсолютных величинах.

Разницу в размерах легко увидеть самостоятельно — для этого хватит нескольких строк на Node.js:

import { generateKeyPairSync, sign } from "node:crypto";

const message = Buffer.from("measure me");

const ec = generateKeyPairSync("ec", { namedCurve: "P-256" });
const rsa = generateKeyPairSync("rsa", { modulusLength: 3072 }); // slow: prime search

const ecSig = sign("sha256", message, ec.privateKey);  // DER-encoded by default
const rsaSig = sign("sha256", message, rsa.privateKey);

console.log("ECDSA P-256:", ecSig.length, "bytes"); // ~70-72 (64 raw)
console.log("RSA-3072:  ", rsaSig.length, "bytes"); // 384

Где применяется каждый из них сегодня

• TLS / X.509. Оба алгоритма используются повсюду. Среди действующих сертификатов по-прежнему преобладает RSA, но крупные центры сертификации (CA) выпускают сертификаты ECDSA (P-256, P-384) как стандартный вариант, и с ними рукопожатие заметно сокращается; многие крупные сайты отдают ECDSA, оставляя RSA как запасной вариант. TLS 1.3 изначально поддерживает оба семейства подписей.
• SSH. Экосистема перешла на эллиптические кривые: для новых ключей по умолчанию обычно выбирают Ed25519 (родственную схему подписи на эллиптических кривых, но не ECDSA), часто встречается и ECDSA P-256. Ключи RSA по-прежнему работают, но устаревшая схема подписи ssh-rsa (на основе SHA-1) в последних релизах OpenSSH отключена по умолчанию — ключи RSA должны использовать варианты с SHA-2.
• JWT. RS256 (RSA) — исторически сложившийся вариант по умолчанию в экосистеме поставщиков удостоверений; ES256 (ECDSA P-256) — компактный современный выбор, и его требуют несколько платформ (API токенов Apple, DPoP, большинство учётных данных WebAuthn, то есть ключей доступа). Компромиссы здесь настолько специфичны, что мы написали отдельное руководство: ES256 или RS256 для JWT. Настоящие токены можно разобрать в отладчике JWT.
• Блокчейны. Фактически здесь используется только ECDSA: и Bitcoin, и Ethereum подписывают с помощью ECDSA на кривой secp256k1 (вместе с Taproot в Bitcoin дополнительно появились подписи Schnorr). Из-за размера подписей RSA здесь даже не рассматривают: каждый байт транзакции оплачивается.
• Подпись кода и прошивок. Исторически здесь преобладал RSA, теперь картина всё более смешанная; устройства с ограниченными ресурсами предпочитают ECDSA за маленькие ключи и быструю подпись, которой нужно мало памяти.

Подвох ECDSA: nonce должен быть безупречным

У ECDSA есть эксплуатационное требование, которого у RSA просто нет: каждая подпись расходует новое секретное число k (nonce, одноразовое число), и стойкость схемы зависит от того, уникально ли это число и равномерно ли оно случайно для каждой без исключения подписи. Ошибки здесь не прощаются:

• Если одно и то же k хотя бы раз использовано для двух разных сообщений с одним ключом, закрытый ключ вычисляется по этим двум подписям средствами элементарной алгебры. Именно это произошло в знаменитом инциденте с PlayStation 3 в 2010 году: из-за постоянного nonce был раскрыт ключ подписи консоли.
• Даже частично предсказуемого или слегка смещённого nonce, если наблюдать его во множестве подписей, может хватить, чтобы восстановить ключ методами на основе решёток. Поэтому слабый системный генератор случайных чисел в момент подписи — это риск компрометации ключа, а не просто вопрос качества.

Стандартное решение — детерминированный ECDSA, описанный в RFC 6979: k выводится из закрытого ключа и дайджеста сообщения с помощью HMAC, поэтому одни и те же входные данные всегда дают один и тот же хорошо распределённый nonce, а случайность в момент подписи не нужна. FIPS 186-5 теперь допускает детерминированный ECDSA, и большинство современных библиотек реализуют RFC 6979 или вариант с подстраховкой (hedged): детерминированный вывод с примесью дополнительной энтропии. При выборе библиотеки это одна из первых вещей, которые стоит проверить. RSA, напротив, не требует случайности для каждой подписи в схеме PKCS#1 v1.5, а повтор случайной соли в RSA-PSS не приводит к компрометации ключа.

Постквантовый обратный отсчёт идёт для обоих

Что бы вы ни выбрали, заранее планируйте вывод выбранного алгоритма из обращения. Достаточно большой квантовый компьютер, выполняющий алгоритм Шора, одинаково справляется и с факторизацией, и с дискретным логарифмом на эллиптических кривых — RSA и ECDSA падут вместе. NIST наметил график перехода в NIST IR 8547 (пока это первый публичный проект): классические алгоритмы подписи — ECDSA, EdDSA и RSA — запрещены после 2035 года для федеральных систем при любом наборе параметров. Одна более ранняя веха касается только уровня стойкости 112 бит, что для подписей означает RSA-2048 и P-224: они объявлены устаревшими после 2030 года, т. е. ими ещё можно пользоваться, но с признанным риском. Срок 2030 года не касается P-256, P-384 и RSA-3072 — это различие важно понимать правильно, потому что от него зависит, каким из ваших ключей нужно уделить внимание в первую очередь.

Названные преемники — ML-DSA (на основе решёток, стандартизован в FIPS 204) и SLH-DSA (на основе хеш-функций, FIPS 205), а за ними последует FN-DSA, производный от Falcon. Приготовьтесь к шоку от размеров: подпись ML-DSA-65 занимает около 3,3 КБ — в 50 раз больше подписи P-256, — поэтому работа над протоколами с гибридными и составными сертификатами всё ещё продолжается. Практический вывод на сегодня — не «немедленно внедрить PQC повсюду», а обеспечить криптографическую гибкость: знать все места, где ваши системы создают подписи, сделать выбор алгоритмов настраиваемым и не зашивать в код размеры ключей и подписей.

Так что же выбрать сегодня?

Хотите увидеть разницу на реальных байтах? Сгенерируйте или вставьте подпись в инструмент проверки подписей ECDSA: он сам определяет кривую и кодировку и показывает, что именно проверил.