Схема Шнорра

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

Введение

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

Патенты

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

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

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

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

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга:Шнайер Б.: Прикладная криптография
• Шаблон:Книга Шаблон:Wayback

Ссылки

• RFC 8235