Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
559
Эти три наблюдения имеют смысл, только если тексты, полученные путем рандомизированного заполнения, обладают достаточно хорошим случайным распределением в пространстве входных данных схемы OWTP.
Формальное доказательство схемы шифрования ОАЕР основано на мощном методе, называемом моделью случайного оракула (random oracle model). Такое доказательство предполагает, что функции хэширования, использованные в конструкции схемы ОАЕР, носят совершенно случайный характер. Эти функции называются случайными оракулами (random oracle) (их свойства описаны в разделе 10.3.1.2). Если функции хэширования, использованные в схеме заполнения, являются случайными оракулами, результат заполнения (т.е. случайные входные данные схемы OWTP) должен иметь равномерное распределение. Следовательно, интуитивно ясно, что этот способ приводит к результатам, полученным в главе 9.
Точнее говоря, целью доказательства стойкости схемы OAEP-OWTP, основанного на модели случайного оракула (ROM-based), является создание эффективного преобразования (называемого редукцией (reduction)) преимущества атаки на схему шифрования OAEP-OWTP в аналогичное преимущество инвертирования соответствующей перестановки OWTP (с точностью до полинома). Например, если перестановка OWTP является функцией RSA, инверсия решает задачу RSA или нарушает предположение о ее неразрешимости (определение 8.4, предположение 8.3 в разделе 8.7). Поскольку считается, что эффективного алгоритма инвертирования перестановки OWTP не существует, создание эффективного преобразования редукции приводит к противоречию. Доказательство, построенное таким образом, называется сведением к противоречию (reduction to contradiction).
15.2.1 Доказательство стойкости с помощью модели случайного оракула
Понятие случайного оракула введено в разделе 10.3.1.2. Случайный оракул представляет собой мощную гипотетическую детерминированную функцию, эффективно вычисляющую равномерно распределенные случайные величины.
Белларе и Роджуэй использовали эти свойства для доказательства стойкости схемы шифрования ОАЕР [24]. Их доказательство называется моделью случайного оракула (ROM) [22].
В модели ROM предполагается существование не только случайного оракула, но и специального агента, Саймона-имитатора, с которым мы уже встречались в разделе 14.5.4. Предполагается, что Саймон-имитатор может имитировать любого случайного оракула (даже Злоумышленника). Итак, если кто-либо захочет применить случайного оракула, скажем, оракула G, к числу а, он автоматически пошлет Саймону так называемый запрос случайному оракулу (random oracle
560
Часть V. Методы формального доказательства стойкости
query) и получит от него результат G(a). Саймон всегда честно выполняет любой запрос и возвращает его результат.
Благодаря этому правилу Саймон может точно имитировать поведение случайного оракула. Попробуем разобраться, как это ему удается.
Для оракула G, например, Саймон поддерживает G-список, содержащий все пары (a,G(a)), где хранятся все предшествующие запросы а. Имитация выполняется довольно просто: получив запрос а, Саймон проверяет, хранится ли он в списке. Если есть, Саймон просто возврашает значение G(a) (вот почему результат запроса называется детерминированным), в противном случае Саймон извлекает из генеральной совокупности равномерно распределенных чисел новую величину G(a), возвращает ее в качестве ответа на запрос (вот почему он называется равномерным) и заносит пару (a, G(a)) в список, упорядоченный по первому элементу пары. Дополнительный алгоритм сортировки списка применять необязательно, поскольку каждый список инициализируется как пустой и растет по мере выполнения запросов. При получении очередного запроса поиск элемента в списке, состоящем из N записей, можно выполнить за log N единиц времени (см. алгоритм 4.4), т.е. за полиномиально ограниченное время (вот почему имитатор называется эффективным).
Лемма 15.1. Случайный оракул точно имитируется полиномиально ограниченным алгоритмом. о
В схеме шифрования с открытым ключом, использующей случайных оракулов (например, в схеме OWTP-OAEP), этот способ имитации позволяет Саймону построить однозначное отображение исходного текста в зашифрованный текст (например, в схеме OWTP-OAEP Саймон создает отображение, заданное формулой (15.2.1)). Если атакующий, например, Злоумышленник, хочет создать корректный подобранный зашифрованный текст с, применяя OWTP-перестановку /, он должен обратиться к Саймону за расшифровкой. Следовательно, Саймон способен расшифровать сообщение с, даже не владея тайной информацией, позволяющей инвертировать функцию /. Это довольно просто, поскольку Саймон поддерживает список пар, состоящих из исходных и зашифрованных текстов. Действительно, если зашифрованный текст является корректным, он должен содержаться в списке случайного оракула.
Следовательно, кроме случайных оракулов, Саймон может имитировать оракулов расшифровки4, например, оракула О в протоколах 14.3. и 14.4. Это еще одна причина, по которой наш специальный агент называется Саймоном-имитатором.
