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

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

Алгоритм [ править ]

Выбор параметров [ править ]

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

Обозначения [ править ]

В дальнейшем

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

Генерация ключей [ править ]

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

Подписание [ править ]

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

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

Подпись - пара, $(s,e)$ .

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

Проверка [ править ]

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

Если $e_{v}=e$ затем подпись проверяется.

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

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

$r_{v}=g^{s}y^{e}=g^{k+xe}g^{-xe}=g^{k}=r$ , и, следовательно, $e_{v}=H(r_{v}\parallel M)=H(r\parallel M)=e$ .

Публичные элементы: $G$ , $g$ , $q$ , $y$ , $s$ , $e$ , $r$ . Частные элементы: $k$ , $x$ .

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

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

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

s'-s=(k'-k)-x(e'-e)

.

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

Аргумент безопасности [ править ]

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

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

[Seurin-1] Jump up to: Перейти обратно: ^а ^б Сёрин, Янник (12 января 2012 г.). «О точной безопасности подписей типа Шнорра в случайной модели Oracle» . Архив электронной печати по криптологии . Международная ассоциация криптологических исследований . Проверено 06 февраля 2023 г.

[Tibouchi-2] Jump up to: Перейти обратно: ^а ^б Тибучи, Мехди (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] Шнорр, КП (1990). «Эффективная идентификация и подписи для смарт-карт». В Жиле Брассаре (ред.). Достижения криптологии . Конференция по теории и применению криптографических методов. Труды КРИПТО '89. Конспекты лекций по информатике. Том. 435. стр. 239–252. дои : 10.1007/0-387-34805-0_22 . ISBN 978-0-387-97317-3 . S2CID 5526090 .

[5] Шнорр, КП (1991). «Эффективное создание подписей с помощью смарт-карт» . Журнал криптологии . 4 (3): 161–174. дои : 10.1007/BF00196725 . S2CID 10976365 .

[Neven-6] Jump up to: Перейти обратно: ^а ^б Невен, Грегори; Умный, Найджел ; Варински, Богдан. «Требования к хэш-функции для подписей Шнорра» . Исследования IBM . Проверено 19 июля 2012 г.

[1]

[2]

[3]

[4]

[5]

[6]