Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 245

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 239 240 241 242 243 244 < 245 > 246 247 248 249 250 251 .. 311 >> Следующая

606
Часть V. Методы формального доказательства стойкости.
Схема подписи и открытый ключ
3 л о
У м ы ш л е и н и к
курс обучения
Умелая подделка
Схема подписи и открытый ключ
Случайные оракулы
Решение
трудноразрешимой задачи
Имитация случайных оракулов
Рис. 16.1. Сведение подделки подписи к решению трудноразрешимой задачи
информации для вычисления дискретного логарифма. Интуиция подсказываеЯ что число у должно быть произвольным, в противном случае редукция становитс! бесполезной.
Допустим, что вероятность успешной подделки равна Adv(fc), где число к является значимой величиной, а время, затраченное Злоумышленником на подделк)! ограничено полиномом t(k), зависящим от параметра к. Вычислим вероятности Adv' (к), с которой Саймон находит дискретный логарифм, и время его работа f/(/c). Разумеется, пары (t(k), Adv(/c)) и (t'(k), Adv'(fc)) связаны между собой. '
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
607
Многократные вызовы Злоумышленника на первом этапе
Саймон вызывает Злоумышленника 1/Adv(fc) раз. Поскольку Злоумышленник считается успешным фальсификатором, при некоторых условиях (каких — уточним позднее) он с вероятностью, равной единице (поскольку его алгоритм выполняется 1/Adv(fc) раз), выдаст корректную подпись (r,e, s) сообщения М в схеме (Gen, Sign, Verify). Иначе говоря,
е = Я(М,г), yrrs = <7e(modp).
где |е| = к.
При этом Злоумышленник должен несколько раз вычислить функцию хэширования Н. В модели ROM, продемонстрированной на рис. 16.1, Злоумышленник должен послать Саймону запросы, предназначенные для случайного оракула. В ответ Саймон играет роль случайного оракула: имитирует функцию хэширования Н, поддерживая /f-список, содержащий элементы ((Л/*,г$),е$), упорядоченные по сообщениям Здесь пары (A/j,r-j) представляют собой запросы, а число ei — случайные ответы.
Поскольку Злоумышленник полиномиально ограничен, он может послать случайному оракулу лишь п — qjj запросов, где величина </# — значение полинома, зависящего от параметра к. Пусть пары
Qi = (MbnJ.Qa - (M2,r2),-..-Qn = (Mn,rn) (16.3.1)
представляют собой п запросов случайному оракулу, посланных Злоумышленником. Кроме того, пусть числа
R\ ' ei, Я2 = е2,..., Rn = еп
обозначают п ответов, полученных от Саймона. Поскольку \Н| = к, ответы Саймона равномерно распределены по множеству {1.2,3,..., 2fc}.
Благодаря этому свойству, если Злоумышленнику удалось подделать подпись (г, е, s) на сообщении М, он должен послать запрос (М, г) и получить ответ е = = (М,г). Иначе говоря, при некотором г € [1,п] должно выполняться условие (Л/,г) = (M{,ri). Вероятность того, что пара (М. г) не будет послана в виде запроса, равна 2~к. (Это число представляет собой вероятность того, что Злоумышленник правильно угадает случайный ответ Саймона Ri = е,-, не посылая ему запроса.) Считая величину 2~к пренебрежимо малой, можно утверждать, что пара ((Л/, г), е) принадлежит /f-списку Саймона.
Следует иметь в виду одно важное обстоятельство: без запроса, посланного Саймону, и его ответа, Злоумышленник не может подделать подпись. Вероятность противоположного события равна 2~к, т.е. пренебрежимо мала. Учитывая это, можно считать, что Злоумышленник "вынужден" подделывать подпись одного из п сообщений в списке (16.3.1).
608
Часть V. Методы формального доказательства стойкости
Qb+i Q n
• - • - -»- (M, r, e. s)
Q2 Qb / R„
Qi Rb
• и
Ri \
R'b
Ю • .... • (M,r,e \s')
R'n
Qb = №r) Rb = e 4 - e
Рис. 16.2. Успешное разветвление ответов на запросы случайному оракулу
Многократные вызовы Злоумышленника на втором этапе
Саймон снова вызывает Злоумышленника 1 / Adv(/c) раз при тех же условиях. Иначе говоря, повторяются п запросов, перечисленных в списке (16.3.1). Однако на этот раз Саймон создает п других случайных ответов, имеющих равномерное распределение.
Необходимо подчеркнуть, что, поскольку ответы по-прежнему равномерно распределены по множеству {1,2,3,..., 2к}, они остаются правильными.
Получив вторую порцию ответов, Злоумышленник должен снова проявить все свои способности и с вероятностью, равной единице, создать корректную nonJ пись (г', е', s') сообщения М'. Как и в первый раз, пара (М', г') должна совпадать с одной из пар Qj в списке (16.3.1) при некотором j € [1,п]. Вероятность против воположного события равна 2~к.
На рис. 16.2 проиллюстрировано "успешное разветвление запросов Злоумышленника". Это событие происходит, когда в обоих сеансах вызова Злоумышлении-1 ка пары поддельных пар сообщение-подпись (М, (r,e, s)) и (М', (r',e',s')) удо-| влетворяют условию (М, г) — (М', г'). Заметим, что в каждом из сеансов выполнения алгоритма Злоумышленник может подделать подпись для пары (М$, г,), где г € i/[l,п] — случайное число, имеющее равномерное распределение и не должно фиксироваться. Применяя парадокс дней рождения (см. раздел 3.6), получаем, что вероятность этого события (т.е. г = j = b) приблизительно равна 1/у/п. Следует иметь в виду, что, если число г во втором сеансе фиксировано, вероятность успешного разветвления равна 1/п.
Предыдущая << 1 .. 239 240 241 242 243 244 < 245 > 246 247 248 249 250 251 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed