Схема Шнорра

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

Введение

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

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

В протоколе имеются два участника — Алиса, которая хочет подтвердить свой идентификатор, и Боб, который должен проверить это подтверждение. У Алисы имеется два ключа — <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^{-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^{w}\pmod p=7355</math> ключ
• Открытый ключ <math>(48731,443,11444, 7355)</math>, закрытый — <math>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>.

Литература

• 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.
• Варновский Н. П. [nature.web.ru/db/msg.html?mid=1157083&uri=node18.html Криптографические протоколы] // [nature.web.ru/db/msg.html?mid=1157083&uri=book.html Введение в криптографию] / Под редакцией В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1.

Отрывок, характеризующий Схема Шнорра

Во время короткого визита Николая, как и всегда, где есть дети, в минуту молчания Николай прибег к маленькому сыну князя Андрея, лаская его и спрашивая, хочет ли он быть гусаром? Он взял на руки мальчика, весело стал вертеть его и оглянулся на княжну Марью. Умиленный, счастливый и робкий взгляд следил за любимым ею мальчиком на руках любимого человека. Николай заметил и этот взгляд и, как бы поняв его значение, покраснел от удовольствия и добродушно весело стал целовать мальчика.
Княжна Марья не выезжала по случаю траура, а Николай не считал приличным бывать у них; но губернаторша все таки продолжала свое дело сватовства и, передав Николаю то лестное, что сказала про него княжна Марья, и обратно, настаивала на том, чтобы Ростов объяснился с княжной Марьей. Для этого объяснения она устроила свиданье между молодыми людьми у архиерея перед обедней.
Хотя Ростов и сказал губернаторше, что он не будет иметь никакого объяснения с княжной Марьей, но он обещался приехать.
Как в Тильзите Ростов не позволил себе усомниться в том, хорошо ли то, что признано всеми хорошим, точно так же и теперь, после короткой, но искренней борьбы между попыткой устроить свою жизнь по своему разуму и смиренным подчинением обстоятельствам, он выбрал последнее и предоставил себя той власти, которая его (он чувствовал) непреодолимо влекла куда то. Он знал, что, обещав Соне, высказать свои чувства княжне Марье было бы то, что он называл подлость. И он знал, что подлости никогда не сделает. Но он знал тоже (и не то, что знал, а в глубине души чувствовал), что, отдаваясь теперь во власть обстоятельств и людей, руководивших им, он не только не делает ничего дурного, но делает что то очень, очень важное, такое важное, чего он еще никогда не делал в жизни.
После его свиданья с княжной Марьей, хотя образ жизни его наружно оставался тот же, но все прежние удовольствия потеряли для него свою прелесть, и он часто думал о княжне Марье; но он никогда не думал о ней так, как он без исключения думал о всех барышнях, встречавшихся ему в свете, не так, как он долго и когда то с восторгом думал о Соне. О всех барышнях, как и почти всякий честный молодой человек, он думал как о будущей жене, примеривал в своем воображении к ним все условия супружеской жизни: белый капот, жена за самоваром, женина карета, ребятишки, maman и papa, их отношения с ней и т. д., и т. д., и эти представления будущего доставляли ему удовольствие; но когда он думал о княжне Марье, на которой его сватали, он никогда не мог ничего представить себе из будущей супружеской жизни. Ежели он и пытался, то все выходило нескладно и фальшиво. Ему только становилось жутко.


Страшное известие о Бородинском сражении, о наших потерях убитыми и ранеными, а еще более страшное известие о потере Москвы были получены в Воронеже в половине сентября. Княжна Марья, узнав только из газет о ране брата и не имея о нем никаких определенных сведений, собралась ехать отыскивать князя Андрея, как слышал Николай (сам же он не видал ее).
Получив известие о Бородинском сражении и об оставлении Москвы, Ростов не то чтобы испытывал отчаяние, злобу или месть и тому подобные чувства, но ему вдруг все стало скучно, досадно в Воронеже, все как то совестно и неловко. Ему казались притворными все разговоры, которые он слышал; он не знал, как судить про все это, и чувствовал, что только в полку все ему опять станет ясно. Он торопился окончанием покупки лошадей и часто несправедливо приходил в горячность с своим слугой и вахмистром.
Несколько дней перед отъездом Ростова в соборе было назначено молебствие по случаю победы, одержанной русскими войсками, и Николай поехал к обедне. Он стал несколько позади губернатора и с служебной степенностью, размышляя о самых разнообразных предметах, выстоял службу. Когда молебствие кончилось, губернаторша подозвала его к себе.
– Ты видел княжну? – сказала она, головой указывая на даму в черном, стоявшую за клиросом.
Николай тотчас же узнал княжну Марью не столько по профилю ее, который виднелся из под шляпы, сколько по тому чувству осторожности, страха и жалости, которое тотчас же охватило его. Княжна Марья, очевидно погруженная в свои мысли, делала последние кресты перед выходом из церкви.
Николай с удивлением смотрел на ее лицо. Это было то же лицо, которое он видел прежде, то же было в нем общее выражение тонкой, внутренней, духовной работы; но теперь оно было совершенно иначе освещено. Трогательное выражение печали, мольбы и надежды было на нем. Как и прежде бывало с Николаем в ее присутствии, он, не дожидаясь совета губернаторши подойти к ней, не спрашивая себя, хорошо ли, прилично ли или нет будет его обращение к ней здесь, в церкви, подошел к ней и сказал, что он слышал о ее горе и всей душой соболезнует ему. Едва только она услыхала его голос, как вдруг яркий свет загорелся в ее лице, освещая в одно и то же время и печаль ее, и радость.
– Я одно хотел вам сказать, княжна, – сказал Ростов, – это то, что ежели бы князь Андрей Николаевич не был бы жив, то, как полковой командир, в газетах это сейчас было бы объявлено.
Княжна смотрела на него, не понимая его слов, но радуясь выражению сочувствующего страдания, которое было в его лице.
– И я столько примеров знаю, что рана осколком (в газетах сказано гранатой) бывает или смертельна сейчас же, или, напротив, очень легкая, – говорил Николай. – Надо надеяться на лучшее, и я уверен…
Княжна Марья перебила его.
– О, это было бы так ужа… – начала она и, не договорив от волнения, грациозным движением (как и все, что она делала при нем) наклонив голову и благодарно взглянув на него, пошла за теткой.
Вечером этого дня Николай никуда не поехал в гости и остался дома, с тем чтобы покончить некоторые счеты с продавцами лошадей. Когда он покончил дела, было уже поздно, чтобы ехать куда нибудь, но было еще рано, чтобы ложиться спать, и Николай долго один ходил взад и вперед по комнате, обдумывая свою жизнь, что с ним редко случалось.
Княжна Марья произвела на него приятное впечатление под Смоленском. То, что он встретил ее тогда в таких особенных условиях, и то, что именно на нее одно время его мать указывала ему как на богатую партию, сделали то, что он обратил на нее особенное внимание. В Воронеже, во время его посещения, впечатление это было не только приятное, но сильное. Николай был поражен той особенной, нравственной красотой, которую он в этот раз заметил в ней. Однако он собирался уезжать, и ему в голову не приходило пожалеть о том, что уезжая из Воронежа, он лишается случая видеть княжну. Но нынешняя встреча с княжной Марьей в церкви (Николай чувствовал это) засела ему глубже в сердце, чем он это предвидел, и глубже, чем он желал для своего спокойствия. Это бледное, тонкое, печальное лицо, этот лучистый взгляд, эти тихие, грациозные движения и главное – эта глубокая и нежная печаль, выражавшаяся во всех чертах ее, тревожили его и требовали его участия. В мужчинах Ростов терпеть не мог видеть выражение высшей, духовной жизни (оттого он не любил князя Андрея), он презрительно называл это философией, мечтательностью; но в княжне Марье, именно в этой печали, выказывавшей всю глубину этого чуждого для Николая духовного мира, он чувствовал неотразимую привлекательность.
«Чудная должна быть девушка! Вот именно ангел! – говорил он сам с собою. – Отчего я не свободен, отчего я поторопился с Соней?» И невольно ему представилось сравнение между двумя: бедность в одной и богатство в другой тех духовных даров, которых не имел Николай и которые потому он так высоко ценил. Он попробовал себе представить, что бы было, если б он был свободен. Каким образом он сделал бы ей предложение и она стала бы его женою? Нет, он не мог себе представить этого. Ему делалось жутко, и никакие ясные образы не представлялись ему. С Соней он давно уже составил себе будущую картину, и все это было просто и ясно, именно потому, что все это было выдумано, и он знал все, что было в Соне; но с княжной Марьей нельзя было себе представить будущей жизни, потому что он не понимал ее, а только любил.
Мечтания о Соне имели в себе что то веселое, игрушечное. Но думать о княжне Марье всегда было трудно и немного страшно.
«Как она молилась! – вспомнил он. – Видно было, что вся душа ее была в молитве. Да, это та молитва, которая сдвигает горы, и я уверен, что молитва ее будет исполнена. Отчего я не молюсь о том, что мне нужно? – вспомнил он. – Что мне нужно? Свободы, развязки с Соней. Она правду говорила, – вспомнил он слова губернаторши, – кроме несчастья, ничего не будет из того, что я женюсь на ней. Путаница, горе maman… дела… путаница, страшная путаница! Да я и не люблю ее. Да, не так люблю, как надо. Боже мой! выведи меня из этого ужасного, безвыходного положения! – начал он вдруг молиться. – Да, молитва сдвинет гору, но надо верить и не так молиться, как мы детьми молились с Наташей о том, чтобы снег сделался сахаром, и выбегали на двор пробовать, делается ли из снегу сахар. Нет, но я не о пустяках молюсь теперь», – сказал он, ставя в угол трубку и, сложив руки, становясь перед образом. И, умиленный воспоминанием о княжне Марье, он начал молиться так, как он давно не молился. Слезы у него были на глазах и в горле, когда в дверь вошел Лаврушка с какими то бумагами.
– Дурак! что лезешь, когда тебя не спрашивают! – сказал Николай, быстро переменяя положение.
– От губернатора, – заспанным голосом сказал Лаврушка, – кульер приехал, письмо вам.
– Ну, хорошо, спасибо, ступай!
Николай взял два письма. Одно было от матери, другое от Сони. Он узнал их по почеркам и распечатал первое письмо Сони. Не успел он прочесть нескольких строк, как лицо его побледнело и глаза его испуганно и радостно раскрылись.
– Нет, это не может быть! – проговорил он вслух. Не в силах сидеть на месте, он с письмом в руках, читая его. стал ходить по комнате. Он пробежал письмо, потом прочел его раз, другой, и, подняв плечи и разведя руками, он остановился посреди комнаты с открытым ртом и остановившимися глазами. То, о чем он только что молился, с уверенностью, что бог исполнит его молитву, было исполнено; но Николай был удивлен этим так, как будто это было что то необыкновенное, и как будто он никогда не ожидал этого, и как будто именно то, что это так быстро совершилось, доказывало то, что это происходило не от бога, которого он просил, а от обыкновенной случайности.