Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
• Схема шифрования подписи Z является стойкой в смысле неразличимости (indistinguishablity) шифрования, подвергающегося атаке на основе адаптивно подобранного зашифрованного текста (adaptive chosen-ciphertext attack), и невозможности подделать подпись с помощью атаки на основе адаптивно подобранного сообщения, независимо от того, когда осуществляется атака: за завтраком, в полночь (at midnight) или пополуночи (in the small hours). Формальное доказательство стойкости связано с факторизацией целого числа.
• Протокол электронного аукциона П является стойким, позволяя покупателю отрицать свое участие в протоколе, а победителю — оставаться неузнанным. Формальное доказательство стойкости протокола связано со стандартным предположением о неразрешимости задачи (standard intractability assumption) — задачей принятия решений Диффи-Хеллмана.
В ходе исследования формально доказуемой стойкости в этой и следующих трех главах каждое использованное жаргонное выражение будет подробно разъясняться. После этих объяснений приведенные выше утверждения станут намного понятнее.
14.1.1 Структурная схема главы
Раздел 14.2 начинается с введения в основную тему этой главы: формальное доказательство стойкости с помощью формального моделирования атак и точного измерения их последствий. Формальное доказательство продемонстрирует неадекватность принципа "все или ничего", введенного в главе 8. Более сильное понятие "семантической стойкости", означающее сокрытие любой частичной информации о сообщении, будет сформулировано в разделе 14.3. Неадекватность понятия семантической стойкости будет показана в разделе 14.4. Это доказательство приводит к новым понятиям: "стойкости относительно подобранного зашифрованного текста" ("chosen-ciphertext security"), "стойкости относительно адаптивно подобранного зашифрованного текста" ("adaptive chosen-ciphertext security") и "неуязвимости" ("non-malleability"). Эти понятия и связи между ними будут изучены в разделе 14.5.
516
Часть V. Методы формального доказательства стойкости
14.2 Формальное доказательство стойкости
Абстрактно говоря, "формально доказуемая стойкость" криптографической системы представляет собой меру устойчивости системы к атакам. Система называ-1 ется стойкой, если Злоумышленник не может взламывать ее слишком часто или! слишком быстро. Следовательно, для измерения стойкости системы необходимей оценивать вероятность взлома и объем вычислительных затрат.
Чтобы конкретизировать наши рассуждения, рассмотрим "игровую атаку", ко-торая разыгрывается между Злоумышленником и "оракулом". Роль оракула испол-J няет наивный пользователь криптографической системы, не способный отказаться от взаимодействия со Злоумышленником. Эта игра позволит продемонстрировать] вычислительные аспекты, связанные с понятием стойкости. Кроме того, она явля-1 ется первым шагом на пути усиления понятия стойкости криптосистем по срав-J нению со слабым понятием, введенным в разделе 8.2 (свойство 8.2).
Допустим, что Злоумышленник организовывает атаку, а О — оракул, прини-! мающий участие в игре. Целью Злоумышленника является взлом криптосистемы! Следовательно, в результате игры с криптосистемой должно случиться "нечто! ужасное", что позволит Злоумышленнику преодолеть защиту.
Для описания криптосистемы будем использовать определение 7.1 из раздев ла 7.2, т.е. будем считать, что она состоит из алгоритма шифрования Е, простран! ства исходных текстов Л4 и пространства зашифрованных текстов С. Однакш следует сделать одно важное замечание: алгоритм шифрования S считается ве! роятностным, т.е. содержит внутреннюю случайную операцию, имеющую некое распределение вероятностей. Таким образом, зашифрованный текст представляе-! собой случайную величину, имеющую то же самое распределение. Например, если исходное сообщение дважды шифруется с помошью одного и того же ключи шифрования, с большой вероятностью возникнут два разных зашифрованных тек! ста (поскольку алгоритм шифрования является однозначным преобразованием). I
Игровая атака описывается протоколом 14.1.
В этой игре оракул О предлагает Злоумышленнику ответить на следующий вопрос.
Результатом какого из экспериментов, Ski(mo) или ?fci(mi), является оклик c*?J Будем считать, что Злоумышленник применяет вероятностный полиномиальный алгоритм распознавания, описанный в определении 4.14 (раздел 4.7). Это! алгоритм считается вероятностным не только потому, что результат работы ораку<1 ла О является случайным, но и потому, что Злоумышленник является полиномщ ально ограниченным и, следовательно, может использовать вероятностный nonnJ номиальный алгоритм (РРТ), если будет уверен, что такой алгоритм более эффен» тивен, чем детерминированный. (Как правило, это предположение выполняется! (см. главу 4).) Обозначим через Adv преимущество Злоумышленника, с которым он может распознавать различие между зашифрованными текстами. По определе-
Глава 14. Определения формальной и сильной стойкости криптосистем... 517
Протокол 14.1. Атака на основе неразличимых подобранных исходных текстов
