Идентификация - аутентификация. Часть 4. Протоколы с нулевым разглашением.

В прошлой заметке мы рассмотрели протоколы идентификации "Запрос-Ответ", которые позволяли защитить секрет в условиях ненадёжного канала связи. Теперь же, рассмотрим протоколы, которые вообще предполагают отсутствие разглашения "секрета" в како-либо виде.
Это четвёртая теоритическая заметка из цикла.
--
Дело в том, что в предыдущих видах протоколов сторона A всегда отправляла B секрет, в каком-либо изменённом виде, или какую-то последовательность, сгенерированную на основе секрета, котороя также могла выдать секрет (обычно пароль) или его часть.
Решение - а давайте будем демонстрировать знание секрета, не выдавая о нём никакой информации. Т.е. выдаётся только один бит информации, обозначающий что A знает секрет. Если присмотреться - то это будет вполне похоже на предыдущий тип протоколов "Запрос-ответ"

Идея:
Протокол должен быть построен так, что только A, владеющий секретом может ответить на вопросы B, не выдавая никакой информации о секрете. Секрет - а лучше набор секретов, должен обеспечивать случайность и независимость различных циклов протокола.
К сожалению, при таком построении достоверность зависит от числа циклов протокола, так как информация о секрете не передаётся, то достоверность доказательства знания секрета носит вероятностный характер, вследствии чего протокол должен поддерживать множество циклов, увеличивая число которых можно асимптотически приблизить вероятность несанкционированнной аутентификации к 0.
Иными словами, чем больше раундов - тем надёжнее система

--
Собственно, слов много, но ничего пока не понятно. Предлагаю разобрать пример - Протокол Фиата-Шамира.
Он основан на сложности задач извлечения квадратного корня по модулю большого составного числа (с неизвестным разложением на множители)

В данном протоколе присутствует некий доверенный центр, который выдаёт обеим сторонам p, q и модуль n. Каждая сторона вычисляет число 1<=S<=n-1, которое взаимно простое с n.

Далее вычисляется V = S^2 mod n.

После чего запускаются раунды (циклы) аутентификации, каждый из которых состоит из шагов:

  1. A выбирает случайно число 1 < Z < n-1 и посылает B число x=Z^2 mod n
  2. B случайно выбирает бит c и посылает его A
  3. A вычисляет число y, причём y=z если c=0 и y=(Z*S) mod n, если c=1. после чего отправляет его B
  4. B выдаёт положительный ответ, если y!=0 и справедливо тождество y^2 = (x*v^c) mod n

B идентифицирует A только в том случае, когда даны верные ответы на все циклы аутентификации.

--

Собственно на этом всё, о протоколах с нулевым разглашением. Далее будут ещё заметки различного типа, по данному циклу. Но, самое основное что хотелось поведать - уже поведано.