Подпись Шнорра - Schnorr signature

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

Алгоритм

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

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

Обозначение

В следующих,

Возведение в степень означает повторное применение групповой операции.
Сопоставление означает умножение на множестве классов конгруэнтности или применение групповой операции (если применимо)
Вычитание означает вычитание на множестве групп эквивалентности
${ Displaystyle М ин {0,1 } ^ {*}}$ , набор конечных битовых строк
${ displaystyle s, e, e_ {v} in mathbb {Z} _ {q}}$ , то набор классов сравнения по модулю ${ displaystyle q}$
${ Displaystyle х, к 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 у = г ^ {х}}$ .

Подписание

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

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

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

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

Проверка

Позволять ${ 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, и Эль-Гамаль, повторно используя секретное значение nonce ${ displaystyle k}$ на двух подписях Шнорра разных сообщений позволит наблюдателям восстановить закрытый ключ.^[2] В случае подписей Шнорра это просто требует вычитания ${ displaystyle s}$ значения:

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

.

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

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

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

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

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

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

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

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

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

Примечания

^ ^а ^б ^c ^d Сёрин, Янник (12 января 2012). «О точной безопасности подписей типа Шнорра в модели случайного Oracle» (PDF). Архив криптологии ePrint. Международная ассоциация криптологических исследований. Получено 2014-08-11.
^ ^а ^б https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf
^ Fiat; Шамир (1986). «Как проявить себя: практические решения проблем идентификации и подписи» (PDF). Материалы CRYPTO '86. Конспект лекций по информатике. 263: 186–194. Дои:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0. S2CID 4838652.
^ Шнорр (1989). «Эффективная идентификация и подписи для смарт-карт» (PDF). Материалы CRYPTO '89. Конспект лекций по информатике. 435: 239–252. Дои:10.1007/0-387-34805-0_22. ISBN 978-0-387-97317-3. S2CID 5526090.
^ ^а ^б Невен, Смарт, Варински. «Требования к хеш-функции для подписей Шнорра». IBM Research. Получено 19 июля 2012.CS1 maint: несколько имен: список авторов (связь)

внешняя ссылка

RFC 8235

[:0-1] а ^б ^c ^d Сёрин, Янник (12 января 2012). «О точной безопасности подписей типа Шнорра в модели случайного Oracle» (PDF). Архив криптологии ePrint. Международная ассоциация криптологических исследований. Получено 2014-08-11.

[tibouchi-2] а ^б https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf

[3] Fiat; Шамир (1986). «Как проявить себя: практические решения проблем идентификации и подписи» (PDF). Материалы CRYPTO '86. Конспект лекций по информатике. 263: 186–194. Дои:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0. S2CID 4838652.

[4] Шнорр (1989). «Эффективная идентификация и подписи для смарт-карт» (PDF). Материалы CRYPTO '89. Конспект лекций по информатике. 435: 239–252. Дои:10.1007/0-387-34805-0_22. ISBN 978-0-387-97317-3. S2CID 5526090.

[neven-5] а ^б Невен, Смарт, Варински. «Требования к хеш-функции для подписей Шнорра». IBM Research. Получено 19 июля 2012.CS1 maint: несколько имен: список авторов (связь)

[1]

[2]

[3]

[4]

[5]