Схема Шнорра

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Введение[править | править исходный текст]

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

Схема Шнорра минимизирует зависимость вычислений необходимых для создания подписи от сообщения. В этой схеме основные вычисления могут быть сделаны во время простоя процессора, что позволяет увеличить скорость подписания.

Генерация ключей[править | править исходный текст]

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

Протокол проверки подлинности[править | править исходный текст]

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

Безопасность алгоритма зависит от параметра r. Сложность вскрытия алгоритма примерно равна 2^r. Шнорр советует использовать r около 72 битов.

Пример[править | править исходный текст]

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

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

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

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

Протокол цифровой подписи[править | править исходный текст]

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

Генерация подписи[править | править исходный текст]

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

Проверка подписи[править | править исходный текст]

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

Эффективность[править | править исходный текст]

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

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

Пример[править | править исходный текст]

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

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

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

  1. Пегги нужно подписать сообщение M=1000.
  2. Пегги выбирает  r = 11 и вычисляет g^r = 35411 = 630 mod 2267.
  3. Предположим, что сообщение -  1000 , и последовательное соединение означает  1000630 . Также предположим, что хэширование этого значения дает дайджест  H(1000630) = 200 . Это означает  S_1 = 200 .
  4. Пегги вычисляет S_2 = r + wS_1 mod q = 11 + 1026*200 mod 103 = 11 + 24 = 35.
  5. Пегги отправляет Виктору M=1000, S_1 =200 и S_2 = 35.

Патенты[править | править исходный текст]

Схема Шнорра была запатентована в Соединенных Штатах. В 1993 году РКР приобрело мировые права на этот патент. Срок действия патента США истек 19 февраля 2008 года.

Литература[править | править исходный текст]