Идентификация в криптографии

курсовая работа

Протоколы с нулевым разглашением

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

Протоколы с нулевым разглашением призваны решить эту проблему, давая возможность доказывающему продемонстрировать знание секрета, не выдавая о нем никакой информации. Точнее говоря, выдается только один бит информации, обозначающий то, что доказывающий знает секрет. 

В протоколах с нулевым разглашением термин “доказательство” имеет смысл, отличный от традиционно принятого в математике. Доказательство имеет вероятностный характер. Это означает, что утверждение имеет место с некоторой вероятностью, которая может быть выбрана сколь угодно близкой к единице.

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

А доказывает В знание секрета s с помощью t итераций следующего трехшагового протокола.

Доверенный центр T выбирает модуль n=pq и сообщает его всем доказывающим. При этом числар и q остаются секретными.

Каждый доказывающий А выбирает секрет S, которым является число, взаимно простое с n, 1 < s < n - 1, вычисляет значение v = S2 mod n и объявляет v своим открытым ключом.

Следующие три шага производятся независимо t раз, причем В принимает доказательство владения А секретом s, если все эти итерации приводят к положительному ответу.

1. А выбирает случайно Z, 1 <z<n- 1, и посылает В число х = Z2 mod n. 

2. В случайно выбирает бит с и направляет его А.

3. А вычисляет и направляет В число у, равное либо z, если с = 0, либо zs mod n, если с =1. В дает положительный ответ, если y не равен 0 и у2 = xvc (mod n).

Заметим, что в зависимости от значения бита с выполнено одно из двух условий: у2 = x(mod n) или у2 = xv(mod n), так как v = s2 (mod n). Проверка равенства y = O исключает случай z = 0. Корректность протокола может быть обоснована следующими рассуждениями. Наличие запроса с требует, чтобы А был в состоянии ответить на любой из двух вопросов, ответ на один из которых требует знания секрета S, а ответ на другой предотвращает попытку обмана. Противник, выдающий себя за A, может попытаться обмануть проверяющего, выбрав любое число z и передав В число х = z2/v.

Тогда он сможет ответить на запрос “с = 1”, направив правильный ответ “у = z”, но не сможет ответить на запрос “с = 0”, ответ на который требует знания корня квадратного из числах по модулю п.

Доказывающий A, знающий s, в состоянии ответить на оба вопроса. Если же он не знает S, то в лучшем случае -- на один из двух вопросов. Таким образом, обман удается с вероятностью, не превышающей 1/2. При кратной итерации протокола вероятность обмана может быть доведена до величины, не превышающей 2-t .

Ответ “у = z” не зависит от секрета s доказывающего A, а ответ У = zs mod n” также не несет информации о S, так как случайное z не известно проверяющему В.

Идеи, лежащие в основе протоколов с нулевым разглашением, могут быть сформулированы следующим образом.

Доказывающий А выбирает случайный элемент из заранее оговоренного множества, как свой секретный ключ для данной итерации протокола, вычисляет, используя его как аргумент некоторой однонаправленной функции, ее значение, и предъявляет это значение проверяющему. Этим обеспечивается случайность и независимость различных итераций протокола и определяется набор вопросов, на каждый из которых доказывающий готов дать ответ. Протокол построен так, что только доказывающий A, владеющий секретом S, в состоянии ответить на все эти вопросы, и ни один ответ не дает информации о секрете. На следующем этапе В выбирает один из этих вопросов и А дает на него ответ, который затем проверяется В. Осуществляется необходимое число итераций протокола с целью снизить до приемлемого уровня вероятность обмана. Другими словами, в основе протоколов с нулевым разглашением лежит комбинация идей протоколов типа “режь и выбирай” (этот термин происходит от стандартного метода, которым дети делят кусок пирога: один режет, а другой выбирает) и протоколов типа “запрос-ответ”.

Делись добром ;)