Войти  |  Регистрация
Авторизация

Схема Шнорра



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

Введение

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

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

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

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

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

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

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

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

  • Предварительная обработка. Алиса выбирает случайное число r {displaystyle r} , меньшее q {displaystyle q} , и вычисляет x = g r ( mod p ) {displaystyle x=g^{r}{pmod {p}}} . Эти вычисления являются предварительными и могут быть выполнены задолго до появления Боба.
  • Инициирование. Алиса посылает x {displaystyle x} Бобу.
  • Боб выбирает случайное число e {displaystyle e} из диапазона от 0 {displaystyle 0} до 2 t − 1 {displaystyle 2^{t}-1} и отправляет его Алисе.
  • Алиса вычисляет s = r + w e ( mod q ) {displaystyle s=r+we{pmod {q}}} и посылает s {displaystyle s} Бобу.
  • Подтверждение. Боб проверяет что x = g s y e ( mod p ) {displaystyle x=g^{s}y^{e}{pmod {p}}}
  • Безопасность алгоритма зависит от параметра t. Сложность вскрытия алгоритма примерно равна 2 t {displaystyle 2^{t}} . Шнорр советует использовать t около 72 битов, для p ≥ 2 512 {displaystyle pgeq 2^{512}} и q ≥ 2 140 {displaystyle qgeq 2^{140}} . Для решения задачи дискретного логарифма, в этом случае, требуется по крайней мере 2 72 {displaystyle 2^{72}} шагов известных алгоритмов.

    Пример

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

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

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

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

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

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

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

    x = g s 1 y e 1 mod p {displaystyle x=g^{s_{1}}y^{e_{1}}{mod {p}}} x = g s 2 y e 2 mod p {displaystyle x=g^{s_{2}}y^{e_{2}}{mod {p}}} .

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

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

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

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

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

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

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

  • Предварительная обработка. Пегги выбирает случайное число r {displaystyle r} , меньшее q {displaystyle q} , и вычисляет x = g r ( mod p ) {displaystyle x=g^{r}{pmod {p}}} . Это стадия предварительных вычислений. Стоит отметить, что для подписи разных сообщений могут использоваться одинаковые открытый и закрытый ключи, в то время как число r {displaystyle r} выбирается заново для каждого сообщения.
  • Пегги объединяет сообщение M {displaystyle M} и x {displaystyle x} и хеширует результат для получения первой подписи: S 1 = H ( M | g r mod p ) {displaystyle S_{1}=H(M|g^{r}{mod {p}})}
  • Пегги вычисляет вторую подпись. Необходимо отметить, что вторая подпись вычисляется по модулю q {displaystyle q} . S 2 = r + w S 1 mod q {displaystyle S_{2}=r+wS_{1}{mod {q}}} .
  • Пегги отправляет Виктору сообщение M {displaystyle M} и подписи S 1 {displaystyle S_{1}} , S 2 {displaystyle S_{2}} .
  • Проверка подписи

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

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

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

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

    Пример

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

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

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

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

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

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

    s = e α + k mod ( p − 1 ) {displaystyle s=ealpha +k{mod {(}}p-1)} .

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

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

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

    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent