Схема Шнорра

Схема Шнорра (англ. schnorr scheme) — одна из наиболее эффективных и теоретически обоснованных схем аутентификации. Безопасность схемы основывается на трудности вычисления дискретных логарифмов. Предложенная Клаусом Шнорром^[англ.] схема является модификацией схем Эль-Гамаля (1985) и Фиата-Шамира (1986), но имеет меньший размер подписи. Схема Шнорра лежит в основе стандарта Республики Беларусь СТБ 1176.2-99 и южнокорейских стандартов KCDSA и EC-KCDSA. Она была покрыта патентом США 4999082, который истек в феврале 2008 года.

Введение

Схемы аутентификации и электронной подписи — одни из наиболее важных и распространенных типов криптографических протоколов, которые обеспечивают целостность информации.

Понять назначение протоколов аутентификации можно легко на следующем примере. Предположим, что у нас есть информационная система, в которой необходимо разграничить доступ к различным данным. Также в данной системе присутствует администратор, который хранит все идентификаторы пользователей с сопоставленным набором прав, с помощью которого происходит разграничение доступа к ресурсам. Одному пользователю может быть одновременно разрешено читать один файл, изменять второй и в то же время закрыт доступ к третьему. В данном примере под обеспечением целостности информации понимается предотвращение доступа к системе лиц, не являющихся её пользователями, а также предотвращение доступа пользователей к тем ресурсам, на которые у них нет полномочий. Наиболее распространенный метод разграничения доступа, парольная защита, имеет массу недостатков, поэтому перейдем к криптографической постановке задачи.

В протоколе имеются два участника — Алиса, которая хочет подтвердить свой идентификатор, и Боб, который должен проверить это подтверждение. У Алисы имеется два ключа — [math]\displaystyle{ \Kappa _1 }[/math], открытый (общедоступный), и [math]\displaystyle{ \Kappa _2 }[/math] — закрытый (приватный) ключ, известный только Алисе. Фактически, Боб должен проверить, что Алиса знает свой закрытый ключ [math]\displaystyle{ \Kappa _2 }[/math], используя только [math]\displaystyle{ \Kappa _1 }[/math].

Схема Шнорра — одна из наиболее эффективных среди практических протоколов аутентификации, реализующая данную задачу. Она минимизирует зависимость вычислений, необходимых для создания подписи, от сообщения. В этой схеме основные вычисления могут быть сделаны во время простоя процессора, что позволяет увеличить скорость подписания. Как и DSA, схема Шнорра использует подгруппу порядка [math]\displaystyle{ q }[/math] в [math]\displaystyle{ \mathbb{Z}_p^{*} }[/math]. Также данный метод использует хеш-функцию [math]\displaystyle{ h:\{0, 1\}^{*} \to \mathbb{Z}_p }[/math].

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

Генерация ключей для схемы подписи Шнорра происходит так же, как и генерация ключей для DSA, кроме того, что не существует никаких ограничений по размерам. Заметим также, что модуль [math]\displaystyle{ p }[/math] может быть вычислен автономно.

Выбирается простое число [math]\displaystyle{ p }[/math], которое по длине обычно равняется [math]\displaystyle{ 1024 }[/math] битам.
Выбирается другое простое число [math]\displaystyle{ q }[/math] таким, чтобы оно было делителем числа [math]\displaystyle{ p-1 }[/math]. Или другими словами должно выполняться [math]\displaystyle{ p-1\equiv 0\pmod q }[/math]. Размер для числа [math]\displaystyle{ q }[/math] принято выбирать равным [math]\displaystyle{ 160 }[/math] битам.
Выбирается число [math]\displaystyle{ g }[/math], отличное от [math]\displaystyle{ 1 }[/math], такое, что [math]\displaystyle{ g^q\equiv 1\pmod p }[/math].
Пегги выбирает случайное целое число [math]\displaystyle{ w }[/math] меньшее [math]\displaystyle{ q }[/math].
Пегги вычисляет [math]\displaystyle{ y=g^{q-w}\pmod p }[/math].
Общедоступный ключ Пегги — [math]\displaystyle{ (p, q, g, y ) }[/math], секретный ключ Пегги — [math]\displaystyle{ w }[/math].

Протокол проверки подлинности

Алгоритм работы протокола

Предварительная обработка. Алиса выбирает случайное число [math]\displaystyle{ r }[/math], меньшее [math]\displaystyle{ q }[/math], и вычисляет [math]\displaystyle{ x= g^r \pmod p }[/math]. Эти вычисления являются предварительными и могут быть выполнены задолго до появления Боба.
Инициирование. Алиса посылает [math]\displaystyle{ x }[/math] Бобу.
Боб выбирает случайное число [math]\displaystyle{ e }[/math] из диапазона от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ 2^t-1 }[/math] и отправляет его Алисе.
Алиса вычисляет [math]\displaystyle{ s=r+we \pmod q }[/math] и посылает [math]\displaystyle{ s }[/math] Бобу.
Подтверждение. Боб проверяет что [math]\displaystyle{ x=g^sy^e \pmod p }[/math]

Безопасность алгоритма зависит от параметра t. Сложность вскрытия алгоритма примерно равна [math]\displaystyle{ 2^t }[/math]. Шнорр советует использовать t около 72 битов, для [math]\displaystyle{ p \ge 2^{512} }[/math] и [math]\displaystyle{ q \ge 2^{140} }[/math]. Для решения задачи дискретного логарифма, в этом случае, требуется по крайней мере [math]\displaystyle{ 2^{72} }[/math] шагов известных алгоритмов.

Пример

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

Выбирается простое [math]\displaystyle{ p=48731 }[/math] и простое [math]\displaystyle{ q=443 }[/math] ([math]\displaystyle{ q|p-1 }[/math])
Вычисляется [math]\displaystyle{ g }[/math] из условия [math]\displaystyle{ g^q=1 \pmod p }[/math], в данном случае [math]\displaystyle{ g=11444 }[/math]
Алиса выбирает секретный ключ [math]\displaystyle{ w=357 }[/math] и вычисляет открытый [math]\displaystyle{ y=g^{q-w}\pmod p=7355 }[/math] ключ
Алиса отправляет открытый ключ [math]\displaystyle{ (p,q,g,y) }[/math] соответственно равный [math]\displaystyle{ (48731,443,11444,7355) }[/math], закрытый оставляет у себя — [math]\displaystyle{ w=357 }[/math]

Проверка подлинности:

Алиса выбирает случайное число [math]\displaystyle{ r=274 }[/math] и отсылает [math]\displaystyle{ x=g^r \pmod p=37123 }[/math] Бобу.
Боб отсылает Алисе число [math]\displaystyle{ e = 129 }[/math]
Алиса считает [math]\displaystyle{ s=(r+w*e)\pmod q=255 }[/math] и отправляет [math]\displaystyle{ s }[/math] Бобу.
Боб вычисляет [math]\displaystyle{ z=g^s*y^e \pmod p=37123 }[/math] и идентифицирует Алису, так как [math]\displaystyle{ z=x }[/math].

Атаки на Схему

Пассивный противник

Если в схеме Шнорра предположить, что Алиса является противником, то на шаге 1 она может выбрать [math]\displaystyle{ x }[/math] случайным, но эффективным способом. Пусть [math]\displaystyle{ x }[/math] — это переданное Алисой число. Предположим, что можно найти два случайных числа [math]\displaystyle{ e_1 }[/math] и [math]\displaystyle{ e_2 }[/math] такие, что [math]\displaystyle{ e_1 \neq e_2 }[/math] и для каждого из них Алиса может найти соответствующие [math]\displaystyle{ s_1 }[/math] и [math]\displaystyle{ s_2 }[/math], для которых подтверждение даст положительный результат. Получаем:

[math]\displaystyle{ x=g^{s_1}y^{e_1} \bmod p }[/math]

[math]\displaystyle{ x=g^{s_2}y^{e_2} \bmod p }[/math].

Отсюда [math]\displaystyle{ g^{s_1}y^{e_1} = g^{s_2}y^{e_2} \pmod p }[/math] или же [math]\displaystyle{ y^{e_1-e_2} = g^{s_2-s_1} \pmod p }[/math]. Так как [math]\displaystyle{ e_1 \neq e_2 }[/math], то существует [math]\displaystyle{ (e_2-e_1)^{-1} \bmod q }[/math] и, следовательно, [math]\displaystyle{ (s_1-s_2)(e_2-e_1)^{-1} = w \bmod q }[/math], то есть дискретный логарифм [math]\displaystyle{ y }[/math]. Таким образом, либо [math]\displaystyle{ e_1, e_2, e_1 \neq e_2 }[/math] такие, что Алиса может ответить надлежащим образом на оба из них (при одном и том же [math]\displaystyle{ x }[/math]) на шаге 3 протокола, встречаются редко, что означает, что атака Алисы успешна лишь с пренебрежимо малой вероятностью. Либо такие значения попадаются часто, и тогда тот алгоритм, который применяет Алиса, можно использовать для вычисления дискретных логарифмов.

Иными словами, доказано, что в предположении трудности задачи дискретного логарифмирования схема аутентификации Шнорра является стойкой против пассивного противника, то есть корректной.

Активный противник

Активный противник может провести некоторое количество сеансов выполнения протокола в качестве проверяющего с честным доказывающим (или подслушать такие выполнения) и после этого попытаться атаковать схему аутентификации. Для стойкости против активного противника достаточно, чтобы протокол аутентификации был доказательством с нулевым разглашением. Однако свойство нулевого разглашения для схемы Шнорра до сих пор никому доказать не удалось.

Протокол цифровой подписи

Алгоритм Шнорра также можно использовать и в качестве протокола цифровой подписи сообщения [math]\displaystyle{ M }[/math]. Пара ключей используется та же самая, но добавляется однонаправленная хеш-функция [math]\displaystyle{ H(M) }[/math].

Генерация подписи

Предварительная обработка. Пегги выбирает случайное число [math]\displaystyle{ r }[/math], меньшее [math]\displaystyle{ q }[/math], и вычисляет [math]\displaystyle{ x= g^r \pmod p }[/math]. Это стадия предварительных вычислений. Стоит отметить, что для подписи разных сообщений могут использоваться одинаковые открытый и закрытый ключи, в то время как число [math]\displaystyle{ r }[/math] выбирается заново для каждого сообщения.
Пегги объединяет сообщение [math]\displaystyle{ M }[/math] и [math]\displaystyle{ x }[/math] и хеширует результат для получения первой подписи:
[math]\displaystyle{ S_1=H(M | g^r \bmod p) }[/math]
Пегги вычисляет вторую подпись. Необходимо отметить, что вторая подпись вычисляется по модулю [math]\displaystyle{ q }[/math].
[math]\displaystyle{ S_2=r+wS_1 \bmod q }[/math].
Пегги отправляет Виктору сообщение [math]\displaystyle{ M }[/math] и подписи [math]\displaystyle{ S_1 }[/math], [math]\displaystyle{ S_2 }[/math].

Проверка подписи

Виктор вычисляет [math]\displaystyle{ X = g^{S_2}y^{S_1}\bmod p }[/math] (либо [math]\displaystyle{ X = g^{S_2}y^{-S_1}\bmod p }[/math], если вычислять [math]\displaystyle{ y }[/math] как [math]\displaystyle{ y=g^{w}\pmod p }[/math]).
Виктор проверяет, что [math]\displaystyle{ H(M|X)=S_1 }[/math]. Если это так, то он считает подпись верной.

Эффективность

Основные вычисления для генерации подписи производятся на этапе предварительной обработки и на этапе вычисления [math]\displaystyle{ wS_1\bmod q }[/math], где числа [math]\displaystyle{ w }[/math] и [math]\displaystyle{ S_1 }[/math] имеют порядок [math]\displaystyle{ 140 }[/math] битов, а параметр [math]\displaystyle{ r }[/math] — [math]\displaystyle{ 72 }[/math] бита. Последнее умножение ничтожно мало по сравнению с модульным умножением в схеме RSA.

Проверка подписи состоит в основном из расчета [math]\displaystyle{ X = g^{S_2}y^{S_1} }[/math], который может быть сделан в среднем за [math]\displaystyle{ 1.5l + 0.25t }[/math] вычислений по модулю [math]\displaystyle{ p }[/math], где [math]\displaystyle{ l = [log_2q] }[/math] есть длина [math]\displaystyle{ q }[/math] в битах.

Более короткая подпись позволяет сократить количество операций для генерации подписи и верификации: в схеме Шнорра [math]\displaystyle{ O(\log_2q\log_2^2p) }[/math], а в схеме Эль-Гамаля [math]\displaystyle{ O(\log^3p) }[/math].

Пример

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

[math]\displaystyle{ q = 103 }[/math] и [math]\displaystyle{ p = 2267 }[/math]. Причем [math]\displaystyle{ p = 22q + 1 }[/math].
Выбирается [math]\displaystyle{ f=2 }[/math], который является элементом в поле [math]\displaystyle{ Z_{2267*} }[/math]. Тогда [math]\displaystyle{ \frac{p-1}{q} = 22 }[/math] и [math]\displaystyle{ g = 2^{22} \bmod 2267 = 354 }[/math]
Пегги выбирает ключ [math]\displaystyle{ w = 30 }[/math], тогда [math]\displaystyle{ y = 1206 }[/math]
Секретный ключ Пегги — [math]\displaystyle{ 30 }[/math], открытый ключ — [math]\displaystyle{ (103,2267,354,1206) }[/math].

Подпись сообщения:

Пегги нужно подписать сообщение [math]\displaystyle{ M=1000 }[/math].
Пегги выбирает [math]\displaystyle{ r = 11 }[/math] и вычисляет [math]\displaystyle{ g^r = 354^{11} = 630 mod 2267 }[/math].
Предположим, что сообщение — [math]\displaystyle{ 1000 }[/math] , и последовательное соединение означает [math]\displaystyle{ 1000630 }[/math] . Также предположим, что хеширование этого значения дает дайджест [math]\displaystyle{ H(1000630) = 200 }[/math] . Это означает [math]\displaystyle{ S_1 = 200 }[/math] .
Пегги вычисляет [math]\displaystyle{ S_2 = r + wS_1 mod q = 11 + 30*200 mod 103 = 11 + 26 = 37 }[/math].
Пегги отправляет Виктору [math]\displaystyle{ M=1000 }[/math], [math]\displaystyle{ S_1 =200 }[/math] и [math]\displaystyle{ S_2 = 37 }[/math].

Патенты

Схема Шнорра имеет патенты в ряде стран. Например, в США № 4,995,082 от 19 февраля 1991 года (истёк 19 февраля 2008 года). В 1993 году Public Key Partners (PKP) из Саннивейла (Sunnyvale) приобрела мировые права на данный патент. Кроме США, данная схема запатентована также и в нескольких других странах.

Модификации схемы

Модификация схемы, которая была выполнена Эрни Брикеллом (Brickell) и Кевином МакКерли (McCurley) в 1992 году, значительно повысила безопасность данной схемы. В их методе используется число [math]\displaystyle{ p }[/math], которое так же, как и [math]\displaystyle{ p - 1 }[/math], сложно разложить, простой делитель [math]\displaystyle{ q }[/math] числа [math]\displaystyle{ p-1 }[/math] и элемент [math]\displaystyle{ \alpha }[/math] порядка [math]\displaystyle{ q }[/math] в [math]\displaystyle{ \mathbb{Z}_p^{*} }[/math], которые впоследствии применяются в подписи. В отличие от схемы Шнорра подпись в их методе вычисляется уравнением

[math]\displaystyle{ s = e \alpha + k\bmod(p-1) }[/math].

Преимущества

В то время, как в вычислительном плане модификация Брикелл и МакКерли менее эффективна, чем схема Шнорра, данный метод имеет преимущество, так как основывается на трудности двух сложных задач:

вычисление логарифма в циклической подгруппе порядка [math]\displaystyle{ q }[/math] в [math]\displaystyle{ \mathbb{Z}_p^{*} }[/math];
разложение [math]\displaystyle{ p-1 }[/math] на множители.

См. также

Примечания

Литература

Schnorr C.P. Efficient Signature Generation by Smart Cards. — J. Cryptology, 1991. — С. 161—174.
Schnorr C.P. Efficient Identification and Signatures for Smart Cards.Advances in Cryptology - CRYPTO’89. Lecture Notes in Computer Science 435. — 1990. — С. 239 — 252.
A. Menezes, P.van Oorschot, S. Vanstone. Handbook of Applied Cryptography. — CRC Press, 1996. — 816 с. — ISBN 0-8493-8523-7.
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
Варновский Н. П. Криптографические протоколы // Введение в криптографию / Под редакцией В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1. Архивная копия от 25 февраля 2008 на Wayback Machine

Ссылки

RFC 8235