Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
15.2.4.2 Полное решение, полученное Фуджисаки и его соавторами 1
Вскоре после появления работы Шоупа Фуджисаки и его соавторы [114] об-J наружили способ инвертировать функцию RSA, не налагая на показатель степени никаких ограничений.
В схеме RSA-OAEP раскрытие Саймону числа s*, представляющего собой значительную часть прообраза зашифрованного текста с*, является слишком избыточным. Поскольку число s* состоит из к — fco бит и к > 2ко, более половины бит (причем старших) прообраза зашифрованного текста с* оказываются раскрытыми. Зная такую крупную часть прообраза, Фуджисаки с соавторами применили метод "бриллиантовой решетки", позволяющий найти число Т = I(t*) из уравнения ]
(2koI(s*) + Ту -- с*(mod N), (15.2.211
где число е может быть произвольно большим. Напомним, что алгоритм 9.1 инвертирует функцию RSA, log2 N раз применяя однобитовый оракул. Применим
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
точно такой же принцип, учитывая, что атакующий Л фактически является оракулом RSA, позволяющим ответить на вопрос: "Правда ли, что число s* содержит больше половины битов прообраза зашифрованного текста с*?". Используя алгоритм Фуджисаки, Саймон может дважды применить атакующий алгоритм Л и получить два связанных между собой блока (блоки "болыпе-половины-или-нет") частичной информации о прообразе. Эти два блока можно использовать в формуле (15.2.21) для поиска двух неизвестных целых чисел, которые меньше \/N. Одним из этих двух чисел является число T(f). Таким образом, Саймон инвертирует функцию RSA.
Поскольку Саймон применяет атакующий алгоритм Л дважды, он должен дважды разыграть с ним атаку, основанную на редукции: один раз Саймон посылает алгоритму Л число с*, а второй раз — число с* = с*ае (mod N), где а — случайное число, принадлежащее группе Щ^. Соответствующие числа s* и s* будут записаны в Я- и Я-списке соответственно. Пусть q — таж(#(Я-список),#(Я-список)). Работая с этими списками, Саймон будет хранить не более q2 пар (?, F). Одна из этих пар позволит Саймону решить два корректных уравнения, заданных формулой (15.2.21), и таким образом инвертировать функцию RSA, если число а было выбрано правильно (вероятность противоположного события пренебрежимо мала, так как в схеме RSA-OAEP к ^> 2ко). Поскольку решить два уравнения, заданных формулой (15.2.21), можно за Ов((к^2.ЛГ)3) единиц времени, оценка времени, необходимого для инвертирования функции RSA, имеет следующий вид.
2т + q2 х Os((log2 AO3) (15.2.22)
Здесь число т — время, необходимое атакующему Л для проведения атаки IND-ССА2 на схему RSA-OAEP.
Схема RSA-OAEP имеет еще два варианта дополнения параметра безопасности: PKCS#1 версии 2 и выше [230] и SET [259]. В этих вариантах известная порция данных s* размещается в разных местах исходного текста. Благодаря достаточно большому размеру числа s* (значительно превышающему половину размера блока), для извлечения корня достаточно не более двух раз вызвать атакующего. Итак, метод Фуджисаки распространяется и на эти два варианта.
Следовательно, схема RSA-OAEP и ее варианты являются доказуемо стойкими к атаке IND-CCA2.
В заключение отметим, что тот же результат применим и к схеме Рабин-ОАЕР. Следовательно, инверсия функции Рабина, т.е. извлечение квадратного корня по модулю N в произвольной точке, приводит к разложению модуля N на простые множители. Саймон может это сделать с помощью теоремы 6.17.3 (раздел 6.6.2), извлекая случайное число х и считая число с* результатом шифрования числа х с помощью функции шифрования Рабина. Схема Рабин-ОАЕР является более стойкой, чем схема RSA-OAEP, поскольку факторизация является более слабым условием, чем предположение, лежащее в основе схемы RSA.
576
Часть V. Методы формального доказательства стойкости
15.2.5 Неэффективность метода сведения
к противоречию для схемы RSA-OAEP
Схема RSA-OAEP весьма эффективна. Однако этого нельзя сказать о процесса "сведения к противоречию".
Выражение (15.2.22) означает время, необходимое Саймону-имитатору для] двойного применения атакующего алгоритма Л, чтобы инвертировать функции! RSA в произвольной точке. В это выражение входит квадратный член q2, гдч число q представляет собой количество запросов, которые атакующий алгоритм *А должен послать случайному оракулу Н.
Обратите внимание на то, что случайный оракул представляет собой идеализа-1 цию функции хэширования, допускающей очень эффективное вычисление. Такт»! образом, атакующий должен выполнить, скажем, 250 вычислений функции хэши-1 рования. Итак, можно считать, что q т 250. Следовательно, квадратичный член q4 в формуле (15.2.22) означает, что время, которое Саймон должен затратить для решения задачи RSA, имеет порядок
210°.OB((log2A03).
Как показано в разделе 4.6, время, необходимое для факторизации целого чисн] ла с помощью решетки числового поля (Number Field Sieve — NFS), выражается! формулой (4.6.1). При обычном размере числа \N\ = 1024 значение, вычисляемое! по формуле (4.6.1), равно приблизительно 286. Таким образом, если для фактори-1 зации применяется решетка числового поля, противоречие, выражаемое оценкой! 2100 - Og((log2 N)s), теряет смысл. Саймон может инвертировать функцию RSAJ основанную на 1024-битовом модуле, намного быстрее, не прибегая к помощи атакующего алгоритма Л. Таким образом, доказательство, основанное на "сведе-1 нии к противоречию" для 1024-битового модуля RSA, становится некорректным.]
