Основы подписи Шнорра
Объяснение подписей Шнорра с помощью упрощенной математики.
Опубликовано 3 января, 2022 года, автором – Калли Розенбаум.
С тегами: Шнорр, Подпись, BIP340.
Статья впервые появилась на popeller.io
Оригинал статьи здесь.
Если у вас имеются проблемы с пониманием подписей Шнорра, просто помните, вы не одни. В этой статье, я попытаюсь объяснить подписи Шнорра на приемлемом для себя уровне, и конечно же надеюсь, что и вы, почерпнете для себя что-то ценное.
Что за Шнорр?
Шнорр - это такие новые подписи в Биткоине, которые были активированы в недавнем Тапрут-обновлении. Шнорр имеет ряд крутых свойств, которые находятся в самой документации (BIP340), но естественно, я не собираюсь пересказывать это всё.
Подпись и проверка
Схема подписи состоит из двух действий – подписывания и проверки, как показано на следующей схеме.
Левая часть: идёт подписывание сообщения при помощи приватного ключа.
Правая часть: проверка того, что сообщение (изображение кота) было подписано правильным приватным ключом.
Подписант имеет приватный ключ и сообщение для подписи(как например: Биткоин-транзакция или картинка кота.) и производит саму подпись.
У самого же проверяющего имеется публичный ключ, соответствующий приватному ключу, который использовал подписант – сообщение и подпись.
Процесс проверки позволяет убедиться в том, что подпись была создана с помощью правильного приватного ключа, без знания приватного ключа.
Если вы хотите изучать эту тему более детальнее, можете посетить вторую половину главы 2, в книге “Изобретая Биткоин”.
Сторона подписанта
Теперь давайте посмотрим как подписи Шнорра вообще создаются. Они представляют собой левую часть приведенной выше диаграммы. Также, я подразумеваю, что вы уже знакомы с тем, как пара-ключей создается, используя генератор псевдослучайных чисел, а также с принципами работы эллиптических кривых. Если нет, Я всё же рекомендую прочитать раздел 4.8, в книге “Изобретая Биткоин”.
Предположим, что вы хотите сделать подпись для картинки того самого кота.
Сама картинка – это сообщение m, для подписи.
Ваш приватный ключ – это p, который принадлежит вашему публичному ключу P.
Для старта возьмём одноразовое случайное число r, которое можно использовать как закрытый ключ, то есть можно сгенерировать соответствующий публичный ключ, умножив его на G, публично известную точку генерации эллиптической кривой.
На этом этапе, вы имеете следующее:
R – это ваше криптографическое обязательство, которое станет первой частью окончательной подписи , а r должно оставаться секретным и не использоваться повторно. Это будет объяснено чуть позже.
Вы подготовили всё что необходимо для создания вашей подписи. Вы следуете следующим 2 шагам.
Первый шаг – заключается в расчёте предварительного секрета для хеширования, e:
Хеш-загадка – это результат хеширования строки, что получается в результате склеивания R, P, m.
Эти компоненты будут абсолютно доступны у проверяющего. Используя “секрет хеша”, вы можете приступить ко второму шагу:
Вычислить вызов-отклик или просто ответ, s, который является второй частью подписи (Спасибо Антони Тауну, Рубену Сомсену и @nothingmuch в Твиттере, за их помощь со словом response).
вы отправляете картинку кота, m, и также свою подпись (R,s) вашему другу, Фреду.
Сторона проверяющего
Фред хочет убедиться что картинка с котиком, не была скомпрометирована во время передачи, и что она действительно пришла от Вас, единственного, у которого есть доступ к своему приватному ключу p.
Фред имеет доступ к P, m, R и s. Конечно, он также знает G, потому что это одна из известных констант. На основе этой информации он может вычислить хеш-загадку и убедиться, что проверочное уравнение соблюдается.
Если это уравнение соблюдается, Фред может быть уверен что это подпись была сделана с помощью p.
Заметьте, что уравнение (2) получается из уравнения отклика путём перемножения обеих сторон на G. Начиная с уравнения отклика, мы получаем:
Как вы можете видеть: Если уравнение отклика соблюдается, то выполняется и уравнение проверки. Аналогично, если уравнение проверки выполняется, то выполняется и уравнение ответа. Таким образом, когда Фред проверяет уравнение для точек эллиптической кривой, он также косвенно проверяет и уравнение-ответ на скалярах.
Когда Фред проверит подпись, он сможет насладиться фотографией кота, полностью уверенный в том, что это действительно та самая фотография, которую вы ему отправили.
Почему r – является секретным?
Вы можете задаться вопросом, почему nonce должен храниться в секрете. Вы даже можете задаться вопросом, зачем он вообще нужен? Предлагаю начать с последнего.
И давайте для примера просто уберем r и посмотрим что произойдет.
Вы создаёте подпись следующим образом:
Подпись будет состоять только из s. Фред верифицирует Вашу подпись как:
Это уравнение верно, но оно также позволит Фреду извлечь закрытый ключ p, поскольку он знает и s, и e. Он возьмет уравнение ответа и решит его для p:
Это понятно что нам требуется nonce, дабы Фред не смог вычислить ваш приватный ключ, но почему мы должны держать наш nonce в секрете? Почему вообще нужно заморачиваться с производным комитментом, а не использовать одноразовое число напрямую?
Это происходит по той же причине. Предположим что если бы nonce, r, был свободно предоставлен Фреду, то он мог бы вычислить p следующим образом:
И Фред смог бы вычислить p путём вычитания r от s и также разделить полученный результат на e.
Раскрывая лишь один комитмент, R, Фреду, мы как-бы гарантируем, что Фред не сможет вычислить p, но с другой стороны в это же время, мы позволяем ему убедиться что p было использовано для генерации подписи.
Не используйте повторно nonce.
Но даже если вы держите свой nonce в секрете, существует вероятность что вы можете “слить” ваши приватные ключи, ЕСЛИ вы используете nonce дважды для одного и того же приватного ключа. Давайте предположим что делаете 2 подписи с одним и тем же nonce и приватным ключом следующим образом:
Затем вы даёте подписи (R, s) и (R, s’) самому проверяющему. И проверяющий может с помощью простой арифметики вычислить ваш приватный ключ. Он может составить систему уравнений с двумя уравнениями и двумя неизвестными следующим образом:
Это решаемо для p путём вычитания s’ от s:
Как видите, верификатор сможет извлечь приватный ключ. Урок усвоен: Не используйте nonce повторно.
Если nonce повторно используется, НО для другого приватного ключа, p и p’, уравнение которое представлено выше, уже не будет решаемым, поскольку у Вас уже будет 3 неизвестных значения, p, p’, и r, а уравнений всего два.
Что насчёт хеша-загадки?
Секрет хеша, e, получается через хеширование R||P||m. Почему мы используем именно эту строку как прообраз хеша? Давайте посмотрим на каждые составляющие более подробно.
Сообщение для подписи – m, поэтому это очень важно что m, как-то подтверждается с самой подписью. Если мы уберём m из загадки, “подпись” будет валидна для любых сообщений.
(Спасибо waxwing и AJ Towns за их помощь в этом разделе.)
Чтобы удостовериться, что никто, кроме владельца приватного ключа, не может создать подпись, секрет должен содержать комитмент одноразового кода R. Предположим что challenge не включала nonce commitment, то подпись может быть с лёгкостью быть подделана любым человеком, имеющим доступ к открытому ключу P.
Они могут составить любое произвольное s и сделать следующее:
Последнее уравнение является “уравнением проверки”, но только для R. Правая сторона этого уравнения, содержит только известные ему переменные, s, e, и P. Следовательно подпись (R, s) является валидной.
Когда в строке-загадке находится R, абсолютно не представляется возможным решить данное проверочное уравнение для R потому что R – является частью секрета e. Довольно трудно найти такой R, чтобы было R = sG – H(R||P||m)P.
И давайте уже посмотрим что именно делает P в загадке. Допустим то, что мы не имели P в секрете, e = H(R||m), и та подпись (R, s) – является валидной для публичного ключа P и сообщением m. Затем подпись (R, s’) = (R, s + ex), где x – является производным числом, будет также валидной для публичного ключа P’ = P + xG и сообщение m. Взглянем пожалуй на:
Это известно как “атака по связанным ключам”. Если вы осведомлены о том как расширенные публичные ключи выводятся в стандарте BIP32, то скорее всего, вы увидите потенциальную опасность. Для освежения памяти, есть замечательная иллюстрация.
Получение дочернего расширенного публичного ключа из родительского расширенного публичного ключа, Оранжевые бумажные полоски известны как идентификатор блокчейна, подробно описанный в книге “Изобретая Биткоин” (значение, которое позволяет определить, для какого блокчейна генерируются ключи: регтест, тестовая сеть или основная сеть Биткоина, прим. ред.). Вам просто нужно знать, что это 256-битные числа.
Это означает, что если злоумышленник знает родительский расширенный публичный ключ (xpub) и валидную подпись для дочернего ключа, то он может использовать этот трюк для подделки подписей для родительского xpub, а также для любых дочерних xpub, которые могут быть получены из родительского xpub. Это проблема не только для BIP32, но и для многих схем, использующих сложение публичных ключей, например, Taproot (BIP341). Немного больше подробностей можно найти в разделе Design в BIP340.
В следующем посте я покажу, как подписи Шнорра можно использовать в условиях мультиподписи, чтобы получить подпись, которая выглядит так же, как обычная одиночная подпись. Это довольно-таки практично в Биткоине, поскольку это снижает требования к ресурсам для проверки самого блокчейна.
Ссылка на блог Калле Розенбаум.
Спасибо за комментарии для русского перевода @NCrashed. Редакция и картинки @notgeld.
Поддержите @n1sto
