Русская Википедия:Схема Шнорра

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Введение

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

<math>x=g^{s_1}y^{e_1} \bmod p</math>

<math>x=g^{s_2}y^{e_2} \bmod p</math>.

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

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

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

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

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

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

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

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

   <math>S_1=H(M | g^r \bmod p)</math>

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

   <math>S_2=r+wS_1 \bmod q</math>.

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

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

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

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

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

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

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

Пример

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

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

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

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

Патенты

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

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

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

<math>s = e \alpha + k\bmod(p-1)</math>.

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

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

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

См. также

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

Литература

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

Ссылки

• RFC 8235