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

В криптографии подпись Шнорра представляет собой цифровую подпись, созданную алгоритмом подписи Шнорра, который был описан Клаусом Шнорром. Это схема цифровой подписи, известная своей простотой, одна из первых, безопасность которой основана на неразрешимости некоторых проблем с дискретным логарифмом . Он эффективен и генерирует короткие подписи. Это было покрыто США. Патент 4995082, срок действия которого истек в феврале 2008 года.

• 1 Алгоритм
  • 1.1 Выбор параметров
  • 1.2 Обозначение
  • 1.3 Генерация ключа
  • 1.4 Подписание
  • 1.5 Проверка
  • 1.6 Доказательство правильности
  • 1.7 Утечка ключа при повторном использовании nonce
  • 1.8 Аргумент безопасности
• 2 Короткие подписи Шнорра
• 3 См. Также
• 4 Примечания
• 5 Ссылки
• 6 Внешние ссылки

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

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

Обозначение

Далее

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

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

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

Signing

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

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

Подпись - это пара: $(s,\; e)\; \{\backslash \; displaystyle\; (s,\; e)\}$.

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

Проверка

• Пусть $rv\; =\; gsye\; \{\backslash \; displaystyle\; r\_\; \{v\}\; =\; g\; ^\; \{s\}\; y\; ^\; \{e\}\}$
• Пусть $ev\; =\; H\; (rv\; \parallel \; M)\; \{\backslash \; displaystyle\; e\_\; \{v\}\; =\; H\; (r\_\; \{v\}\; \backslash \; parallel\; M)\}$

Если $ev\; =\; e\; \{\backslash \; displaystyle\; e\_\; \{v\}\; =\; e\}$, то подпись проверено.

Подтверждение правильности

Относительно легко увидеть, что $ev\; =\; e\; \{\backslash \; displaystyle\; e\_\; \{v\}\; =\; e\}$, если подписанное сообщение равно подтвержденное сообщение:

$rv\; =\; gsye\; =\; gk\; -\; xegxe\; =\; gk\; =\; r\; \{\backslash \; displaystyle\; r\_\; \{v\}\; =\; g\; ^\; \{s\}\; y\; ^\; \{e\}\; =\; g\; ^\; \{k-xe\}\; g\; ^\; \{xe\}\; =\; g\; ^\; \{k\}\; =\; r\}$, и, следовательно, $ev\; =\; H\; (rv\; \parallel \; M)\; =\; H\; (r\; \parallel \; M)\; =\; e\; \{\backslash \; displaystyle\; e\_\; \{v\}\; =\; H\; (r\_\; \{v\}\; \backslash \; parallel\; M)\; =\; H\; (r\; \backslash \; parallel\; M)\; =\; e\}$.

общедоступные элементы: $G\; \{\backslash \; displaystyle\; G\}$, $g\; \{\backslash \; displaystyle\; g\}$, $q\; \{\backslash \; displaystyle\; q\}$, $y\; \{\backslash \; displaystyle\; y\}$, $s\; \{\backslash \; displaystyle\; s\}$, $e\; \{\backslash \; displaystyle\; e\}$, $r\; \{\backslash \; displaystyle\; r\}$. Частные элементы: $k\; \{\backslash \; displaystyle\; k\}$, $x\; \{\backslash \; displaystyle\; x\}$.

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

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

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

$s\; \prime \; -\; s\; =\; (k\; \prime \; -\; k)\; -\; x\; (e\; \prime \; -\; e)\; \{\backslash \; displaystyle\; s\text{'}-s\; =\; (k\text{'}-k)\; -x\; (e\text{'}-e)\}$.

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

безопасности

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

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

. В 2012 году Сёрин предоставил точное доказательство схемы подписи Шнорра. В частности, Сёрин показывает, что доказательство безопасности с использованием леммы о разветвлении является наилучшим возможным результатом для любых схем подписей, основанных на односторонних гомоморфизмах группы , включая подписи типа Шнорра и. А именно, согласно предположению ROMDL, любая алгебраическая редукция должна терять множитель $f\; (ϵ\; F)\; qh\; \{\backslash \; displaystyle\; f\; (\{\backslash \; epsilon\}\; \_\; \{F\})\; q\_\; \{h\}\}$в своем отношение времени к успеху, где $f\; \le \; 1\; \{\backslash \; displaystyle\; f\; \backslash \; leq\; 1\}$- функция, которая остается близкой к 1, пока «$ϵ\; F\; \{\backslash \; displaystyle\; \{\backslash \; epsilon\}\; \_\; \{F\}\}$заметно меньше 1 дюйма, где $ϵ\; F\; \{\backslash \; displaystyle\; \{\backslash \; epsilon\}\; \_\; \{F\}\}$- вероятность подделки ошибка делает не более $qh\; \{\backslash \; displaystyle\; q\_\; \{h\}\}$запросов к случайному оракулу.

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

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

• DSA
• EdDSA
• Схема подписи Эль-Гамаля

• Menezes, Alfred J. et al. (1996), Справочник по прикладной криптографии, CRC Press.
• C.P. Шнорр (1990), «Эффективная идентификация и подписи для смарт-карт», в G. Brassard, ed. Достижения в криптологии - Crypto '89, 239-252, Springer-Verlag. Конспект лекций по информатике, номер 435
• Клаус-Питер Шнорр (1991), «Эффективное создание подписи с помощью смарт-карт», Журнал криптологии 4 (3), 161–174 (PS) (PDF).

• RFC 8235