Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
4Не следует путать оракула расшифровки и случайного оракула. Это совершенно разные понятия. Оракул расшифровки вполне реален, например, его роль может играть наивный пользователь, вынужденный расшифровывать сообщения Злоумышленника, а случайный оракул представляет собой гипотетическую функцию.
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
561
Имитируемая возможность расшифровки позволяет Саймону организовать "курс обучения криптоанализу" для Злоумышленника в рамках атаки IND-ATK (напомним, что сокращение АТК означает CPA, ССА или ССА2).
Если "курс обучения" выполняется точно, Злоумышленник должен успешно взламывать схему шифрования со значимым преимуществом и за относительно короткое время (полиномиальное). Иначе говоря, при атаке IND-ATK Злоумышленник должен связать один из двух подобранных зашифрованных текстов с зашифрованным окликом. Затем Симон, контролирующий случайных оракулов, также успешно завершит инвертирование криптографической функции, примененной к зашифрованному оклику: пару (исходный текст, зашифрованный оклик) можно найти в списке имитируемых случайных оракулов. Детали этого приема описаны в разделе 15.2.3.1. В следующей главе будет также описан трюк, позволяющий доказать стойкость некоторых цифровых схем с помощью модели случайных оракулов.
Все это хорошо, однако действует только в идеальном мире, в котором существуют случайные оракулы!
Несмотря на это, благодаря точной имитации поведения случайных оракулов с помощью криптографических функций хэширования схема шифрования ОАЕР оказалась вполне пригодной для практического применения. Хотя предположение об имитации случайных оракулов является недоказанным, его широко применяют на практике. В конце концов, любая схема OWTP, лежащая в основе популярных криптосистем с открытым ключом, основывается на недоказанных, но общепринятых предположениях.
Голдрайх (Goldreich) [65] считает, что методы доказательства стойкости, основанные на модели случайного оракула, представляют собой полезные испытательные схемы. Криптографические схемы, не прошедшие испытания, должны быть отвергнуты. В настоящее время считается общепризнанным, что современные криптографические схемы должны быть основаны на модели случайных оракулов.
Если функции хэширования (или псевдослучайные функции), используемые в реальных криптографических схемах или протоколах, не имеют очевидных недостатков, то доказательство их стойкости с помощью идеализированной версии считается корректным, особенно если целью является доказательство необоснованного предположения о полиномиальной неразличимости. Такое рассуждение называется доказательством стойкости, основанным на модели случайных оракулов (ROM-based security proof).
Перейдем к описанию доказательства, основанного на модели случайных оракулов. В следующей главе будут рассмотрены некоторые схемы цифровой подписи, стойкость которых доказывается с помощью модели случайных оракулов.
562
Часть V. Методы формального доказательства стойкости
15.2.2 Схема RSA-OAEP
В схеме RSA-OAEP перестановка OWTP является результатом применения! функции шифрования RSA. Отметим, что в оставшейся части главы все при-] меры, иллюстрирующие применение схемы RSA-OAEP, используют реализацию] перестановки OWTP с помощью функции шифрования Рабина (раздел 14.3.6.1). I
Поскольку в схеме шифрования RSA-OAEP сначала используются две функции хэширования, допускающие эффективное вычисление, а затем — функция RSA (см. алгоритм 10.6), эффективность этой схемы очень высока и сравнима! с учебной схемой RSA. Эта схема обладает очень широкой полосой пропускание для восстановления сообщений. Если предположить, что модуль RSA состоит иэ1 2048 бит (причина такого выбора будет указана в разделе 15.2.5) и ко = к\ =1 = 160 (так что числа 2~к° и 2~kl являются пренебрежимо малыми), то исходной! сообщение может иметь длину \М\ — \N\ — ко — к\ = 2048 — 320 = 1728 бит! т.е. длина исходного сообщения, зашифрованного в схеме RSA-OAEP, достигает! 84% длины модуля.
Это свойство является очень важным с практической точки зрения. Благо-1 даря ему схема шифрования RSA получила широкое признание со стороны ор| ганизаций, осуществляющих международную стандартизацию (PKCS#1, IEEEj PI363). Она также стала основой для общеизвестного протокола SET, применяе-1 мого в электронной коммерции [259].
Итак, схема шифрования RSA-OAEP оказалась чрезвычайно успешной. Одна-] ко при доказательстве ее стойкости успех стал следствием неудачи.
Для того чтобы понять, как применяется схема RSA-OAEP, достаточно изучить] алгоритм 10.6 и перейти к разделу 15.3. Дальнейшее изложение предназначенш для читателя, которого интересует, почему схема RSA-OAEP является стойкой! Подчеркнем, что это изложение основано на интуитивных рассуждениях.
15.2.3 Трюк в доказательстве стойкости схемы RSA-OAEP
Оригинальное доказательство стойкости схемы шифрования /-ОАЕР, осно-| ванное на модели случайного оракула [24], базируется на сведении атаки INDl ССА2 на схему /-ОАЕР к задаче инвертирования OWTP-функции / с помо! щью скрытой (trapdoor) информации. Недавно Шоуп (Shoup) обнаружил пробеЯ в этом доказательстве [270]. Более того, он заметил, что если функция / является OWTP-перестановкой, то само существование доказательства стойкости фунот ции /-ОАЕР к атаке IND-CCA2 становится маловероятным. К счастью, довольн! быстро опасность утратить весьма успешный алгоритм шифрования с открытый ключом была устранена! Более тщательный анализ, выполненный Фуджисакш
