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

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

Сначала, как и в предыдущем примере, генерируется п, произведение двух больших простых чисел. Для ге­нерации открытого и закрытого ключей Пегги сначала выбирается к различных чисел: v_b v₂,... v_fo где каждое v, является квадратичным остатком mod п. Иными словами, v, выбираются так, чтобы х² = v, (mod n) имело ре-шение, и существовало v,"¹ mod п. Строка, v_b v₂,... v_k, служит открытым ключом. Затем вычисляются наи-меньшие s„ для которых s, = sqrt (v,"¹) (mod я). Строка,_ь s₂,... s_k, служит закрытым ключом.

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

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

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

(3) Пегги вычисляет у — г *(s_l^bl *s₂^bl*..*s_k^bk)mod п. (Она перемножает вместе значения s_t, соответствующие Ъг\. Если первым битом Виктора будет 1, то s_l войдет в произведение, а если первым битом будет 0, то нет, и т.д.) Она посылает у Виктору.

(4) Виктор проверяет, что х = у²*(v^bl * v₂^bl *.. *v_k^bk) mod n. (Он перемножает вместе значения v,, основываясь га случайной двоичной строке. Если его первым битом является 1, то vj войдет в произведение, а если первым битом будет 0, то нет, и т.д.)

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

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

Пример

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

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

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

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

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

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

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

16: х² - 16 (mod 35) имеет решения: х = 4, И, 24, 31.

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

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

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

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

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

v v"¹ 5=sqrt(v"¹)

И 16 4

16 И 9

29 29 8

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

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

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

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

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

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

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

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