Feige –Фиат – Схема идентификации Шамира

В криптографии используется схема идентификации Фейге – Фиат – Шамир - это тип параллельного доказательства с нулевым разглашением, разработанный Уриэлем Фейге, Амосом Фиатом и Ади Шамиром в 1988 году. доказательства с нулевым разглашением, это позволяет одной стороне, Доказывающему, доказать другой стороне, Проверяющему, что она обладает секретной информацией, не раскрывая Проверяющему, что это за секретная информация. Однако схема идентификации Фейдж-Фиат-Шамир использует модульную арифметику и параллельный процесс проверки, который ограничивает количество коммуникаций между проверяющим и проверяющим.

• 1 Настройка
• 2 Процедура
• 3 Безопасность
• 4 Ссылки

Следуя общепринятому соглашению, вызовите прувер Пегги и верификатор Виктор.

Выберите два больших простых целых числа p и q и вычислите произведение n = pq. Создайте секретные числа $s\; 1,\; \cdots ,\; s\; k\; \{\backslash \; displaystyle\; s\_\; \{1\},\; \backslash \; cdots,\; s\_\; \{k\}\}$coprime с n. Вычислить $v\; i\; \equiv \; s\; i\; 2\; (mod\; n)\; \{\backslash \; displaystyle\; v\_\; \{i\}\; \backslash \; Equiv\; s\_\; \{i\}\; ^\; \{2\}\; \{\backslash \; pmod\; \{n\}\}\}$. Пегги и Виктор получают $n\; \{\backslash \; displaystyle\; n\}$, а $p\; \{\backslash \; displaystyle\; p\}$и $q\; \{\backslash \; displaystyle\; q\}$держатся в секрете. Затем Пегги отправляют числа $s\; i\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$. Это ее секретные логины. Пегги отправляет Виктору номера $v\; i\; \{\backslash \; displaystyle\; v\_\; \{i\}\}$, когда она хочет представиться Виктору. Виктор не может восстановить числа Пегги $si\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$из своих чисел $vi\; \{\backslash \; displaystyle\; v\_\; \{i\}\}$из-за сложности при определении модульного квадратного корня , когда факторизация модуля неизвестна.

1. Пегги выбирает случайное целое число $r\; \{\backslash \; displaystyle\; r\}$, случайный знак $s\; \in \; \{-\; 1,\; 1\}\; \{\backslash \; displaystyle\; s\; \backslash \; in\; \backslash \; \{-\; 1,1\; \backslash \}\}$и вычисляет $x\; \equiv \; s\; \cdot \; r\; 2\; (mod\; n)\; \{\backslash \; displaystyle\; x\; \backslash \; Equiv\; s\; \backslash \; cdot\; r\; ^\; \{2\}\; \{\backslash \; pmod\; \{n\; \}\}\}$. Пегги отправляет Виктору $x\; \{\backslash \; displaystyle\; x\}$.
2. Виктор выбирает числа $a\; 1,\; \cdots ,\; ak\; \{\backslash \; displaystyle\; a\_\; \{1\},\; \backslash \; cdots,\; a\_\; \{k\}\}$где $ai\; \{\backslash \; displaystyle\; a\_\; \{i\}\}$равно 0 или 1. Виктор отправляет эти числа Пегги.
3. Пегги вычисляет $y\; \equiv \; rs\; 1\; a\; 1\; s\; 2\; a\; 2\; \cdots \; skak\; (mod\; n)\; \{\backslash \; displaystyle\; y\; \backslash \; Equiv\; rs\_\; \{1\}\; ^\; \{a\_\; \{1\}\}\; s\_\; \{2\}\; ^\; \{a\_\; \{2\}\}\; \backslash \; cdots\; s\_\; \{\; k\}\; ^\; \{a\_\; \{k\}\}\; \{\backslash \; pmod\; \{n\}\}\}$. Пегги отправляет это число Виктору.
4. Виктор проверяет, что $y\; 2\; \equiv \; \pm \; xv\; 1\; a\; 1\; v\; 2\; a\; 2\; \cdots \; vkak\; (mod\; n)\; \{\backslash \; displaystyle\; y\; ^\; \{2\}\; \backslash \; Equiv\; \backslash \; pm\; \backslash ,\; xv\_\; \{1\}\; ^\; \{a\_\; \{1\}\}\; v\_\; \{2\}\; ^\; \{a\_\; \{2\}\}\; \backslash \; cdots\; v\_\; \{k\}\; ^\; \{a\_\; \{k\}\}\; \{\backslash \; pmod\; \{n\}\}\}$и что $x\; \ne \; 0.\; \{\backslash \; displaystyle\; x\; \backslash \; neq\; 0.\}$

Эта процедура повторяется с другими $r\; \{\backslash \; displaystyle\; r\}$и $ai\; \{\backslash \; displaystyle\; a\_\; \{i\}\}$, пока Виктор не убедится, что Пегги действительно обладает модульными квадратными корнями ($si\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$) его $vi\; \{\backslash \; displaystyle\; v\_\; \{i\}\}$числа.

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

Предположим, Ева перехватила номера Виктора $vi\; \{\backslash \; displaystyle\; v\_\; \{i\}\}$, но не знает, какие у Пегги $si\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$числа. Если Ева хочет попытаться убедить Виктора в том, что она Пегги, она должна будет правильно угадать, какими будут числа Виктора $a\; i\; \{\backslash \; displaystyle\; a\_\; \{i\}\}$. Затем она выбирает случайный $y\; \{\backslash \; displaystyle\; y\}$, вычисляет $x\; \equiv \; y\; 2\; v\; 1\; -\; a\; 1\; v\; 2\; -\; a\; 2\; \cdots \; vk\; -\; ak\; (mod\; n)\; \{\backslash \; displaystyle\; x\; \backslash \; Equiv\; y\; ^\; \{2\}\; v\_\; \{1\}\; ^\; \{-\; a\_\; \{1\}\}\; v\_\; \{2\}\; ^\; \{-\; a\_\; \{2\}\}\; \backslash \; cdots\; v\_\; \{k\}\; ^\; \{-\; a\_\; \{k\}\}\; \{\backslash \; pmod\; \{\; n\}\}\}$и отправляет $x\; \{\backslash \; displaystyle\; x\}$Виктору. Когда Виктор отправляет $a\; i\; \{\backslash \; displaystyle\; a\_\; \{i\}\}$, Ева просто возвращает ей $y\; \{\backslash \; displaystyle\; y\}$. Виктор удовлетворен и приходит к выводу, что у Евы есть секретные числа. Однако вероятность того, что Ева правильно угадывает, каким будет $ai\; \{\backslash \; displaystyle\; a\_\; \{i\}\}$Виктора, равна 1 из $2\; k\; \{\backslash \; displaystyle\; 2\; ^\; \{k\}\}$. Если повторить процедуру $t\; \{\backslash \; displaystyle\; t\}$раз, вероятность снизится до 1 из $2\; k\; t\; \{\backslash \; displaystyle\; 2\; ^\; \{kt\}\}$. Для $k\; =\; 5\; \{\backslash \; displaystyle\; k\; =\; 5\}$и $t\; =\; 4\; \{\backslash \; displaystyle\; t\; =\; 4\}$вероятность успешного позирования Пегги меньше 1 из 1 миллиона.

• Файги, Уриэль; Фиат, Амос; Шамир, Ади (1988). «Доказательства личности с нулевым разглашением». Журнал криптологии. 1 (2): 77–94. doi : 10.1007 / BF02351717.
• Трапп, Уэйд; Вашингтон, Лоуренс К. (2003). Введение в криптографию с теорией кодирования. Река Верхнее Седл: Прентис-Холл. Стр. 231 –233. ISBN 0-13-061814-4.