Протокол Фейга — Фиата — Шамира (Feige-Fiat-Shamir) — это один из протоколов идентификации с нулевым разглашением. Основывается на сложности вычисления квадратного корня числа по модулю большого числа с неизвестным разложением на простые множители. Был предложен в 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^b mod n.

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

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

Выводы

Если Алисе неизвестно значение s, она может выбрать такое значение z, которое позволит ей обмануть Боба, либо если он перешлет ей b = 0, либо если он перешлет ей b = 1. Но обмануть Боба в обоих случаях одновременно ей не удастся. Вероятность того, что Алиса обманет Боба в одном цикле, составляет 1/2. Вероятность же обмануть Боба в t циклах равна (1/2)^t.

Для того чтобы этот протокол корректно выполнялся, Алиса никогда не должна повторно использовать значение z. Если бы Алиса поступила таким образом, а Боб во время другого цикла отправил бы Алисе на шаге 2 другой случайный бит b, то Боб бы имел оба ответа Алисы. После этого Боб может вычислить значение s, и ему будет известен секретный ключ Алисы.

Литература

• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. — 816 с. — ISBN 0-8493-8523-7

См. также

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