подпись Шнорра

Схема цифровой подписи

В криптографии подпись Шнорра — это цифровая подпись, созданная с помощью алгоритма подписи Шнорра , описанного Клаусом Шнорром . Это схема цифровой подписи, известная своей простотой, и одна из первых, безопасность которой основана на трудноразрешимости некоторых задач дискретного логарифмирования . Он эффективен и генерирует короткие подписи. ^[1] На него распространяется патент США № 4 995 082 , срок действия которого истек в феврале 2010 года.

Алгоритм

Выбор параметров

• Все пользователи схемы подписи соглашаются на группу , , простого порядка, , с генератором, , в которой задача дискретного журнала считается сложной. Обычно используется группа Шнорра . ${\displaystyle G}$ ${\displaystyle q}$ ${\displaystyle g}$
• Все пользователи согласны с использованием криптографической хеш-функции . ${\displaystyle H:\{0,1\}^{*}\rightarrow \mathbb {Z} _{q}}$

Обозначения

В следующих,

• Возведение в степень означает повторное применение групповой операции.
• Сопоставление означает умножение на наборе классов сравнения или применение групповой операции (если применимо).
• Вычитание означает вычитание на множестве классов сравнения.
• ${\displaystyle M\in \{0,1\}^{*}}$, набор конечных битовых строк
• ${\displaystyle s,e,e_{v}\in \mathbb {Z} _{q}}$, множество классов сравнения по модулю ${\displaystyle q}$
• ${\displaystyle x,k\in \mathbb {Z} _{q}^{\times }}$, мультипликативная группа целых чисел по модулю ${\displaystyle q}$ (для простых чисел , ) ${\displaystyle q}$ ${\displaystyle \mathbb {Z} _{q}^{\times }=\mathbb {Z} _{q}\setminus {\overline {0}}_{q}}$
• ${\displaystyle y,r,r_{v}\in G}$.

Генерация ключей

• Выберите закрытый ключ подписи из разрешенного набора. ${\displaystyle x}$
• Открытый ключ проверки — . ${\displaystyle y=g^{x}}$

Подписание

Чтобы подписать сообщение ,: ${\displaystyle M}$

• Выбирайте рандом из разрешенного набора. ${\displaystyle k}$
• Позволять . ${\displaystyle r=g^{k}}$
• Пусть , где обозначает конкатенацию и представляется в виде битовой строки. ${\displaystyle e=H(r\parallel M)}$ ${\displaystyle \parallel }$ ${\displaystyle r}$
• Позволять . ${\displaystyle s=k-xe}$

Подпись представляет собой пару, . ${\displaystyle (s,e)}$

Обратите внимание, что ; если , то представление подписи может уместиться в 40 байт. ${\displaystyle s,e\in \mathbb {Z} _{q}}$ ${\displaystyle q<2^{160}}$

Проверка

• Позволять ${\displaystyle r_{v}=g^{s}y^{e}}$
• Позволять ${\displaystyle e_{v}=H(r_{v}\parallel M)}$

Если то подпись проверена. ${\displaystyle e_{v}=e}$

Доказательство правильности

Относительно легко увидеть, что если подписанное сообщение равно проверенному сообщению: ${\displaystyle e_{v}=e}$

${\displaystyle r_{v}=g^{s}y^{e}=g^{k-xe}g^{xe}=g^{k}=r}$, и поэтому . ${\displaystyle e_{v}=H(r_{v}\parallel M)=H(r\parallel M)=e}$

Открытые элементы: , , , , , , . Частные элементы: , . ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle q}$ ${\displaystyle y}$ ${\displaystyle s}$ ${\displaystyle e}$ ${\displaystyle r}$ ${\displaystyle k}$ ${\displaystyle x}$

Это показывает только то, что правильно подписанное сообщение будет проверено правильно; для алгоритма безопасной подписи требуются многие другие свойства.

Утечка ключей из-за повторного использования nonce

Как и в случае с тесно связанными алгоритмами подписи DSA , ECDSA и ElGamal , повторное использование секретного значения nonce в двух подписях Шнорра разных сообщений позволит наблюдателям восстановить закрытый ключ. ^[2] В случае подписей Шнорра это просто требует вычитания значений: ${\displaystyle k}$ ${\displaystyle s}$

${\displaystyle s'-s=(k'-k)-x(e'-e)}$.

Если но тогда можно просто изолировать. Фактически, даже небольшие отклонения в значении или частичная утечка могут раскрыть закрытый ключ после сбора достаточного количества подписей и решения проблемы скрытого номера. ^[2] ${\displaystyle k'=k}$ ${\displaystyle e'\neq e}$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle k}$

Аргумент безопасности

Схема подписи была построена путем применения преобразования Фиата–Шамира ^[3] к протоколу идентификации Шнорра. ^{[4] [5]} Следовательно (согласно аргументам Фиата и Шамира), он безопасен, если моделируется как случайный оракул . ${\displaystyle H}$

Его безопасность также можно аргументировать в общей групповой модели , предполагая, что она «устойчива к прообразу со случайным префиксом» и «устойчива к второму прообразу со случайным префиксом». ^[6] В частности, не требуется защита от столкновений . ${\displaystyle H}$ ${\displaystyle H}$

В 2012 году Сёрен ^[1] предоставил точное доказательство схемы подписи Шнорра. В частности, Серен показывает, что доказательство безопасности с использованием леммы о разветвлении является наилучшим возможным результатом для любых схем подписей, основанных на односторонних гомоморфизмах групп, включая подписи типа Шнорра и схемы подписей Гийу – Кискатера. А именно, согласно предположению ROMDL, любая алгебраическая редукция должна терять коэффициент в отношении времени к успеху, где – функция, которая остается близкой к 1, пока « заметно меньше 1», где – вероятность создания ошибка при большинстве запросов к случайному оракулу. ${\displaystyle f({\epsilon }_{F})q_{h}}$ ${\displaystyle f\leq 1}$ ${\displaystyle {\epsilon }_{F}}$ ${\displaystyle {\epsilon }_{F}}$ ${\displaystyle q_{h}}$

Короткие подписи Шнорра

Вышеупомянутый процесс достигает t -битного уровня безопасности с 4 t -битными подписями. Например, для 128-битного уровня безопасности потребуются 512-битные (64-байтовые) подписи. Безопасность ограничена атаками дискретного логарифма на группу, сложность которых равна квадратному корню из размера группы.

В оригинальной статье Шнорра 1991 года было высказано предположение, что, поскольку устойчивость к коллизиям в хеше не требуется, следовательно, более короткие хеш-функции могут быть столь же безопасными, и действительно, недавние разработки предполагают, что t - битный уровень безопасности может быть достигнут с помощью 3 t- битовые подписи. ^[6] Тогда для 128-битного уровня безопасности потребуются только 384-битные (48-байтовые) подписи, и этого можно достичь путем усечения размера e до тех пор, пока он не станет половиной длины битового поля s .

Смотрите также

• ДПО
• ЭдДСА
• Схема подписи Эль-Гамаля

Рекомендации

1. Сёрин, Янник (12 января 2012 г.). «О точной безопасности подписей типа Шнорра в модели случайного оракула». Архив электронной печати по криптологии . Международная ассоциация криптологических исследований . Проверено 06 февраля 2023 г.
2. Тибучи, Мехди (13 ноября 2017 г.). «Атаки на подписи Шнорра с использованием предвзятых одноразовых номеров» (PDF) . Семинар ЕСК . Проверено 06 февраля 2023 г.
3. Фиат, Амос ; Шамир, Ади (1987). «Как проявить себя: практические решения проблем идентификации и подписи». В Эндрю М. Одлизко (ред.). Достижения криптологии . Конференция по теории и применению криптографических методов. Труды КРИПТО'86. Конспекты лекций по информатике. Том. 263. стр. 186–194. дои : 10.1007/3-540-47721-7_12 . ISBN 978-3-540-18047-0. S2CID  4838652.
4. Шнорр, CP (1990). «Эффективная идентификация и подписи для смарт-карт». В Жиле Брассаре (ред.). Достижения криптологии . Конференция по теории и применению криптографических методов. Труды КРИПТО '89. Конспекты лекций по информатике. Том. 435. стр. 239–252. дои : 10.1007/0-387-34805-0_22 . ISBN 978-0-387-97317-3. S2CID  5526090.
5. Шнорр, CP (1991). «Эффективное создание подписей с помощью смарт-карт». Журнал криптологии . 4 (3): 161–174. дои : 10.1007/BF00196725. S2CID  10976365.
6. Невен, Грегори; Умный, Найджел; Варински, Богдан. «Требования к хэш-функции для подписей Шнорра». Исследования IBM . Проверено 19 июля 2012 г.

Внешние ссылки

• RFC 8235
• BIP 340: подписи Шнорра для secp256k1
• Реализация на Python