Схема Шнорра (англ. 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^{\ast }}$. Также данный метод используетхеш-функцию${\displaystyle h:\{0,1{\}}^{\ast }\to {\mathbb{Z}}_p}$.

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

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

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

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

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

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

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

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

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

${\displaystyle x=g^{s_1}{y}^{e_1}modp}$

${\displaystyle x=g^{s_2}{y}^{e_2}modp}$.

Отсюда${\displaystyle g^{s_1}{y}^{e_1}=g^{s_2}{y}^{e_2}(\mathrm{mod}p)}$ или же${\displaystyle y^{e_1-e_2}=g^{s_2-s_1}(\mathrm{mod}p)}$. Так как${\displaystyle e_1\ne e_2}$, то существует${\displaystyle (e_2-e_1{)}^{-1}modq}$ и, следовательно,${\displaystyle (s_1-s_2)(e_2-e_1{)}^{-1}=wmodq}$, то есть дискретный логарифм${\displaystyle y}$. Таким образом, либо${\displaystyle e_1,e_2,e_1\ne e_2}$ такие, что Алиса может ответить надлежащим образом на оба из них (при одном и том же${\displaystyle x}$) на шаге 3 протокола, встречаются редко, что означает, что атака Алисы успешна лишь с пренебрежимо малой вероятностью. Либо такие значения попадаются часто, и тогда тот алгоритм, который применяет Алиса, можно использовать для вычисления дискретных логарифмов.

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

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

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

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

   ${\displaystyle S_1=H(M|g^{r}modp)}$

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

   ${\displaystyle S_2=r+w{S}_{1}modq}$.

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

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

Основные вычисления для генерации подписи производятся на этапе предварительной обработки и на этапе вычисления${\displaystyle w{S}_{1}modq}$, где числа${\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=[lo{g}_{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\ast }}$. Тогда${\displaystyle \frac{p-1}{q}=22}$ и${\displaystyle g=2^{22}mod2267=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+w{S}_{1}modq=11+30\ast 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^{\ast }}$, которые впоследствии применяются в подписи. В отличие от схемы Шнорра подпись в их методе вычисляется уравнением

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

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

• вычисление логарифма в циклической подгруппе порядка${\displaystyle q}$ в${\displaystyle {\mathbb{Z}}_p^{\ast }}$;
• разложение${\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

Для улучшения этой статьижелательно: Проставитьсноски, внести более точные указания на источники. Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.

• Криптография
• Криптография с открытым ключом
• Электронная подпись

• Википедия:Статьи без сносок
• Википедия:Статьи к замене параметров шаблона rq
• Страницы, использующие волшебные ссылки ISBN
• Страницы, использующие волшебные ссылки RFC