Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Рассмотрим теперь протокол, использующий цифровую подпись. Пусть Za9 tA обозначают соответственно случайное число и метку времени доказывающего Af Sa обозначает алгоритм цифровой подписи А. Будем считать, что алгоритм проверки цифровой подписи доказывающего известен проверяющему.
Для идентификации могут быть использованы следующие три протокола.
1. Односторонняя идентификация с использованием временных меток:
О) A^B:tA,id(B),sA(tA,id(B)).
Получив сообщение, пользователь В проверяет, что временная метка находится в допустимом интервале, id (В) совпадает с его собственным идентификатором, а также то, что цифровая подпись под этими двумя полями верна.
2. Односторонняя идентификация с использованием случайных чисел:
(1) А <— В : zB9
(2) А -> В: zA, id (В), Sa (za , zB, id (В)).
340
Идентификация
Получив сообщение, пользователь В проверяет, что id (В) соответствует его идентификатору и что цифровая подпись под строкой (zA, zb, id (В)) верна.
3. Взаимная идентификация с использованием случайных чисел:
(1) A<—B:zB9
(2) А-+В: zA,id(B),SA(zA,zB,id(B)),
(3) А <- В :id(A),SB(zH,zA,id(A)).
§ 12.4. Протоколы с нулевым разглашением
Недостатком протоколов с фиксированным паролем является то, что доказывающий А передает проверяющему В свой пароль, вследствие чего В может в последующем выдать себя за А. Протоколы типа “запрос-ответ” ликвидируют этот недостаток. При их выполнении А отвечает на запросы B9 меняющиеся во времени, не давая В информации, которую тот может использовать, чтобы выступать от имени А. Тем не менее А может выдать некоторую частичную информацию о своем секрете.
Протоколы с нулевым разглашением призваны решить эту проблему, давая возможность доказывающему продемонстрировать знание секрета, не выдавая о нем никакой информации. Точнее говоря, выдается только один бит информации, обозначающий то, что доказывающий знает секрет.
В протоколах с нулевым разглашением термин “доказательство” имеет смысл, отличный от традиционно принятого в математике. Доказательство имеет вероятностный характер. Это означает, что утверждение имеет место с некоторой вероятностью, которая может быть выбрана сколь угодно близкой к единице.
Примером такого протокола является протокол Фиата — Шамира. Он основывается на сложности задачи извлечения квадратного корня по модулю большого составного числа п с неиз-
341
І лава 12
вестным разложением на множители. Как известно, эта задача эквивалентна задаче разложения числа п на множители.
А доказывает В знание секрета s с помощью t итераций следующего трехшагового протокола.
Доверенный центр T выбирает модуль n=pq и сообщает его всем доказывающим. При этом числар и q остаются секретными.
Каждый доказывающий А выбирает секрет S9 которым является число, взаимно простое с п, I < s < п - 1, вычисляет значение v = S2 mod п и объявляет v своим открытым ключом.
Следующие три шага производятся независимо t раз, причем В принимает доказательство владения А секретом s, если все эти итерации приводят к положительному ответу.
1. А выбирает случайно Z9 I <z<п- \9 и посылает В число х = Z2 mod п.
2. В случайно выбирает бит с и направляет его А.
3. А вычисляет и направляет В число у, равное либо z, если с =
О, либо zs mod п, если с - 1.
В дает положительный ответ, если у Ф 0 и
у2 = XVе (mod п).
Заметим, что в зависимости от значения бита с выполнено одно из двух условий: у2 = x(mod п) или у2 = xv(mod п), так как V = S2 (modп). Проверка равенства ^ = O исключает случай z = 0.
Корректность протокола может быть обоснована следующими рассуждениями.
Наличие запроса с требует, чтобы А был в состоянии ответить на любой из двух вопросов, ответ на один из которых требует знания секрета S9 а ответ на другой предотвращает попытку обмана. Противник, выдающий себя за A9 может попытаться обмануть проверяющего, выбрав любое число z и передав В число х = Z2Iv.
342
Идентификация
Тогда он сможет ответить на запрос “с = 1”, направив правильный ответ “у = z”, но не сможет ответить на запрос “с = 0”, ответ на который требует знания корня квадратного из числах по модулю п.
Доказывающий A9 знающий s, в состоянии ответить на оба вопроса. Если же он не знает S9 то в лучшем случае — на один из двух вопросов. Таким образом, обман удается с вероятностью, не превышающей 1/2. При /-кратной итерации протокола вероятность обмана может быть доведена до величины, не превышающей 2 .
Ответ “у = z” не зависит от секрета s доказывающего A9 а ответ У = zs mod я” также не несет информации о S9 так как случайное z не известно проверяющему В.
Идеи, лежащие в основе протоколов с нулевым разглашением, могут быть сформулированы следующим образом.
Доказывающий А выбирает случайный элемент из заранее оговоренного множества, как свой секретный ключ для данной итерации протокола, вычисляет, используя его как аргумент некоторой однонаправленной функции, ее значение, и предъявляет это значение проверяющему. Этим обеспечивается случайность и независимость различных итераций протокола и определяется набор вопросов, на каждый из которых доказывающий готов дать ответ. Протокол построен так, что только доказывающий A9 владеющий секретом S9 в состоянии ответить на все эти вопросы, и ни один ответ не дает информации о секрете. На следующем этапе В выбирает один из этих вопросов и А дает на него ответ, который затем проверяется В. Осуществляется необходимое число итераций протокола с целью снизить до приемлемого уровня вероятность обмана.
