Схемы идентификации 21.1 FEIGE-FIAT-SHAMIR

Схема цифровой подписи и проверки подлинности, разработанная Амосом Фиатом (Amos Fiat) и Ади Шамиром (Adi Shamir), рассматривается в [566, 567]. Уриель Фейге (Uriel Feige), Фиат и Шамир модифицировали алгоритм, превратив его в доказательство подлинности с нулевым знанием [544, 545]. Это лучшее доказательство подлинности с нулевым знанием.

9 июля 1986 года три автора подали заявку на получение патента США [1427]. Из-за возможного военного применения заявка была рассмотрена военными. Время от времени результатом работы Патентное бюро явл я-ется не выдача патента, а нечто, называемое секретным распоряжением . 6 января 1987 года, за три дня до истечения шестимесячного периода, по просьбе армии Патентное бюро издало такое распоряжение . Заявило, что " . . . раскрытие или публикация предмета заявки . . . может причинить ущерб национальной безопасности . . Авторам было приказано уведомить всех граждан США, которые по тем или иным причинам узнали о пров о-димых исследованиях, что несанкционированное раскрытие информации может закончиться двумя годами т ю-ремного заключения, штрафом $10,000 или тем и другим одновременно. Более того, авторы должны б1ли сообщить Уполномоченному по патентам и торговым знакам обо всех иностранных гражданах, которые получили доступ к этой информации.

Это б1ло нелепо. В течение второй половины 1986 года авторы представляли свою работу на конференциях в Израиле, Европе и Соединенных Штатах. Они даже не были американским гражданами, и вся работа была выполнена в Институте Вейцмана (Weizmann) в Израиле.

Слухи об этом стали распространяться в научном сообществе и прессе . В течение двух дней секретное распоряжение было аннулировано. Шамир и его коллеги считают, что за отменой секретного распоряжения стояло NSA, хотя никаких официальных комментариев не было. Дальнейшие подробности этой причудливой истории приведены в [936].

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

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

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

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

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

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

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

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

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

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

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

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

Сначала, как и в предыдущем примере, генерируется n, произведение двух больших простых чисел. Для генерации открытого и закрытого ключей Пегги сначала выбирается k различных чисел: vi, v2, . . . vk, где каждое V,- является квадратичным остатком mod n. Иными словами, v,- выбираются так, чтобы x2 = v,- (mod n) имело решение, и существовало v,-1 mod n. Строка, v1, v2, . . . vk, служит открытым ключом. Затем вычисляются наименьшие Si, для которых Si = sqrt (v,-1) (mod n). Строка s1, s2, . . . sk, служит закрытым ключом.

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

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

(2) Виктор пос1лает Пегги строку из k случайных битов: b1, b2, . . . bk.

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

(4) Виктор проверяет, что x = y2*( v1b1 * v2 b2 *K*vkbk) mod n. (Он перемножает вместе значения v,, основываясь га случайной двоичной строке. Если его первым битом является 1, то v1 войдет в произведение, а если первым битом будет 0, то нет, и т.д.)

Пегги и Виктор повторяют этот протокол t раз, пока Виктор не убедится, что Пегги знает s1, s2, . . . sk.

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

Обратными значениями (mod 35) и их квадратными корнями являются: vv-1 s=sqrt(v-1)

493 942

11 16 4

16 11 9

29 29 8

Обратите внимание, что у чисел 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, вычисляет 162 mod 35 = 11 и посылает его Виктору.

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

(3) Пегги вычисляет 16*(31*41*90*81) mod 35 = 31 и посылает его Виктору.

(4) Виктор проверяет, что 312*(41*111*160*291) mod 35 =11.

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

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

Улучшения

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

ный остаток по модулю n. Эти значения становятся v1, v2, . . . vk (/ не обязаны быть квадратичными остат-

ками). Теперь открытым ключом Пегги служит 1 и перечень j. Пегги пос1лает 1 и перечень j Виктору перед шагом (1) протокола (или Виктор загружает эти значения с какой-то открытой доски объявлений ), И Виктор генерирует v1, v2, . . . vk из Я(/,/).

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

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

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

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

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

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

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

Смысл переменных - такой же, как и в схеме идентификации . Выбирается n - произведение двух больших простых чисел. Генерируется открытый ключ, v1, v2, . . . vk, и закрытый ключ, s1, s2, . . . sk, где s,- = sqrt (v,--1) (mod

(1) Алиса выбирает t случайных целых чисел в диапазоне от 1 до n - r1, r2, . . rt - и вычисляет x1, x2, . . . xt, такие что x; = r,2 mod n.

(2) Алиса хэширует объединение сообщения и строки x,, создавая битовый поток: x1, x2, . . . xt). Она использует первые k*t битов этой строки в качестве значений b,/, где , пробегает от1 до t, а j от 1 до k.

(3) Алиса вычисляет y1, y2, . . . yt„ где = Г; *(s1b1 * s2b"2 *K*skb"k) mod n

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

(4) Алиса посылает Бобу m, все биты b,/, и все значения у,. У Боба уже есть открытый ключ Алисы: v1, v2, . . . vk-