Интернет магазин китайских планшетных компьютеров

Компьютеры - Протокол Фиата-Шамира

это один из наиболее известных протоколов идентификации с нулевым разглашением. Протокол был предложен Амосом Фиатом и Ади Шамиром

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

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

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

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

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

Передаваемые сообщения

• AB : x = r
• AB :
• AB : y = r * s

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

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

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

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