Схема подписи Fiat-Shamir

Превращение этой схемы идентификации в схему подписи - это, по сути, вопрос превращения Виктора в хэш-функциию. Главным преимуществом схемы цифровой подписи Fiat-Shamir по сравнению с RSA является ее скорость: для Fiat-Shamir нужно всего лишь от 1 до 4 процентов модульных умножений, используемых в RSA. В этом протоколе снова вернемся к Алисе и Бобу.

Смысл переменных - такой же, как и в схеме идентификации. Выбирается п - произведение двух больших простых чисел. Генерируется открытый ключ, v_b v₂,... v_fo и закрытый ключ, s_u s₂,... s_k, где s, = sqrt (v,-^-1) (mod и).

(1) Алиса выбирает t случайных целых чисел в диапазоне от 1 до п - г_ь г₂,..., г, - и вычисляет х_и х₂,... х„ такие что jc,-= r,² mod п.

(2) Алиса хэширует объединение сообщения и строки х„ создавая битовый поток: Щт, х_и х₂,... x_t). Она ис­пользует первые k*t битов этой строки в качестве значений Ь_у, где i пробегает от1 до t, aj от 1 до к.

(3) Алиса вычисляет у_ъу₂,...у„, где>-, = г, *(^" * s₂^ba *... *s_k^b*) mod n

(Для каждого i она перемножает вместе значения s„ в зависимости от случайных значений by. Если Ъ,_Г\, то St участвует в вычислениях, если Ь_у=0, то нет.)

(4) Алиса посылает Бобу т, все биты Ъ_ф и все значения у,. У Боба уже есть открытый ключ Алисы: v_b v₂,...

Vk-

(5) Боб вычисляет z_bz₂,... z„ где z, = у²*( v,⁶" * v₂"'² *.. *v_k^b'^k) mod n

(И снова Боб выполняет умножение в зависимости от значений by.) Также обратите внимание, что z, должно быть равно х,.

(6) Боб проверяет, что первые k*t битов Щт, z_b z₂,... z_t) - это значения by, которые прислала ему Алиса.

Как и в схеме идентификации безопасность схемы подписи пропорциональна 1/2^й Она также зависит от сложности разложения п на множители. Фиат и Шамир показали, что подделка подписи облегчается, если сложность разложения п на множители заметно меньше 2^й Кроме того, из-за вскрытия методом дня рождения (см. раздел 18.1), они рекомендуют повысить кЧ от 20 по крайней мере до 72, предлагая к = 9 и t = 8.