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

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

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

В протоколе предполагается, что обеим сторонам заранее известно некоторое число n = pq. При этом разложение числа n на простые множители считается неизвестным для всех участников протокола.

Описание алгоритма

Доказывающая сторона выбирает секретное число s, взаимно простое с n, далее вычисляет значение v ≡ s² mod n и публикует значение, объявляя его своим открытым ключом.

Далее следует выполнение протокола идентификации:

1. Алиса выбирает некоторое случайное число z, 1 < z < n — 1
2. Алиса вычисляет число x ≡ z² mod n и посылает его проверяющей стороне
3. Боб выбирает случайный бит b и пересылает его Алисе
4. Алиса вычисляет число y: если b = 0, то y = z, иначе y ≡ zs mod n, и пересылает число y Бобу.
5. Боб проверяет, что y² ≡ xv mod n.

Если b = 0, то y = z, y² = z², xv = x, и проверка означает, что выражение x ≡ z² mod n верно. Аналогично, если b = 1, то y ≡ zs mod n, y² ≡ z²s² mod n, xv = xv ≡ xs² mod n. И проверка также означает, что выражение z²s² ≡ xs² mod n

Эти шаги образуют один цикл протокола, называемый аккредитацией. Алиса и Боб повторяют этот цикл t раз при разных случайных значениях z и b до тех пор, пока Боб не убедится, что Алиса знает значение s.