Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
563
(Fujisaki) и его соавторами [114], позволил найти правильный способ применения функции RSA в схеме ОАЕР.
Рассмотрим эту драматическую ситуацию. Начнем с изучения оригинального доказательства стойкости, приведенного Белларе и Роджуэем. Затем будет приведено замечание Шоупа, демонстрирующее дефект в этом доказательстве. В заключение излагается работа Фуджисаки и его соавторов, спасающая положение. (Шоуп также разработал специальный вариант спасения, который мы рассмотрим в свое время.)
15.2.3.1 Редукция, основанная на модели случайного оракула
Предположим, что атакующий А, которые выполняет алгоритм РРТ, имеет значимое преимущество взлома схемы /-ОАЕР с помощью атаки IND-CCA2. Сконструируем алгоритм, позволяющий специальному агенту Саймону-имитатору использовать атакующего А для инвертирования функции /-OWTP со значимым преимуществом. Этот алгоритм должен быть эффективным (т.е. полиномиальным). Таким образом, Саймон эффективно "сводит" задачу инвертирования функции / к способности атакующего А взломать схему /-ОАЕР. По этой причине алгоритм, используемый Саймоном, называется полиномиальной редукцией (polynomial-time reduction). Поскольку алгоритмы, которые выполняют атакующий А и Саймон, являются полиномиальными, инвертирование функции / также выполняется за полиномиальное время. Считается, что инвертирование функции / невозможно вьтолнить за полиномиальное время. Это противоречит предположению о том, что атакующий А способен организовать успешную атаку IND-ССА2 на функцию /-ОАЕР (см. раздел 15.2.5). Такое доказательство стойкости называется редукционным (reductionist proof).
Рассмотрим процесс редукции.
Допустим, что Саймон имеет описание функции OWTP / и точку с* из области равномерно распределенных значений функции /. Саймон желает вычислить значение /-1(с*), используя организатора атаки IND-CCA2 А. Следует заметить, что точка с* должна быть случайной: если это условие не выполняется, результат алгоритма, выполняемого Саймоном, будет бесполезным.
Схематичное описание алгоритма редукции
Процесс редукции показан на рис. 15.2.3.2. Как видим, Саймон имеет доступ ко всем линиям, связывающим атакующего А с внешним миром, так что атакующий А может общаться только с Саймоном.
• Сначала Саймон посылает атакующему А описание алгоритма шифрования /-ОАЕР.
• Затем Саймон начинает с атакующим А игру IND-CCA2 (т.е. запускает протокол 14.4). В этой игре Саймон имитирует оракула расшифровки О. Как будет показано далее, в рамках модели случайного оракула Саймон
564
Часть V. Методы формального доказательства стойкости
Схема шифрования и открытый ключ
Курс обучения криптоанализу
"о- "i
Курс обучения криптоанализу
Осмысленное угадывание
Схема шифрования и открытый ключ
Случайные оракулы
Имитация курса
обучения криптоанализу ^~
те. т,
Имитации курса
обучения криптоанализу
С а й
м о и
/• OWTP
с . случайная точка
Осмысленное угадывание
Имитация случайных оракулов
Рис. 15.3. Редукция задачи инвертирования однонаправленной функции с секретом f к атаке на схему f-OAEP
действительно может имитировать оракула расшифровки О, не вызывая подозрений у атакующего Л.
• Саймон предоставляет атакующему Л поддельные услуги, имитируя случайных оракулов G и Я, задействованных в схеме ОАЕР (см. рис. 15.1).
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
565
Как указано в разделе 15.2.1, как только атакующему понадобится помощь оракулов G и/или Н (например, при подборе зашифрованного текста), он пошлет запрос Саймону и получит соответствующие ответы.
Чрезвычайно важным обстоятельством является тот факт, что имитирование, выполняемое Саймоном, должно быть точным, чтобы атакующий Л ничего не заподозрил. Только в этом случае атакующий получит полный объем знаний и облегчит свою задачу. Атака IND-CCA2, разыгранная между Саймоном и атакующим А, развивается следующим образом.
1. На "этапе поиска" Симон получает для расшифровки индифферентно подобранные зашифрованные тексты, посланные атакующим А. Эти тексты могут быть выбраны атакующим А по своему усмотрению, однако, если он хочет, чтобы зашифрованные тексты были подобраны правильно, т.е. с помощью случайных оракулов, запросы следует направлять Саймону. (Как показано на рис. 15.2.3.2, Саймон контролирует все каналы, связывающие атакующего А с внешним миром.) Методы имитации, применяемые Саймоном, будут описаны позднее.
2. Поскольку Саймон получает от атакующего А подобранные тексты, подлежащие расшифровке, он должен отвечать, имитируя блок расшифровки (оракула О). Детали будут описаны в свое время.
3. Атакующий А завершает "этап поиска", посылая Саймону пару подобранных исходных текстов то, т\. Получив эти тексты, Саймон "подбрасывает монету" Ъ G гу{0,1} и посылает атакующему А зашифрованный оклик с*, представляющий собой сообщение ть, зашифрованное с помощью имитированного алгоритма шифрования /-ОАЕР. Саймон считает, что зашифрованный текст с* шифрует сообщение ть-
4. Теперь атакующий А находится на "этапе угадывания". Следовательно, он может посылать адаптивно подобранные зашифрованные тексты, проходя "расширенный курс обучения криптоанализу". Саймон реагирует так, как показано в п. 2. Если атакующий А посылает запросы случайным оракулам, пытаясь создать адаптивно подобранные зашифрованные тексты, Саймон должен отвечать на них так, как показано в п. 1.
