Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Доказательство. В теореме 14.5.4.2 доказан следующий факт: NM-CCA2 =>¦ IND-CCA2. Следовательно, осталось доказать обратное: IND-CCA2 =>• NM-CCA2. Покажем, что, если криптосистема ?Рк является уязвимой для атаки NM-CCA2, она также уязвима для атаки IND-CCA2.
Допустим, что криптосистема ?ф является уязвимой для атаки NM-CCA2. Тогда существует полиномиально ограниченный атакующий Л, способный взломать криптосистему ?pk с помощью атаки NM-CCA2 с преимуществом Adv(.4), которое не является пренебрежимо малой величиной. Допустим, что Саймону-имитатору и атакующему Л удалось провести редукцию и взломать криптосистему ?рк с помощью атаки NM-CCA2.
Процесс управления атаками показан на рис. 14.5.4.1. Заметим, что редукция стала возможной именно благодаря тому, что зашифрованный текст с1, вычисленный атакующим Л, отличается от зашифрованного оклика с*. Следовательно, Саймон одновременно управляет двумя атаками. Одна из этих атак протекает в режиме NM-CCA2. Саймон играет в ней роль Злоумышленника, посылающего оракулу О зашифрованный текст с1, подобранный после оклика. Получив результат расшифровки, Саймон может проверить отношение между исходными текстами (заданное атакующим Л) и определить бит Ь.
Легко видеть, что, поскольку атакующий Л является полиномиально ограниченным, Саймон угадает бит за полиномиальное время со значимым преимуществом, так как преимущество атакующего Л также не является пренебрежимо малой величиной. о
На рис. 14.4 продемонстрированы все известные взаимосвязи между введенными понятиями стойкости. Если между двумя понятиями нет отношения следования, линия между ними не проводится. Детали этих взаимосвязей описаны в работе [19].
552
Часть V. Методы формального доказательства стойкости
Из теоремы 14.4 следует, что в схемах шифрования с открытым ключом достаточно рассмотреть стойкость к атаке IND-CCA2. Этот вид стойкости легче доказать, чем стойкость к атаке NM-CCA2. Кроме того, вследствие эквивалентности стойкости к атакам IND-CCA2 и NM-CCA2 принято считать, что именно понятие стойкости к атаке IND-CCA2 является основным при исследовании алгоритмов шифрования с открытым ключом.
В следующей главе будут рассмотрены две прикладные криптосистемы, стойкие по отношению к атаке IND-CCA2.
14.6 Резюме
В главе рассмотрены различные понятия стойкости криптосистем с открытым ключом, упорядоченные по мере возрастания строгости.
Изучение начинается с протокола, в котором используется обычный учебный алгоритм. Показана его слабость и непригодность для практического применения. Затем вводится более строгое понятие стойкости: семантическая стойкость, или неразличимое шифрование при пассивной атаке. Продемонстрированы недостатки семантической стойкости и необходимость разработать понятие более сильной стойкости. В заключение изложено наиболее строгое понятие стойкости криптосистем с открытым ключом: неразличимое шифрование при атаке на основе адаптивно подобранного зашифрованного текста (IND-CCA2), которое пригодно для применения на практике. Продемонстрирована стойкость алгоритмов шифрования к различным сценариям атак: строгая стойкость и связанное с ней понятие стойкости к атаке IND-CCA2.
В настоящее время понятие стойкости к атаке IND-CCA2 является стандартным требованием, предъявляемым к криптосистемам с открытым ключом. Все новые схемы шифрования с открытым ключом должны обладать этим свойством. В следующей главе будут рассмотрены две прикладные криптосистемы, обладающие формально доказуемой стойкостью к атаке IND-CCA2.
Упражнения
14.1. Может ли учебный вариант алгоритма RSA скрывать знак символа Якоби исходного сообщения?
14.2. Стоек ли учебный вариант схемы шифрования RSA (Рабина) при шифровании, например, зарплаты? Стоек ли учебный вариант схемы шифрования Эль-Гамаля, если число, выражающее величину зарплаты, не принадлежит множеству (д)!
14.3. Предположим, что в атаке на основе подобранного открытого текста (протокол 14.1) оракул О подбрасывает неидеальную монету, у которой вероят-
Глава 14. Определения формальной и сильной стойкости криптосистем... 553
ность ОРЛА равна 2/3. Выведите формулу, позволяющую вычислить преимущество Злоумышленника по аналогии с формулой (14.2.3).
14.4. Должен ли Злоумышленник организовывать атаку на основе подобранного открытого текста для взлома алгоритма шифрования с открытым ключом?
14.5. Что такое семантическая стойкость? Для какой атаки является неуязвимой криптосистема с открытым ключом, обладающая семантической стойкостью: 1) если атакующий является пассивным и полиномиально ограниченным; 2) если атакующий является пассивным и полиномиально неограниченным; 3) если атакующий является активным и полиномиально ограниченным?
14.6. Семантическая стойкость означает сокрытие любой частичной информации об исходных сообщениях. Почему эта стойкость недостаточно сильна для применения на практике?
14.7. Предположим, что схема шифрования Рабина (алгоритм 8.2) подвергается атаке во время ленча (протокол 14.3). Каких результатов может ожидать атакующий?
Подсказка: в результате атаки во время ленча атакующий может адаптивно подбирать открытые сообщения и получать помощь при расшифровке.
