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

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

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

(1) Алиса выбирает tслучайных целых чиселв диапазоне от 1 до n - r₁, r₂, . . ., r_t - и вычисляет x₁, x₂, . . . x_t, такие что x_i= r_i²mod n.

(2) Алиса хэширует объединение сообщения и строки x_i, создавая битовый поток: H(m, x₁, x₂, . . . x_t). Она использует первые k*t битов этой строки в качестве значений b_ij, где iпробегает от1 до t, а jот 1 до k.

(3) Алиса вычисляет y₁, y₂, . . . y_t,, где y_i= r_i*( ) mod n

(Для каждого i она перемножает вместе значения s_i, в зависимости от случайных значений b_ij. Если b_ij=1, то s_i участвует в вычислениях, если b_ij=0, то нет.)

(4) Алиса посылает Бобу m, все биты b_ij, и все значения y_i. У Боба уже есть открытый ключ Алисы: v₁, v₂, . . . v_k.

(5) Боб вычисляет z₁, z₂, . . . z_t, где z_i = y²*( )mod n

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

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

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