Схема Шнорра

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

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

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

В протоколе имеются два участника — Алиса, которая хочет подтвердить свой идентификатор, и Боб, который должен проверить это подтверждение. У Алисы имеется два ключа — ${\displaystyle \mathrm {K} _{1}}$, открытый (общедоступный), и ${\displaystyle \mathrm {K} _{2}}$ — закрытый (приватный) ключ, известный только Алисе. Фактически, Боб должен проверить, что Алиса знает свой закрытый ключ ${\displaystyle \mathrm {K} _{2}}$, используя только ${\displaystyle \mathrm {K} _{1}}$.

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

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

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

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

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

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

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

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

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

Если в схеме Шнорра предположить, что Алиса является противником, то на шаге 1 она может выбрать ${\displaystyle x}$ случайным, но эффективным способом. Пусть ${\displaystyle x}$ — это переданное Алисой число. Предположим, что можно найти два случайных числа ${\displaystyle e_{1}}$ и ${\displaystyle e_{2}}$ такие, что ${\displaystyle e_{1}\neq e_{2}}$ и для каждого из них Алиса может найти соответствующие ${\displaystyle s_{1}}$ и ${\displaystyle s_{2}}$, для которых подтверждение даст положительный результат. Получаем:

${\displaystyle x=g^{s_{1}}y^{e_{1}}{\bmod {p}}}$

${\displaystyle x=g^{s_{2}}y^{e_{2}}{\bmod {p}}}$.

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

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

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

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

1. Предварительная обработка. Пегги выбирает случайное число ${\displaystyle r}$, меньшее ${\displaystyle q}$, и вычисляет ${\displaystyle x=g^{r}{\pmod {p}}}$. Это стадия предварительных вычислений. Стоит отметить, что для подписи разных сообщений могут использоваться одинаковые открытый и закрытый ключи, в то время как число ${\displaystyle r}$ выбирается заново для каждого сообщения.
2. Пегги объединяет сообщение ${\displaystyle M}$ и ${\displaystyle x}$ и хеширует результат для получения первой подписи:

   ${\displaystyle S_{1}=H(M|g^{r}{\bmod {p}})}$

3. Пегги вычисляет вторую подпись. Необходимо отметить, что вторая подпись вычисляется по модулю ${\displaystyle q}$.

   ${\displaystyle S_{2}=r+wS_{1}{\bmod {q}}}$.

4. Пегги отправляет Виктору сообщение ${\displaystyle M}$ и подписи ${\displaystyle S_{1}}$, ${\displaystyle S_{2}}$.

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

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

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

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

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

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

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

1. Пегги нужно подписать сообщение ${\displaystyle M=1000}$.
2. Пегги выбирает ${\displaystyle r=11}$ и вычисляет ${\displaystyle g^{r}=354^{11}=630mod2267}$.
3. Предположим, что сообщение — ${\displaystyle 1000}$ , и последовательное соединение означает ${\displaystyle 1000630}$ . Также предположим, что хеширование этого значения дает дайджест ${\displaystyle H(1000630)=200}$ . Это означает ${\displaystyle S_{1}=200}$ .
4. Пегги вычисляет ${\displaystyle S_{2}=r+wS_{1}modq=11+30*200mod103=11+26=37}$.
5. Пегги отправляет Виктору ${\displaystyle M=1000}$, ${\displaystyle S_{1}=200}$ и ${\displaystyle S_{2}=37}$.

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

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

${\displaystyle s=e\alpha +k{\bmod {(}}p-1)}$.

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

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

• Криптосистема с открытым ключом
• DSA
• Схема Эль-Гамаля

• 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