Схема идентификации Feige-Fiat-Shamir

В своих работах [544, 545], Фейге, Фиат и Шамир показали, как параллельная схема может повысить число аккредитаций на этап и уменьшить взаимодействия Пегги и Виктора.

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

Выполняется следующий протокол:

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

(2) Виктор посылает Пегги строку из k случайных битов: b₁, b₂, . . . b_k.

(3) Пегги вычисляет y= r*( )mod n. (Она перемножает вместе значения s_i, соответствующие b_i=1. Если первым битом Виктора будет 1, то s₁ войдет в произведение, а если первым битом будет 0, то нет, и т.д.) Она посылает yВиктору.

(4) Виктор проверяет, что x= y²*( )mod n. (Он перемножает вместе значения v_i, основываясь га случайной двоичной строке. Если его первым битом является 1, то v₁ войдет в произведение, а если первым битом будет 0, то нет, и т.д.)

Пегги и Виктор повторяют этот протокол tраз, пока Виктор не убедится, что Пегги знает s₁, s₂, . . . s_k.

Вероятность, что Пегги удастся обмануть Виктор tраз, равна 1/2^kt. Авторы рекомендуют использовать вероятность мошенничества 1/2²⁰ и предлагают значения k= 5 и t= 4. Если у вас склонность к мании преследования, увеличьте эти значения.

Пример

Взглянем на работу этого протокола небольших числах. Если n= 35 (два простых числа - 5 и 7), то возможными квадратичными остатками являются:

1: x²º 1 (mod 35) имеет решения: x= 1, 6, 29, 34.

4: x²º 4 (mod 35) имеет решения: x= 2, 12, 23, 33.

9: x²º 9 (mod 35) имеет решения: x= 3, 17, 18, 32.

11: x²º 11 (mod 35) имеет решения: x= 9, 16, 19, 26.

14: x²º 14 (mod 35) имеет решения: x = 7, 28.

15: x²º 15 (mod 35) имеет решения: x= 15, 20.

16: x²º 16 (mod 35) имеет решения: x= 4, 11, 24, 31.

21: x²º 21 (mod 35) имеет решения: x= 14, 21.

25: x²º 25 (mod 35) имеет решения: x= 5, 30.

29: x²º 29 (mod 35) имеет решения: x= 8, 13, 22, 27.

30: x²º 30 (mod 35) имеет решения: x= 10, 25.

Обратными значениями (mod 35) и их квадратными корнями являются:

Обратите внимание, что у чисел 14, 15, 21, 25 и 30 нет обратных значений mod 35, так как они не взаимно просты с 35. Это имеет смысл, так как должно быть (5 - 1) * (7 - 1)/4 квадратичных остатков mod 35, взаимно простых с 35: НОД(x, 35) = 1 (см. раздел 11.3).

Итак, Пегги получает открытый ключ, состоящий из k= 4 значений: {4,11,16,29}. Соответствующим закрытым ключом является {3,4,9,8}. Вот один этап протокола.

(1) Пегги выбирает случайное r=16, вычисляет 16²mod 35 = 11 и посылает егоВиктору.

(2) Виктор посылает Пегги строку случайных битов: {1, 1, 0, 1}

(3) Пегги вычисляет 16*(3¹*4¹*9⁰*8¹) mod 35 = 31 и посылает егоВиктору.

(4) Виктор проверяет, что 31²*(4¹*11¹*16⁰*29¹)mod 35 =11.

Пегги и Виктор повторяют этот протокол tраз, каждый раз с новым случайным r, пока Виктор будет убежден.

Небольшие числа, подобные использованным в примере, не обеспечивают реальной безопасности. Но когда длина nравна 512 и более битам, Виктор не сможет узнать о закрытом ключе Пегги ничего кроме того факта, что Пегги действительно знает его.

Улучшения

В протокол можно встроить идентификационные данные. Пусть I- это двоичная строка, представляющая идентификатор Пегги: имя, адрес, номер социального страхования, размер головного убора, любимый сорт прохладительного напитка и другая личная информация. Используем однонаправленную хэш-функцию H(x) для вычисления H(I,j), где j- небольшое число, добавленное к I. Найдем набор j, для которых H(I,j)- это квадратичный остаток по модулю n. Эти значения H(I,j)становятся v₁, v₂, . . . v_k(j не обязаны быть квадратичными остатками). Теперь открытым ключом Пегги служит Iи перечень j. Пегги посылает Iи перечень j Виктору перед шагом (1) протокола (или Виктор загружает эти значения с какой-то открытой доски объявлений), И Виктор генерирует v₁, v₂, . . . v_kиз H(I,j).

Теперь, после того, как Виктор успешно завершит протокол с Пегги, он будет убежден, что Трент, которому известно разложение модуля на множители, сертифицировал связь между Iи Пегги, выдав ей квадратные корни из v_i, полученные из I. (См. раздел 5.2.) Фейге, Фиат и Шамир добавили следующие замечания [544, 545]:

Для неидеальных хэш-функций можно посоветовать рандомизировать I, добавляя к нему длинную случайную строку R. Эта строка выбирается арбитром и открывается Виктору вместе с I.

В типичных реализациях kдолжно быть от 1 до 18. Большие значения kмогут уменьшитьвремя и трудности связи, уменьшая количество этапов.

Длина nдолжна быть не меньше 512 битов. (Конечно, с тех пор разложение на множители заметно продвинулось.)

Если каждый пользователь выберет свое собственное nи опубликует его в файле открытых ключей, то можно обойтись и без арбитра. Однако такой RSA-подобный вариант делает схему заметно менее удобной.