Упрощенная схема идентификации Feige-Fiat-Shamir

Перед выдачей любых закрытых ключей арбитр выбирает случайный модуль, n, который является произведением двух больших простых чисел. В реальной жизни длина nдолжна быть не меньше 512 битов и лучше как можно ближе к 1024 битам. nможет общим для группы контролеров. (Использование чисел Блюма (Blum) облегчит вычисления, но не является обязательным для безопасности.)

Для генерации открытого и закрытого ключей Пегги доверенный арбитр выбирает число v, являющееся квадратичным остатком mod n. Другими словами выбирается v так, чтобы уравнение x² º v(mod n) имело решение, и существовало v^-1mod n. Это vи будет открытым ключом Пегги. Затем вычисляется наименьшее s, для которого sº sqrt (v^-1) (mod n). Это будет закрытый ключ Пегги. Используется следующий протокол идентификации.

(1) Пегги выбирает случайное r, меньшее n. Затем она вычисляет x =-r²mod n и посылает xВиктору.

(2) Виктор посылает Пегги случайный бит b.

(3) Если b= 0, то Пегги посылает Виктору r. Если b= 1, то Пегги посылает Виктору y= r*smod n.

(4) Если b= 0, Виктор проверяет, что x= -r²mod n, убеждаясь, что Пегги знает значение sqrt(x). Если b= 1, Виктор проверяет, что x= y²*vmod n, убеждаясь, что Пегги знает значение sqrt(v^-1).

Это один этап протокола, называемый аккредитацией. Пегги и Виктор повторяют этот протокол tраз, пока Виктор не убедится, что Пегги знает s. Это протокол "разрезать и выбрать". Если Пегги не знает s, она может подобрать r так, что она сможет обмануть Виктора, если он пошлет ей 0, или она может подобрать r так, что она сможет обмануть Виктора, если он пошлет ей 1. Она не может сделать одновременно и то, и другое. Вероятность, что ей удастся обмануть Виктора один раз, равна 50 процентам. Вероятность, что ей удастся обмануть его tраз, равна 1/2^t.

Виктор может попробовать вскрыть протокол, выдавая себя за Пегги. Он может начать выполнение протокола с с другим контролером, Валерией. На шаге (1) вместо выбора случайного r ему останется просто использовать значение r, которое Пегги использовало в прошлый раз. Однако, вероятность того, что Валерия на шаге (2) выберет то же значение b, которое Виктор использовал в протоколе с Пегги, равна 1/2. Следовательно, вероятность, что он обманет Валерию, равна 50 процентам. Вероятность, что ему удастся обмануть ее tраз, равна 1/2^t.

Чтобы этот протокол работал, Пегги никогда не должна использовать r повторно. В противном случае, если Виктор на шаге (2) пошлет Пегги другой случайный бит, то он получит оба ответа Пегги. Тогда даже по одному из них он сможет вычислить s, и для Пегги все закончится.