Протокол Фиата — Шамира: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
Fauust (обсуждение | вклад)
оформление
Исправил логику обмана алгоритма
Строка 24: Строка 24:
* Если '''y'''=0, то '''B''' отвергает доказательство или, другими словами, '''А''' не удалось доказать знание '''s'''. В противном случае, сторона '''B''' проверяет, действительно ли <math>y^2= x*v^e\pmod n</math> и, если это так, то происходит переход к следующему раунду протокола.
* Если '''y'''=0, то '''B''' отвергает доказательство или, другими словами, '''А''' не удалось доказать знание '''s'''. В противном случае, сторона '''B''' проверяет, действительно ли <math>y^2= x*v^e\pmod n</math> и, если это так, то происходит переход к следующему раунду протокола.


Выбор '''е''' из множества {0,1} предполагает, что если сторона '''А''' действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного '''e'''. Допустим, что '''А''' хочет обмануть '''B'''. '''А''' выбирает случайное '''r''' и отсылает <math>x=r^2/v</math>, тогда если '''е'''=0, то '''А''' удачно возвращает '''B''' <math>y=r</math>, в случае же '''е'''=1, '''А''' не сможет правильно ответить, так как не знает '''s''', а извлечь квадратный корень из '''v''' по модулю '''n''' достаточно сложно.
Выбор '''е''' из множества {0,1} предполагает, что если сторона '''А''' действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного '''e'''. Допустим, что '''А''' хочет обмануть '''B'''. В этом случае '''А''', может отреагировать только на конкретное значение '''e'''. Например, если '''А''' знает, что получит '''е'''=0, то '''А''' следует действовать строго по иниструкции и '''В''' примет ответ. В случаи если '''А''' знает, что получит '''е'''=1, то '''А''' выбирает случайное '''r''' и отсылает <math>x=r^2/v</math> на сторону '''В''', в результате получаем нам нужное <math>y=r</math>. Проблема заключается в том, что '''А''' изначально не знает какое '''e''' он получит и поэтому не может со 100% вероятностью выслать на сторону '''В''' нужные для обмана '''r''' и '''х''' (<math>x=r^2</math> при '''e'''=0 и <math>x=r^2/v</math> при '''e'''=1). Поэтому вероятность обмана в одном раунде составляет 50%.
Чтобы снизить вероятность жульничества (она равна <math>1/2^t)</math>) '''t''' выбирают достаточно большим ('''t'''=20, '''t'''=40). Таким образом, '''B''' удостоверяется в знании '''А''' тогда и только тогда, когда все '''t''' раундов прошли успешно.
Чтобы снизить вероятность жульничества (она равна <math>1/2^t)</math>) '''t''' выбирают достаточно большим ('''t'''=20, '''t'''=40). Таким образом, '''B''' удостоверяется в знании '''А''' тогда и только тогда, когда все '''t''' раундов прошли успешно.



== Пример ==
== Пример ==

Версия от 17:57, 13 апреля 2010

Протокол Фиата-Шамира — это один из наиболее известных протоколов идентификации с нулевым разглашением (Zero-knowledge protocol). Протокол был предложен Амосом Фиатом(англ. Amos Fiat) и Ади Шамиром(англ. Adi Shamir)

Пусть А знает некоторый секрет s. Необходимо доказать знание этого секрета некоторой стороне В без разглашение какой-либо секретной информации. Стойкость протокола основывается на сложности извлечения квадратного корня по модулю достаточно большого составного числа n, факторизация которого неизвестна.


Описание протоколa

A доказывает B знание s в течение t раундов. Раунд называют также аккредитацией. Каждая аккредитация состоит из 3х этапов.

Предварительные действия

  • Доверенный центр Т выбирает и публикует модуль , где p, q -простые и держатся в секрете.
  • Каждый претендент A выбирает s взаимно-простое с n, где . Затем вычисляется . V регистрируется T в качестве открытого ключа A

Передаваемые сообщения (этапы каждой аккредитации)

  • AB :
  • AB :
  • AB :

Основные действия

Следующие действия последовательно и независимо выполняются t раз. В считает знание доказанным, если все t раундов прошли успешно.

  • А выбирает случайное r , такое, что и отсылает стороне B (доказательство)
  • B случайно выбирает бит e (e=0 или е=1) и отсылает его A (вызов)
  • А вычисляет у и отправляет его обратно к B. Если e=0, то , иначе (ответ)
  • Если y=0, то B отвергает доказательство или, другими словами, А не удалось доказать знание s. В противном случае, сторона B проверяет, действительно ли и, если это так, то происходит переход к следующему раунду протокола.

Выбор е из множества {0,1} предполагает, что если сторона А действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного e. Допустим, что А хочет обмануть B. В этом случае А, может отреагировать только на конкретное значение e. Например, если А знает, что получит е=0, то А следует действовать строго по иниструкции и В примет ответ. В случаи если А знает, что получит е=1, то А выбирает случайное r и отсылает на сторону В, в результате получаем нам нужное . Проблема заключается в том, что А изначально не знает какое e он получит и поэтому не может со 100% вероятностью выслать на сторону В нужные для обмана r и х ( при e=0 и при e=1). Поэтому вероятность обмана в одном раунде составляет 50%. Чтобы снизить вероятность жульничества (она равна ) t выбирают достаточно большим (t=20, t=40). Таким образом, B удостоверяется в знании А тогда и только тогда, когда все t раундов прошли успешно.

Пример

  • Пусть доверенный центр выбрал простые p=683 и q=811, тогда n=683*811=553913. А выбирает s=43215.

Откуда

  • A выбирает r=38177 и считает
  • Если B отправил e=0, то A возвращает y=38177. Иначе, A возвращает
  • Проверка B:

Если e было равно 0, то Подтверждено. Иначе, и Подтверждено.


Литература

  • 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.