Протокол Фиата — Шамира

Протокол Фиата — Шамира — это один из наиболее известных протоколов идентификации с нулевым разглашением (Zero-knowledge protocol). Протокол был предложен Амосом Фиатом (англ. Amos Fiat) и Ади Шамиром (англ. Adi Shamir)

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

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

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

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

• Доверенный центр Т выбирает и публикует модуль $n=p\ast <!--\; \ast \; -->q$$n=p*q$ , где p, q — простые и держатся в секрете.
• Каждый претендент A выбирает s взаимно-простое с n, где $s\in <!--\; \in \; -->[1,n-<!--\; -\; -->1]$$s\in[1,n-1]$ . Затем вычисляется V$=s^2(\mathrm{mod}n)$$=s^2\pmod n$ . V регистрируется T в качестве открытого ключа A

Передаваемые сообщения (этапы каждой аккредитации)Править

• A$\Rightarrow <!--\; \Rightarrow \; -->$$\Rightarrow$ B : $x=r^2(\mathrm{mod}n)$$x=r^2\pmod n$ 
• A$\Leftarrow <!--\; \Leftarrow \; -->$$\Leftarrow$ B : $e\in <!--\; \in \; -->0,1$$e\in{0,1}$ 
• A$\Rightarrow <!--\; \Rightarrow \; -->$$\Rightarrow$ B : $y=r\ast <!--\; \ast \; -->s^e(\mathrm{mod}n)$$y=r*s^e\pmod n$ 

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

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

• А выбирает случайное r , такое, что $r\in <!--\; \in \; -->[1,n-<!--\; -\; -->1]$$r\in[1,n-1]$  и отсылает $x=r^2(\mathrm{mod}n)$$x=r^2\pmod n$  стороне B (доказательство)
• B случайно выбирает бит e (e=0 или е=1) и отсылает его A (вызов)
• А вычисляет у и отправляет его обратно к B. Если e=0, то $y=r$$y=r$ , иначе $y=r\ast <!--\; \ast \; -->s(\mathrm{mod}n)$$y=r*s\pmod n$  (ответ)
• Если y=0, то B отвергает доказательство или, другими словами, А не удалось доказать знание s. В противном случае, сторона B проверяет, действительно ли $y^2=x\ast <!--\; \ast \; -->v^e(\mathrm{mod}n)$$y^2= x*v^e\pmod n$  и, если это так, то происходит переход к следующему раунду протокола.

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

ПримерПравить

• Пусть доверенный центр выбрал простые p=683 и q=811, тогда n=683*811=553913. А выбирает s=43215.

Откуда $v={43215}^2(\mathrm{mod}553913)=1867536225(\mathrm{mod}553913)=295502$$v=43215^2 \pmod{553913}= 1867536225 \pmod{553913}=295502$ 

• A выбирает r=38177 и считает $x={38177}^2(\mathrm{mod}553913)=1457483329(\mathrm{mod}553913)=138226$$x=38177^2 \pmod{553913}=1457483329 \pmod{553913}=138226$ 
• Если B отправил e=0, то A возвращает y=38177. Иначе, A возвращает $y=38177\ast <!--\; \ast \; -->43215(\mathrm{mod}553913)=1649819055(\mathrm{mod}553913)=266141$$y=38177*43215 \pmod{553913}=1649819055 \pmod {553913}=266141$ 
• Проверка B: $y^2\equiv <!--\; \equiv \; -->x\ast <!--\; \ast \; -->v^e(\mathrm{mod}n)$$y^2 \equiv x*v^e \pmod n$ 

Если e было равно 0, то $y^2={38177}^2(\mathrm{mod}553913)=1457483329=138266$$y^2=38177^2\pmod{553913}=1457483329=138266$  Подтверждено.

Иначе, $y^2={266141}^2(\mathrm{mod}553913)=70831031881(\mathrm{mod}553913)=514832$$y^2=266141^2 \pmod {553913}=70831031881 \pmod {553913}=514832$ 

и $x\ast <!--\; \ast \; -->v=138226\ast <!--\; \ast \; -->295502(\mathrm{mod}553913)=40846059452(\mathrm{mod}553913)=514832$$x*v=138226*295502 \pmod {553913}=40846059452 \pmod {553913}=514832$  Подтверждено.

ЛитератураПравить

• Menezes A., van Oorschot P., Vanstone S. 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.