Схема цифровой подписи и проверки подлинности, разработанная Амосом Фиатом (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 так, чтобы уравнение х2 = v (mod n) имело решение, и существовало vl mod п. Это v и будет открытым ключом Пегги. Затем вычисляется наименьшее s, для которого s = sqrt (v1) (mod я). Это будет закрытый ключ Пегги. Используется следующий протокол идентифи-кации.
(1) Пегги выбирает случайное г, меньшее п. Затем она вычисляет х =-r2 mod n и посылает х Виктору.
(2) Виктор посылает Пегги случайный бит Ъ.
(3) Если Ъ = 0, то Пегги посылает Виктору г. Если Ъ = 1, то Пегги посылает Виктору у = r*s mod n.
(4) Если Ъ = 0, Виктор проверяет, что х = -г2 mod я, убеждаясь, что Пегги знает значение sqrt(x). Если Ъ = 1, Виктор проверяет, что х = y2*v mod я, убеждаясь, что Пегги знает значение sqrt(v-1).
Это один этап протокола, называемый аккредитацией.Пегги и Виктор повторяют этот протокол t раз, пока Виктор не убедится, что Пегги знает s. Это протокол "разрезать и выбрать". Если Пегги не знает s, она может подобрать г так, что она сможет обмануть Виктора, если он пошлет ей 0, или она может подобрать г так, что она сможет обмануть Виктора, если он пошлет ей 1. Она не может сделать одновременно и то, и другое. Вероятность, что ей удастся обмануть Виктора один раз, равна 50 процентам . Вероятность, что ей удастся обмануть его граз,равна1/2(.
Виктор может попробовать вскрыть протокол, выдавая себя за Пегги . Он может начать выполнение протокола с с другим контролером, Валерией. На шаге (1) вместо выбора случайного г ему останется просто использовать значение г, которое Пегги использовало в прошлый раз. Однако, вероятность того, что Валерия на шаге (2) выберет то же значение Ъ, которое Виктор использовал в протоколе с Пегги, равна 1/2 . Следовательно, вероятность, что он обманет Валерию, равна 50 процентам. Вероятность, что ему удастся обмануть ее t раз, равна 1/2(.
Чтобы этот протокол работал, Пегги никогда не должна использовать г повторно. В противном случае, если Виктор на шаге (2) пошлет Пегги другой случайный бит, то он получит оба ответа Пегги . Тогда даже по одному из них он сможет вычислить s, и для Пегги все закончится.