Модифицированный протокол Фиата-Шамира

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

.

Эти значения предоставляются А в ЦСК. Так как ЦСК знает секретное разложение , он может легко вычислить значения . Протокол заключается в выполнении следующих шагов.

1) А передает на компьютер. Компьютер вычисляет ;

2) А выбирает случайное секретное число , вычисляет и передает на компьютер;

3) компьютер выбирает случайную строку из бит , и передает эту строку А;

4) А вычисляет , передает на компьютер;

5) компьютер проверяет равенство

.

Шаги протокола 2)-5) могут быть повторены раз. Если все сравнений из п.5) выполнены, то А получает доступ.

Доказано, что если все элементы попарно различны при , то попытка противника выдать себя за А будет иметь вероятность успеха . С другой стороны, легко показать, что если не является однонаправленной, то противник может выдать себя за А.