Число, которое никогда не должно повторяться
Подпись ECDSA — это пара целых чисел (r, s). На вход алгоритм подписи получает три значения: закрытый ключ d, хеш сообщения z и новое секретное целое число k — nonce (от англ. «number used once», одноразовое число). Подписант выбирает k из диапазона [1, n−1], где n — порядок базовой точки G кривой, и вычисляет:
R = k * G (a point on the curve)
r = x-coordinate of R mod n
s = k^-1 * (z + r * d) mod n
signature = (r, s)
Посмотрите, откуда берётся каждое из двух значений. В s смешано всё сразу: nonce, хеш и ключ. А r выводится из k и больше ни из чего: это координата x точки kG, функция только от nonce и кривой. Сообщение в него не входит. Закрытый ключ в него не входит.
Вот и вся проблема в одной фразе. У двух подписей, созданных с одним и тем же k, будет одинаковое r, а r публикуется вместе с каждой подписью. Повторный nonce — не скрытый сбой, который ещё нужно обнаружить: он выдаёт себя у всех на виду, в поле, которое читает каждая проверяющая сторона и навсегда сохраняет каждый обозреватель блоков.
Две подписи, две неизвестные
Допустим, подписант использовал одно и то же k и один и тот же ключ d для двух разных сообщений с хешами z1 и z2. У обеих подписей одинаковое r, поэтому имеем:
s1 = k^-1 * (z1 + r * d) mod n
s2 = k^-1 * (z2 + r * d) mod n
Публично известно здесь всё, кроме k и d. Два уравнения, две неизвестные. Умножим обе части каждого уравнения на k, чтобы избавиться от обратного элемента:
k * s1 = z1 + r * d mod n
k * s2 = z2 + r * d mod n
Слагаемое r * d в обеих строках одинаково: оба сообщения подписаны одним и тем же ключом, а один и тот же nonce дал одно и то же r. Вычтем второе уравнение из первого — это слагаемое сократится, и закрытый ключ полностью исчезнет из выкладок:
k * s1 - k * s2 = z1 - z2 mod n
k * (s1 - s2) = z1 - z2 mod n
k = (z1 - z2) * (s1 - s2)^-1 mod n
Так восстанавливается nonce. Если подставить его в любое из уравнений шага 2, получится ключ, поскольку теперь d умножается только на r:
k * s1 = z1 + r * d mod n
r * d = k * s1 - z1 mod n
d = (s1 * k - z1) * r^-1 mod n
Четыре шага, без перебора и без догадок. Цена — два вычисления обратного элемента по модулю и несколько умножений: микросекунды на любой машине, причём по данным, которые уже опубликованы.
Одна практическая тонкость: кодировки не всегда сохраняют в точности то s, которое вычислил подписант. Bitcoin и ряд библиотек приводят подпись к форме low-S: если s попадает в верхнюю половину диапазона, его заменяют на n − s. Это мера против пластичности подписи, предложенная в BIP-62 и закреплённая как правило ретрансляции транзакций в BIP-146; к nonce она отношения не имеет, но пересекается с этой арифметикой. Тогда восстановленное значение может соответствовать −k, а не k, и прежде чем числа сойдутся, нужно определить знак. На сложность это никак не влияет; кодирование подписей подробно разобрано в статье Форматы подписи ECDSA.
Не мысленный эксперимент
Это самый результативный на практике класс сбоев ECDSA, и ни один из этих сбоев не вызван математикой. В каждом случае реализация подставляла nonce, который подставлять было нельзя.
- PlayStation 3, 2010 год. Реализация подписи прошивок у Sony подставляла на место
kконстанту. У всех её подписей было одинаковоеr, и главный ключ подписи консоли вычислялся по любым двум из них. Сбой публично продемонстрировали на 27C3 в докладе Console Hacking 2010. Это самая наглядная иллюстрация из возможных: алгоритм был реализован правильно, за исключением одной переменной, которая так ни разу и не изменилась. - Кошельки на Android, 2013 год. 14 августа 2013 года в Android Developers Blog вышла запись Some SecureRandom Thoughts. Ей предшествовало расследование того, что в записи названо «компрометацией транзакции Bitcoin, из-за которой 11 августа пришлось обновить несколько приложений Bitcoin». Первопричина была в том, что приложения, использующие Java Cryptography Architecture, «могут не получать криптографически стойких значений на устройствах Android из-за неправильной инициализации нижележащего генератора псевдослучайных чисел». Кошельки, работавшие на затронутых устройствах, брали nonce для подписей из генератора, который мог раз за разом запускаться в одном и том же состоянии. В Google выпустили обходное решение
PRNGFixesдля уровней API 16–18 и исправили платформу. Обратите внимание, что именно сломалось: не криптографический код кошелька и не кривая, а примитив операционной системы, на котором стоят они оба. - Более широкий класс: смещённые nonce. Полный повтор — громкий вариант. Тихий вариант — nonce, который всего лишь смещён: несколько бит распределены неравномерно, потому что генератор возвращает значения из слегка неверного диапазона, усекает их или допускает утечку через время выполнения. Простого алгебраического пути здесь нет, но задачу можно переформулировать как поиск короткого вектора в решётке, а с этим справляется редукция решёток. Брайтнер и Хенингер в работе Biased Nonce Sense (Financial Cryptography 2019) применили этот подход к публичным блокчейнам и к результатам сканирования всего интернета и восстановили сотни ключей Bitcoin, а также десятки ключей Ethereum, Ripple, SSH и HTTPS — по nonce, которые ни разу не повторялись, а были лишь неидеальны. Урок из этого жёсткий: «в основном случайный» — это не защита.
Ни в одном из этих случаев не понадобился изъян в ECDSA, и ни один из них не исправить переходом на кривую побольше. Алгоритм требует для каждой подписи идеально равномерно распределённый секрет и не выдаёт никакого предупреждения, если такого секрета не получает.
Что видно в блокчейне сегодня
Повторяющиеся значения r по-прежнему лежат в блокчейне Bitcoin и останутся там навсегда: блокчейны ничего не забывают. Наш инструмент проверки повтора nonce загружает последние транзакции адреса через API mempool.space, извлекает подписи DER из входов, которые тратят средства с этого адреса, и группирует их по паре (открытый ключ, r). Вот что он вернул для адреса 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm 20 августа 2026 года:
address 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm (P2PKH)
transactions returned 50 <- API cap, not the full history
spending from it 30
inputs from address 110
signatures parsed 110 (unattributed 0, taproot 0, unparsed 0)
distinct public keys 1
distinct r values 73 <- 110 signatures, only 73 nonces
repeated-r groups 6
identical duplicates 0
Один ключ, 110 подписей, 73 разных nonce. Вся суть в этой разнице: 43 из 110 подписей входят в группы, где у каждой подписи есть хотя бы одна другая с тем же r, и в каждой из шести групп значения s различаются, а значит, безобидное объяснение (одну и ту же подпись просто продублировали) исключено. Самая большая группа:
r = d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
pubkey = 04dbd0c6...49c5ff (uncompressed)
ad698b53bbba9e7d807559ec7d3a466fccb669dd3659a1604a206eeb9965c527 vin 0 2012-12-21
b4922bc8cc3624487cdcf4b0ed5a98a21a4552a48dfe495490a7443dd546821e vin 0 2012-12-21
8ab813e5a4039eb79484c315e9c0e201c9d80385c3f3650a4c4b974db9172148 vin 0 2012-12-21
0b5315f4d472a22a6937a20a8d44b8e77099f2a951b65c53c9ebf912352504fa vin 0 2012-12-19
952d8301780ca74fca5f6541db44ba49e47e8514dfdef36bc7e3d534085dbbf6 vin 0 2012-12-19
... 5 more, the oldest on 2012-08-16
На двух деталях стоит остановиться. Во-первых, вторая по величине группа — это ещё 10 подписей с другим общим r, и в обеих группах каждая подпись стоит на одном и том же индексе входа своей транзакции (в одной группе на индексе 0, в другой на индексе 1). Так не выглядит случайная коллизия генератора случайных чисел (ГСЧ). Так выглядит генератор, который в начале каждой операции подписи заново инициализируется в одно и то же состояние, а затем продвигается вперёд: входу 0 всегда достаётся первое значение, входу 1 — второе. Во-вторых, повторы идут с августа по декабрь 2012 года — почти за год до публичного раскрытия проблемы SecureRandom в Android. Этот класс дефектов уже встречался в реальных системах, когда у него ещё не было публичного названия; это напоминание о том, что такие объявления отмечают момент, когда проблему заметили, а не когда она возникла.
Решение: перестать бросать кости
Надёжное решение не в том, чтобы «взять генератор случайных чисел получше». Оно в том, чтобы полностью убрать генератор случайных чисел из процесса подписи.
RFC 6979, детерминированный ECDSA. Вместо того чтобы выбирать k случайно, его выводят: детерминированный генератор случайных битов на основе HMAC (HMAC-DRBG) инициализируют закрытым ключом и хешем сообщения и берут k из его выхода, а если значение выпадает из диапазона [1, n−1], генерируют заново. Результат выглядит равномерно распределённым, без ключа непредсказуем и, что важнее всего, определяется сообщением. Другое сообщение неизбежно даёт другое k, поэтому случайный повтор становится невозможным по построению, а не просто маловероятным. Если подписать одно и то же сообщение дважды, получатся одни и те же байты: это безвредно и заодно удобно для тестов. Источник энтропии при подписи вообще не используется, поэтому неисправный источник вам не навредит. FIPS 186-5 допускает детерминированный ECDSA наряду с рандомизированным.
RFC 8032, EdDSA. Ed25519 и Ed448 делают ту же идею обязательной, встраивая её в саму схему: секрет для каждой подписи получают хешированием префикса, выведенного из ключа, вместе с сообщением, и в API нет ни одной точки, через которую разработчик реализации мог бы подставить случайное значение. Если вы выбираете схему, а не получаете её в наследство, EdDSA исключает такой сбой по построению. Подписи Taproot в Bitcoin следуют той же философии: BIP-340 предписывает детерминированный вывод nonce с необязательными вспомогательными случайными данными.
Подписи с подмешанной случайностью (hedged). У чистой детерминированности есть один компромисс, о котором стоит знать: сбой, вызванный во время подписи (например, сбой тактового сигнала или напряжения питания смарт-карты), может заставить детерминированного подписанта выдать две разные подписи одного и того же сообщения с одним и тем же выведенным k, а это снова условие повторного nonce. RFC 6979 предусматривает такой случай в § 3.6. Подход с подмешиванием добавляет свежие случайные данные в детерминированный вывод, а не заменяет его ими, и nonce остаётся безопасным, если исправен либо вывод, либо ГСЧ. Так подписывает crypto/ecdsa в Go; в @noble/curves этот режим доступен через параметр extraEntropy; вспомогательные случайные данные в BIP-340 — та же идея.
Как ведут себя распространённые библиотеки по умолчанию:
| Библиотека | Детерминированный nonce по умолчанию? | Подробности |
|---|---|---|
| libsecp256k1 (Bitcoin Core) | Да — RFC 6979 | При необходимости можно передать другую функцию генерации nonce. |
@noble/curves | Да — RFC 6979 | Режим с подмешанной случайностью включается через extraEntropy. |
| Rust p256 / k256 (RustCrypto) | Да — RFC 6979 | Один и тот же ключ и одно и то же сообщение всегда дают одни и те же байты; рандомизированный вариант включается явно. |
| Go crypto/ecdsa | С подмешанной случайностью, не RFC 6979 | Выводит nonce из ключа, сообщения и свежих случайных данных вместе, поэтому байты при каждом запуске разные и зафиксировать их в тестах нельзя. |
| Python ecdsa (на чистом Python) | Включается явно | Детерминированная подпись — отдельный метод; обычный вызов sign() использует случайные данные. |
| Python cryptography (pyca) | Включается явно | Свежие релизы принимают флаг детерминированной подписи, и для этого режима нужна свежая версия OpenSSL, на которой работает библиотека. |
| OpenSSL CLI | Включается явно (с версии 3.2) | Параметр подписи nonce-type:1 с явно заданным дайджестом: pkeyutl -sign -pkeyopt nonce-type:1 -pkeyopt digest:sha256 или dgst -sha256 -sign key.pem -sigopt nonce-type:1. |
| Node.js node:crypto | Нет — случайный nonce | Один и тот же ключ и одно и то же сообщение при каждом вызове дают разные байты подписи. |
| WebCrypto (crypto.subtle) | Нет — случайный nonce | Передать собственный nonce через этот API тоже нельзя. |
| Java JCA (SunEC) | Нет — случайный nonce | Детерминированный ECDSA становится доступен, если подключить провайдер, например Bouncy Castle. |
| PHP openssl_* / Ruby OpenSSL | Нет — случайный nonce | Ни одна из них не предлагает детерминированного режима. |
Ответ «Нет» в этой таблице не означает, что в библиотеке есть ошибка. Случайный nonce из исправного CSPRNG операционной системы — полностью соответствующий стандарту способ подписи, и именно его предписывают все редакции FIPS 186; FIPS 186-5, вышедший в 2023 году, добавил наряду с ним детерминированный вариант. Столбец показывает зависимость, а не корректность: в строках с «Нет» безопасность вашего закрытого ключа зависит от источника энтропии в момент подписи, а в строках с «Да» — не зависит. Важно ли это, зависит от вашего окружения: для защищённого сервера риск совсем иной, чем для только что загрузившегося встраиваемого устройства, клонированного образа виртуальной машины или телефона 2013 года. Шпаргалка по совместимости библиотек показывает это и другие различия в поведении по умолчанию рядом друг с другом.
Что делать на практике
- Никогда не передавайте собственное
k. Если API подписи принимает параметр nonce, считайте его не возможностью, а способом выстрелить себе в ногу, и никогда не используйте его только потому, что тесту понадобились воспроизводимые байты. Детерминированная подпись уже даёт их, причём безопасно. - Никогда не пишите генератор сами. «Мы инициализируем его меткой времени и идентификатором запроса» — именно так и начинаются такие инциденты. Используйте CSPRNG платформы или библиотеку, которой он не нужен.
- Проверьте, какую стратегию выбора nonce вы используете на самом деле. Тест из двух строк скажет почти всё, но читайте результат внимательно, потому что отличить случайный nonce от nonce с подмешанной случайностью он не может:
import { generateKeyPairSync, sign } from "node:crypto";
const { privateKey } = generateKeyPairSync("ec", { namedCurve: "P-256" });
const msg = Buffer.from("same message, twice");
const a = sign("sha256", msg, privateKey);
const b = sign("sha256", msg, privateKey);
console.log(a.equals(b));
// false in node:crypto -> random or hedged nonce
// true -> deterministic derivation (RFC 6979 or EdDSA-style)
Если байты различаются, вы так и не узнали, чисто случайный у вас nonce или с подмешанной случайностью: это можно выяснить только из документации библиотеки. Если совпадают, убедитесь, что это RFC 6979, а не что-то самодельное: сверьте результат с эталонными тестовыми векторами из RFC 6979, приложение A.2. Наш генератор тестовых векторов ECDSA создаёт подписи RFC 6979 для P-256, P-384, P-521 и secp256k1 из seed, так что позже те же векторы можно воспроизвести байт в байт.
- С подозрением относитесь к моментам с низкой энтропией. Случайный nonce вероятнее всего подведёт при первой загрузке встраиваемого устройства, в виртуальных машинах и контейнерах, восстановленных из общего снимка, и на ранней стадии инициализации, пока пул энтропии ещё не получил начальное значение. Детерминированная подпись снимает этот вопрос.
- Если вы нашли повтор, ключ потерян. Не ослаблен, а потерян, причём задним числом, для любого, кто хоть раз видел эти две подписи. Переведите средства, смените ключ везде, где он используется, и считайте, что любую подпись, когда-либо сделанную этим ключом, мог поставить кто-то другой.
Первоисточники
- RFC 6979 — «Детерминированное использование DSA и ECDSA». Вывод через HMAC-DRBG, обоснование и эталонные тестовые векторы в приложении A; оговорка об атаках с внесением сбоев — в § 3.6.
- RFC 8032 — EdDSA (Ed25519, Ed448), где детерминированный вывод nonce входит в саму схему, а не включается по желанию.
- FIPS 186-5 — действующий стандарт цифровой подписи (Digital Signature Standard): он описывает ECDSA и допускает детерминированную генерацию nonce.
- Some SecureRandom Thoughts — Android Developers Blog, 14 августа 2013 года: дефект инициализации генератора псевдослучайных чисел платформы, его связь с компрометацией кошельков Bitcoin и обходное решение
PRNGFixes. - Biased Nonce Sense — Брайтнер и Хенингер, IACR ePrint 2019/023 / Financial Cryptography 2019: решёточные атаки на всего лишь смещённые nonce, проверенные на реальных данных блокчейнов и сканирования всего интернета.
- Console Hacking 2010 — 27C3, публичная демонстрация сбоя PlayStation 3 с постоянным nonce.
- BIP-62 и BIP-146 — канонизация low-S (мера против пластичности, а не против повтора nonce, но именно из-за неё восстановленным значениям может понадобиться поправка знака), а также BIP-340 об обязательном детерминированном nonce в Taproot.
- libsecp256k1 и @noble/curves — две реализации, которые прошли множество аудитов и по умолчанию используют RFC 6979; их исходный код — самая понятная документация того, как должен выглядеть вывод nonce.
Почему это требование к nonce даёт RSA одно из немногих реальных эксплуатационных преимуществ, которые у него ещё остаются, и как два алгоритма соотносятся в остальном, разобрано в статье ECDSA или RSA.