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

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

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

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

• Все пользователи схемы подписи договариваются о группе , простого порядка , с генератором , в которой проблема дискретного журнала считается сложной. Обычно используется группа Шнорра .${\ 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 , повторное использование значения секретного одноразового номера в двух подписях Шнорра разных сообщений позволит наблюдателям восстановить закрытый ключ. ^[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] Следовательно, (согласно аргументам Фиата и Шамира), это безопасно, если моделируется как случайный оракул .${\displaystyle H}$

Его безопасность также может быть аргументирована в рамках общей модели группы при условии, что она «устойчива к случайному префиксу префикса» и «устойчива к случайному префиксу второго преобраза». ^[5] В частности, это не должно быть устойчивым столкновением .${\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}}$

Короткие подписи Шнорра [ править ]

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

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

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

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

Заметки [ править ]

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

• Менезеш, Альфред Дж. И др. (1996), Справочник по прикладной криптографии , CRC Press.
• CP Schnorr (1990), «Эффективная идентификация и подписи для смарт-карт», в G. Brassard, ed. Достижения в криптологии — Crypto '89 , 239–252, Springer-Verlag. Конспект лекций по информатике , № 435
• Клаус-Питер Шнорр (1991), «Эффективное создание подписи с помощью смарт-карт», Journal of Cryptology 4 (3), 161–174 (PS) (PDF) .

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

• RFC 8235