Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Поскольку указанный модуль считается безопасным для применения во мно-1 гих прикладных системах, некорректность доказательства стойкости схемы RSA-J ОАЕР свидетельствует о недостаточно высокой степени полинома.
Доказательство, основанное на "сведении к противоречию", становится корректным, если модуль состоит из 2048 бит. В этом случае формула (4.6.1) имеет! порядок 2116.
15.2.6 Критика модели случайного оракула
Канетти (Canetti), Годцрайх (Goldreich) и Халеви (Halevi) высказали негативное отношение к доказательствам, основанным на применении модели случайного оракула [64, 65]. Они продемонстрировали, что существуют схемы цифровой подписи и шифрования, доказуемо стойкие в рамках модели случайного оракула, но
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
577
уязвимые при реализации в реальных приложениях. Их основная идея заключалась в изобретении плохих схем цифровой подписи или шифрования. В обычных условиях эти схемы работают хорошо, но при некоторых условиях (в основном, при нарушении случайности) становятся плохими.
Очевидно, что доказательство стойкости плохих схем в рамках модели случайного оракула остается корректным, поскольку исходный текст, подлежащий подписанию или шифрованию, является равномерно распределенным. Однако в реальных приложениях равномерное распределение остается недостижимой целью, и, следовательно, реальные приложения являются уязвимыми.
Способ, которым авторы строили свои схемы, довольно сложен. Заинтересованные читатели найдут его описание в работе [65].
Однако, рассмотрев элегантные и убедительные научные аргументы, интересно обнаружить, что эти три автора пришли к разным выводам относительно полезности модели случайного оракула. Они решили не скрывать своих разногласий и сформулировали свои выводы по отдельности.
Канетти (раздел 6.1 в работе [65]) придерживается наиболее скептичной точки зрения. Он считает, что модель случайного оракула представляет собой неудачную абстракцию и снижает ценность метода "сведения к противоречию". Канетти предложил в качестве альтернативы направить научные исследования на поиск специфических полезных свойств модели случайного оракула.
Вывод Голдрайха (раздел 6.2 в работе [65]) является умеренно пессимистичным. Он считает, что проблема заключается в неполноте модели случайного оракула и рекомендует не включать в работы доказательства, использующие этот метод. Иначе говоря, такие доказательства нельзя считать корректными. Однако окончательный вывод Голдрайха довольно оптимистичен: он полагает, что модель случайного оракула имеет определенную ценность для проверки криптосистем на прочность. Голдрайх выразил надежду, что в будущем эта модель будет усовершенствована.
Вывод Халеви (раздел 6.3 в работе [65]) основан на использовании события, имеющего значимую вероятность. Он полагает, что нынешние успехи метода сведения к противоречию являются случайными: "нет никаких оснований утверждать, что все существующие схемы, стойкость которых доказана с помощью модели случайного оракула, в действительности являются стойкими". Халеви считает, что лучше иметь доказательства стойкости современных стандартных схем, полученные с помощью модели случайного оракула, чем не иметь никакого доказательства.
578
Часть V. Методы формального доказательства стойкости
15.2.7 Авторская точка зрения на ценность модели случайного оракула
Автор придерживается собственного мнения на этот счет. Для того чтобы сохранить объективность при обсуждении результатов, изложенных в главе, рассмотрим аргументы, касающиеся схемы RSA-OAEP.
Доказательство стойкости модели RSA-OAEP в рамках модели случайного оракула основано на следующем факте.
Если схема заполнения является истинно случайной функцией, то результатом заполнения с помощью схемы ОАЕР является "идеальный исходный текст": он имеет равномерное распределение в пространстве исходных текстов функции RSA. Таким образом, исследование стойкости функции RSA, используемой в идеальном мире (см. раздел 9.2), показывает, что легче всего преодолеть защиту от атаки IND-CCA2, решив задачу RSA и применив алгоритм расшифровки.
Итак, доказательство, основанное на модели случайного оракула, предполагает, что схема шифрования путем заполнения использует идеальную функцию хэширования, а не случайного оракула, причем наиболее уязвимым местом длА] проведения атаки является именно функция хэширования. Для того чтобы достичь высокой стойкости схемы шифрования путем заполнения, необходимо уделитя большое внимание разработке функции хэширования и обеспечению случайное сти входных данных.
С этой точки зрения модель случайного оракула имеет большое значение, поскольку она фокусирует внимание именно на этих проблемах.
15.3 Криптосистема с открытым ключом Крамера-Шоупа
Другой широко известной эффективной криптосистемой с открытым ключом, стойкой в атаке IND-CCA2, является криптосистема Крамера-Шоупа (Cramer€ Shoup) [84].
15.3.1 Доказуемая стойкость при стандартных
предположениях о неразрешимости задачи
Выше рассмотрена общая методология формального доказательства стойкости, заключающегося в "сведении" атаки на криптографическую систему к реше^ нию общепризнанно трудноразрешимой задачи (т.е. атакующий алгоритм изобра-' жается черным ящиком, решающим трудную задачу). Это доказательство, осно^ ванное на "сведении к противоречию" обладает двумя полезными свойствами.
