Feige-fiat-shamir

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

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

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

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

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

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

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

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

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

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

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

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

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

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