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



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

23 января 2011


Оглавление:
1. Протокол Фиата-Шамира
2. Пример



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

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

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

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

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

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

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

  • A\RightarrowB : x = r
  • A\LeftarrowB : e\in{0,1}
  • A\RightarrowB : y = r * s

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

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

  • А выбирает случайное r , такое, что r\in и отсылает 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 раундов прошли успешно.



Просмотров: 1355


<<< Протокол Фейга-Фиата-Шамира
Cold boot attack >>>