Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
2В разделе 13.3 показано, что криптосистемы с открытым ключом можно сделать безопасными, даже если обе стороны не разделяют между собой открытую информацию.
556
Часть V. Методы формального доказательства стойкости
(раздел 15.4). Глава завершается обзором литературы, посвященной прикладным и доказуемо стойким криптосистемам с открытым ключом (раздел 15.5).
15.2 Схема оптимального асимметричного шифрования с заполнением
Схема оптимального асимметричного шифрования с заполнением (ОАЕР) была изобретена Белларе и Роджуэем [24]. Она представляет собой метод рандомизированного заполнения сообщений (randomized message padding technique), осуществляющий легко обратимое отображение из пространства исходных сообщений в область односторонних перестановок с секретом (one-way trapdoor permutation — OWTP). Наиболее известными примерами таких перестановок являются функции RSA и Рабина 3. Это отображение использует две криптографические функции хэширования и получает на вход исходное открытое сообщение, случайное число и строку нулей, обеспечивающих распознаваемость сообщений (см. рис. 15.1). Подробные инструкции по применению схемы RSA-OAEP (т.е. по вычислению перестановок OWTP с помощью функции RSA) изложены в алгоритме 10.6. Следует отметить, что, поскольку в схеме RSA-OAEP, описанной алгоритмом 10.6, процедура шифрования содержит дополнительный этап проверки, целое число, полученное в результате дополнения числа s || t, всегда меньше модуля N в схеме RSA.
Схему шифрования с открытым ключом ОАЕР можно представить в виде последовательных преобразований.
Исходный текст °?fp Область OWTP °\^FF Зашифрованный текст. (15.2.1) I
Рассмотрим три аспекта идеи, лежащей в основе этих преобразований. Перемешивание разных алгебраических структур. Как указано в разделе 8.6, математическая функция, используемая в учебном алгоритме с открытым ключом, как правило, обладает хорошими и широко известными алгебраическими свойствами. Эти свойства она наследует от алгебраической структуры, определяющей перестановку OWTP (например, аксиомы группы или поля обеспечивают очень хорошие алгебраические свойства (см. определения 5.1 и 5.13)). Большое количество атак на учебные алгоритмы шифрования с открытым ключом, продемонстрированные до сих пор (см. алгоритм 14.1 и примеры 14.2 и 14.3), предполагали один и тот же образ действий Злоумышленника: манипулирование зашифрованным текстом, позволяющее
3В разделе 14.3.6.1 показано, почему алгоритм шифрования Рабина является перестановкой OWTP и как его применять.
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
557
Исходный Избыточный текст вход
У
/У= *-*о
/Г
7
н
Случайный вход
/ = *о
Вывод в область fc-битовой однонаправленной перестановки с потайным входом
Рис. 15.1. Схема оптимального асимметричного шифрования с заполнением
целенаправленно изменять исходный текст на основе заранее известных алгебраических свойств перестановок OWTP.
В отличие от этих схем, преобразование ОАЕР использует сетевые криптографические функции хэширования с хорошо известной симметричной алгоритмической структурой. Действительно, как показано на рис. 15.2 (ср. с рис. 7.2), конструкцию преобразования ОАЕР можно рассматривать как двухраундовый шифр Файстеля (Feistel), в котором в первом раунде используется функция хэширования G, а во втором — вместо функции "S-блока", применяемой в шифре файстеля, используется функция хэширования Н. Тем не менее обе функции S-блока не снабжены ключами, а два половинчатых блока имеют разные размеры.
Эти две структуры, т.е. структура OWTP, лежащая в основе популярных криптосистем с открытым ключом, и структура шифра Файстеля, использованная в схеме ОАЕР, имеют совершенно разные алгебраические свойства. Очевидно, что первая структура имеет блочные алгебраические свойства в пространстве высокой размерности, а вторая — побитовые алгебраические свойства в пространстве размерности 2. Таким образом, есть основания надеяться, что комбинированное преобразование (15.2.1) должно поставить перед Злоумышленником непреодолимые препятствия и предотвратить це-
558
Часть V. Методы формального доказательства стойкости
Рис. 15.2. Схема оптимального асимметричного шифрования с заполнением как двухра-ундовый шифр Файстеля
ленаправленную модификацию исходного текста с помощью манипулирования соответствующим текстом.
Рандомизация исходного текста. Как показано в разделе 9, если исходный текст, поступающий на вход учебной криптографической функции с открытым ключом, представляет собой случайную величину, функция обеспечивает полное сокрытие информации об исходном тексте, даже на уровне отдельч ного бита. Схема заполнения, такая как ОАЕР, получает на вход случайное! число, гарантирующее случайность результата заполнения, т.е. обеспечивает! случайность входа схемы OWTP. Таким образом, последовательная комби-1 нация рандомизированной схемы заполнения со схемой OWTP создает побитовую стойкость примитивной криптографической функции с открытым! ключом (см. главу 9).
Защита целостности данных. Мы много раз убеждались, что основным недо-1 статком, присущим учебным криптоалгоритмам, является их чрезвычай-j ная уязвимость к активным атакам. Обратимая функция (расшифровка RSj^ и сеть Файстеля) и добавленная избыточность 0fcl допускают применения механизма проверки целостности данных (см. раздел 10.5). Таким образом,! активная атака становится невозможной.
