- Протокол Фиата-Шамира
-
Протокол Фиата-Шамира
Протокол Фиата-Шамира — это один из наиболее известных протоколов идентификации с нулевым разглашением (Zero-knowledge protocol). Протокол был предложен Амосом Фиатом(англ. Amos Fiat) и Ади Шамиром(англ. Adi Shamir)
Пусть А знает некоторый секрет s. Необходимо доказать знание этого секрета некоторой стороне В без разглашение какой-либо секретной информации. Стойкость протокола основывается на сложности извлечения квадратного корня по модулю достаточно большого составного числа n, факторизация которого неизвестна.
Содержание
Описание протоколa
A доказывает B знание s в течение t раундов. Раунд называют также аккредитацией. Каждая аккредитация состоит из 3х этапов.
Предварительные действия
- Доверенный центр Т выбирает и публикует модуль n = p * q, где p, q -простые и держатся в секрете.
- Каждый претендент A выбирает s взаимно-простое с n, где . Затем вычисляется v = s2(mod n). V регистрируется T в качестве открытого ключа A
Передаваемые сообщения (этапы каждой аккредитации)
- AB : x = r2(mod n)
- AB :
- AB : y = r * se(mod n)
Основные действия
Следующие действия последовательно и независимо выполняются t раз. В считает знание доказанным, если все t раундов прошли успешно.
- А выбирает случайное r , такое, что и отсылает x = r2(mod n) стороне B (доказательство)
- B случайно выбирает бит e (e=0 или е=1) и отсылает его A (вызов)
- А вычисляет у и отправляет его обратно к B. Если e=0, то y = r, иначе y = r * s(mod n) (ответ)
- Если y=0, то B отвергает доказательство или, другими словами, А не удалось доказать знание s. В противном случае, сторона B проверяет, действительно ли y2 = x * ve(mod n) и, если это так, то происходит переход к следующему раунду протокола.
Выбор е из множества {0,1} предполагает, что если сторона А действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного e. Допустим, что А хочет обмануть B. В этом случае А, может отреагировать только на конкретное значение e. Например, если А знает, что получит е=0, то А следует действовать строго по иниструкции и В примет ответ. В случаи если А знает, что получит е=1, то А выбирает случайное r и отсылает x = r2 / v на сторону В, в результате получаем нам нужное y = r. Проблема заключается в том, что А изначально не знает какое e он получит и поэтому не может со 100% вероятностью выслать на сторону В нужные для обмана r и х (x = r2 при e=0 и x = r2 / v при e=1). Поэтому вероятность обмана в одном раунде составляет 50%. Чтобы снизить вероятность жульничества (она равна 1 / 2t)) t выбирают достаточно большим (t=20, t=40). Таким образом, B удостоверяется в знании А тогда и только тогда, когда все t раундов прошли успешно.
Пример
- Пусть доверенный центр выбрал простые p=683 и q=811, тогда n=683*811=553913. А выбирает s=43215.
Откуда v = 432152(mod 553913) = 1867536225(mod 553913) = 295502
- A выбирает r=38177 и считает x = 381772(mod 553913) = 1457483329(mod 553913) = 138226
- Если B отправил e=0, то A возвращает y=38177. Иначе, A возвращает y = 38177 * 43215(mod 553913) = 1649819055(mod 553913) = 266141
- Проверка B:
Если e было равно 0, то y2 = 381772(mod 553913) = 1457483329 = 138266 Подтверждено. Иначе, y2 = 2661412(mod 553913) = 70831031881(mod 553913) = 514832 и x * v = 138226 * 295502(mod 553913) = 40846059452(mod 553913) = 514832 Подтверждено.
Литература
- 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
Wikimedia Foundation. 2010.