Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
8.18. Поскольку все учебные алгоритмы уязвимы для активных атак, необходимо быть бдительным и не предоставлять услуги оракула для расшифровки сообщений. Насколько практична такая стратегия?
8.19. Активная атака, как правило, сопровождается изменением зашифрованного сообщения, передаваемого по сети. Эффективна ли активная атака, если алгоритм шифрования в криптосистеме с открытым ключом содержит механизм, защищающий целостность данных и распознающий несанкционированные изменения зашифрованных текстов?
8.20. Какие преимущества имеют гибридные системы?
Глава 9
Идеальный мир: битовая стойкость основных криптографических функций с открытым ключом
9.1 Введение
Примеры, рассмотренные нами в предыдущей главе, свидетельствуют о том, что основные криптографические функции с открытым ключом, как правило, допускают утечку частичной информации об исходных сообщениях, особенно, если эти сообщения не случайны. Однако эти функции не настолько плохи, если исходные сообщения носят случайный характер. В таких ситуациях описанные ранее криптографические функции оказываются очень стойкими.
В главе рассматривается понятие битовой стойкости (bit security) основных криптографических функций с открытым ключом. Мы покажем, что каждая из этих функций обеспечивает защиту битов. Это означает, что если исходное сообщение является случайным, то расшифровать его отдельный бит так же сложно, как и восстановить весь блок, т.е. вычислить обратную функцию.
Свойство битовой стойкости применялось многими исследователями для создания стойких схем шифрования с открытым ключом на основе распространенных криптографических функций. В основе этих работ лежит идея рандомизации исходных текстов перед шифрованием. В части V описывается общая методология доказательства стойкости —- модель случайного оракула (random oracle model). В рамках этой модели стойкость схем шифрования с открытым ключом (как и схем цифровой подписи), основанных на применении основных криптографических функций, описанных в предыдущей главе, доказывается в строгом смысле. Важным компонентом доказательства повышенной стойкости таких схем является предположение о том, что исходный текст является рандомизированным.
Заметим, что в идеальном мире все исходные сообщения являются случайными. Однако в реальном мире это условие не выполняется. Кроме того, в идеальном
334
Часть III. Основные методы криптографии
мире злоумышленники никогда не организовывают активных атак. Следовательно, основные криптографические схемы с открытым ключом слишком слабы для реального мира.
Читатели, не интересующиеся реальными криптографическими схемами, могут пропустить эту главу.
9.1.1 Структурная схема главы
В разделе 9.2 рассматривается битовая стойкость алгоритма RSA. Раздел 9.3 посвящен битовой стойкости алгоритма Рабина и применению этой схемы для генерации псевдослучайных чисел. В разделе 9.4 изучается битовая стойкость алгоритма Эль-Гамаля. В разделе 9.5 описывается битовая стойкость дискретного логарифма.
9.2 Битовая стойкость алгоритма RSA
Если алгоритм RSA используется для шифрования сообщения, не содержащего никакой априори угадываемой информации (например, если сообщение является равномерно распределенным случайным числом из группы ZJy), то сложность восстановления отдельного бита исходного сообщения из зашифрованного текста сравнима с расшифровкой всего блока [75,76,128]. Не ограничивая общности, будем считать, что перед криптоаналитиком стоит задача восстановления младшего значащего бита, т.е. бита четности исходного сообщения.
Теорема 9.1. Пусть N—модуль алгоритма RSA. Сложность решения следующих двух задач одинакова. I. Восстановить сообщение по заданному тексту, зашифрованному с помощью! алгоритма RSA.
II. Восстановить младший значащий бит сообщения по заданному тексту, зашифрованному с помощью алгоритма RSA.
Очевидно, что из решения первой задачи следует решение второй. Обратное утверждение не столь очевидно. На первый взгляд вычислительная сложность этих двух задач одинакова: первая задача оказывается вычислительной, если исходное сообщение не является равномерно распределенным случайным сообщением, а вторая относится к задачам принятия решений и в половине случаев сводится к простому угадыванию.
Несмотря на это, если взломщику помогает оракул, который может надежно решить вторую задачу, то первую задачу можно решить, вызвав оракула log2 АГ раз. Поскольку размеры чисел АГ и log2 N совпадают, этот метод позволяет свести
Глава 9. Идеальный мир: битовая стойкость..
335
первую задачу ко второй за полиномиальное время, зависящее от размера входного числа. По этой причине такой метод называется полиномиальной редукцией (polynomial time reduction). Следовательно, с помощью оракула задачу I можно решить за полиномиальное время, зависящее от размера исходных данных и превышающее время решения задачи П. И все же эти две задачи имеют одинаковую временную сложность, поскольку мы не дифференцируем понятие сложности по степени полинома.
Рассмотрим метод полиномиальной редукции задачи I к задаче П. Назовем оракул, решающий задачу II, "оракулом четности RSA" и обозначим его как РОм-Тогда процедура сведения задачи I к задаче II описывается следующим образом.
