Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Гибридная схема Шоупа [269] использует ослабленное предположение о неразрешимости задачи, применяемой в схеме Крамера-Шоупа. В оригинальной схеме Крамера-Шоупа (алгоритм 15.1) шифрование сообщения тп имело вид схемы Эль-Гамаля: Нттп. В "ослабленной" версии [269] число hr скрыто с помощью функции хэширования Н(...; hr). Это затрудняет решение задачи DDH. Хэшированное значение H(...;hr) используется для создания симметричных ключей, шифрующих блок DEM и применяемых в механизме проверки целостности данных. Шоуп назвал ослабленное предположение о неразрешимости задачи DDH "хеджированием с помощью хэширования" ("hedging with hash").
15.5 Литературные заметки о прикладных доказуемо стойких криптосистемах с открытым ключом
Первой работой, посвященной прикладным криптосистемам с открытым ключом, устойчивым к активным атакам, является статья Дамгарда (Damgard) [88]. В ней описан способ предотвращения активных атак на криптосистему с открытым ключом с помощью процедуры проверки целостности данных. Впоследствии этот метод лег в основу общей стратегии проектирования криптосистем, стойких к активным атакам. Однако две схемы Дамгарда, описанные в его работе, оказались уязвимыми для атаки ССА2 [311].
Ченг (Zheng) и Себерри (Seberry) предложили практичные схемы шифрования и цифровой подписи, гарантирующие стойкость к атаке ССА2 [310, 311]. Общая идея этих схем заключалась в усовершенствовании однонаправленной функции, применяемой в учебных прототипах (в схеме Эль-Гамаля), с помощью функции хэширования. Это важная идея, которая позднее легла в основу модели случайного оракула, используемой при доказательстве стойкости (см. раздел 15.2). Доказа-
596
Часть V. Методы формального доказательства стойкости
тельство стойкости схем к атаке IND-CCA2, изложенное в работе [310], основано на нестандартном предположении, получившем название "исключительности пространств, генерируемых функциями" ("sole-samplability of spaces induced by functions"), а также на предположении о неразрешимости задачи Диффи-Хеллмана. Впоследствии Солдера (Soldera) обнаружил, что одна из схем Ченга и Себерри на самом деле уязвима к атаке IND-CCA2 [280, 281].
Обнаружив неполноту доказательства стойкости схемы RSA-OAEP, Шоуп предложил для рандомизированной схемы заполнения на основе алгоритма RSA модификацию, получившую название ОАЕР+ [270]. Он доказал ее стойкость с помощью более строгой редукции, чем редукция, примененная при доказательстве стойкости схемы RSA-OAEP в работе Фуджисаки и его соавторов [114]. Повышенная строгость редукции обеспечивается благодаря тому, что преимущество Саймона при инвертировании функции RSA линейно зависит от преимущества, с которым Злоумышленник взламывает криптосистему. Однако, поскольку время, затрачиваемое Саймоном на инвертирование функции RSA, по-прежнему ограничено квадратичной функцией, зависящей от количества запросов, которые Злоумышленник вынужден посылать случайному оракулу, процесс редукции остается неэффективным (см. раздел 15.2.5). Бонэ (Boneh) также предложил модификации схемы ОАЕР, получившие названия Simple-OAEP (SAEP) и Simple-OAEP+ (SAEP+) [49]. Однако эти схемы не позволяли восстанавливать сообщения (эта проблема будет рассматриваться при описании некоторых схем рандомизированного заполнения в разделе 16.4.4.2). Недавно Корон (Согоп) и его соавторы [83] показали, что для шифрования с помощью алгоритма RSA можно применять другую схему рандомизированного заполнения, получившую название "вероятностная схема цифровой подписи с восстановлением сообщения (Probabilistic Signature Scheme with Message Recovery — PSS-R). Ее исходный вариант был предложен Белларе и Роджуэем в работе [26] (см. следующую главу). По существу, эти авторы догадались, что применение функций хэширования в схеме заполнения отменяет требование избыточности при проверке целостности данных (например, наличия младших нулевых разрядов в схеме RSA-OAEP). Эта схема будет описана в следующей главе. Как и схемы SAEP и SAEP+, схема PSS-R обладает слабыми возможностями для восстановления сообщения, если в ее основе лежит шифрование с помощью алгоритма RSA (см. раздел 16.4.4.2).
Подобно схеме RSA-OAEP, схемы рандомизированного заполнения, упомянутые в предыдущем абзаце, обладают стойкостью к атаке IND-CCA2, доказанной в рамках модели случайного оракула. Однако, поскольку стойкость схемы RSA-OAEP к атаке IND-CCA2 была доказана вновь (раздел 15.2.4), причем схема RSA-OAEP долгое время была стандартом шифрования с помощью алгоритма RSA, и схема ОАЕР позволяет лучше восстанавливать сообщения, пока неясно, сможет ли новая схема стать такой же популярной.
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
597
Приемы заполнения, разработанные для функции OWTP, привели к созданию оптимальных схем. Однако функция OWTP на самом деле обладает редкими свойствами. Вероятно, среди распространенных функций, применяемых в криптографии с открытым ключом, единственными OWTP-функциями являются функции RSA и Рабина (над квадратичными вычетами). Более того, модель случайного оракула, на которой основано доказательство стойкости схем заполнения до сих пор не позволяла выполнить "сведение к противоречию". Некоторые исследователи предлагают изобрести доказуемо стойкие схемы для однонаправленной функции общего вида. Другие авторы изобретают схемы, усовершенствующие схемы заполнения, заменяя функции OWTP однонаправленными функциями с секретом общего вида. Многие функции, применяемые в криптографии с открытым ключом, не являются перестановками (например, функция Эль-Гамаля). Следовательно, такая модификация является полезной. Фуджисаки и Окамото [112], а такжде Пойнт-шеваль [234] предложили две обобщенные схемы, обладающие этим свойством. Однако эти схемы оказались неоптимальными: во время расшифровки для распознавания ошибок требуется выполнять повторное шифрование. Поскольку расшифровка часто выполняется с помощью медленных вычислительных устройств, например, смарт-карт, таких схем следует избегать.
