Проблемы с детерминированным ECDSA на основе RFC6979 в биткойнах

Генерация случайного числа kна эллиптической кривой имеет решающее значение, и в подписи любой транзакции в биткойнах kдля вычисления точки требуется случайное число k*G. Если это kвыбрано не случайно, происходит мгновенная утечка закрытого ключа.
Поэтому они придумали детерминированную генерацию ECDSA, которая описана в RFC6979 . По сути, они объединяют закрытый ключ с хешированным сообщением, используют функцию HMAC и генерируют псевдослучайный k.
Этот способ кажется простым и легким.

  • Вносит ли это какие-либо накладные расходы?
  • Если да, то можно ли пренебречь этими накладными расходами?

Или вообще есть какие-то неэффективности или проблемы с этим методом, и почему мы все еще видим недетерминированную реализацию ECDSA?

Ответы (1)

Никаких серьезных проблем с эффективностью. Подписание выполняется довольно редко для любого конкретного клиента (обычно всего несколько подписей на транзакцию). Хотя возможно, что для создания kзначения подписывание может занять немного больше времени, это не будет заметно, особенно если учесть, как редко оно используется каким-либо конкретным клиентом. Именно проверка всех подписей является узким местом процессора для проверки блоков в биткойне, потому что все полные узлы должны проверять подписи всех транзакций в сети, а это занимает одинаковое время независимо от того, как kбыл выбран параметр.

Грегори Максвелл прокомментировал использование детерминированных kзначений здесь :

Основными аргументами в большинстве областей против дерандомизации DSA являются соответствие FIPS (не имеет значения для нас) и разумные опасения по поводу рисков использования (менее) проверенной криптографической конструкции. При широко распространенном движении к дерандомизированному DSA эта последняя проблема не так важна.

Новая библиотека libsecp256k1 от Питера Вуилле на самом деле использует детерминированную генерацию файлов k.

Также обратите внимание, что одним из ключевых преимуществ использования этой конструкции является то, что вам не нужно беспокоиться о слабости вашего генератора случайных чисел, используемого в процессе подписания. Например, подписание разных фрагментов данных одним и тем же kзначением мгновенно приведет к утечке вашего закрытого ключа . Аналогичная атака также может быть использована, если PRNG достаточно слаб, чтобы определить взаимосвязь между различными kзначениями, используемыми при подписи одного и того же фрагмента данных. Поскольку kдетерминировано генерируется из данных, которые вы подписываете (и закрытого ключа), эти опасения по поводу PRNG больше не так важны, поскольку вы всегда будете создавать одну и ту же подпись для одного и того же фрагмента данных. Это также упрощает написание модульных тестов ECDSA.

Как вы упомянули, процесс проверки такой же, и добавление пары дополнительных вычислений HMAC на стороне клиента на самом деле не влияет на процесс подписи.
Подписание одних и тех же данных дважды с разными значениями «k» безопасно.
@adaclin Только в том случае, если злоумышленник не может определить связь между двумя используемыми значениями k. Если, например, известно, что один k равен другому плюс один, ваш закрытый ключ мгновенно становится утечкой.
@PieterWuille Спасибо, я обновил свой ответ. Я перепутал атаку «другие данные с одними и теми же данными» с упомянутой здесь атакой с разными данными и одними и теми же данными .
@abeikverdi На самом деле для создания одноразового номера с использованием RFC6979 с SHA256 требуется 22 вызова функции сжатия SHA256, что занимает порядка 10% всего времени подписания.
@PieterWuille Можете ли вы просветить меня? Разве мы не можем просто объединить закрытый ключ и хешированное сообщение в качестве одноразового номера HMAC?
@abeikverdi Прочтите RFC6979 и попробуйте реализовать его, вот увидите.
@PieterWuille Я уже прочитал RFC6979. Хотя никогда не пытался это реализовать. Это 10% накладных расходов, о которых вы говорите, ваш личный опыт? или это научно?
Я проверил это. Не может быть более научным, чем это.
@StephenM347StephenM347 Разве этот RFC 6979 не генерирует одно и то же k дважды? HMAC_DBGA(закрытый ключ d || H(m)) генерирует одно и то же k для одного и того же хешированного сообщения, поскольку закрытый ключ является постоянным. Не так ли? Разве это не проблема?
@abeikverdi, не совсем, именно поэтому это полезно, потому что создает одну и ту же подпись для одних и тех же данных. Он использует один и тот же k только дважды для одного и того же сообщения. Только когда вы подписываете разные данные одним и тем же значением k, происходит утечка вашего закрытого ключа. Использование одного и того же k для тех же данных не дает никакой новой информации.
@StephenM347 StephenM347 данные, на которые вы ссылаетесь, которые представляют собой хешированное сообщение, являются хэшем транзакции?
@abeikverdi, по сути, да, подписываемые данные представляют собой хэш транзакции, очищенной от всех входных данных (другие подписи вы не подписываете). Есть еще один небольшой нюанс, предыдущий scriptPubKey расходуемого вывода вставляется в scriptSig до двойного хеширования SHA256.
@StephenM347 Большое спасибо! Я полностью понял это сейчас!
Проблемы с детерминированным ECDSA на основе RFC6979 в биткойнах
СпросиСетьПолитика конфиденциальности1y, 1v