Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
7.7.3 Роль внутренних функций алгоритма Rijndael
В заключение опишем роль внутренних функций алгоритма Rijndael.
• Функция SubBytes предназначена для реализации нелинейного подстановочного шифра. Как указывалось в разделе 7.6.2, нелинейность — важное свойство блочного шифра, защищающее его от криптоанализа.
• Функции ShiftRows и MixColumns предназначены для смешивания байтов, размещенных в разных местах блока исходного сообщения. Как правило, распределения исходных текстов в пространстве сообщений имеют низкую энтропию благодаря высокой избыточности натуральных языков и экономических данных (иначе говоря, обычные исходные тексты образуют малое подпространство во всем пространстве сообщений). Смесь байтов, стоящих в разных позициях блока сообщения, расширяет распределение сообщений. По существу, это обеспечивает свойство перемешивания, сформулированное Шенноном (см. раздел 7.1.1).
• Функция AddRoundKey обеспечивает необходимую секретную случайность распределения сообщений.
Эти функции применяются многократно (как минимум 10 раз, если размер ключа и данных равен 128 бит).
7.7.4 Быстродействующая и стойкая реализация
Как мы убедились, внутренние функции алгоритма Rijndael очень просты и действуют в очень простых алгебраических пространствах. В результате реализации этих внутренних функций могут быть чрезвычайно эффективными. Из описания внутренних функций алгоритма Rijndael следует, что только функции SubBytes и MixColumns выполняют нетривиальные алгебраические операции, а значит, необходимо обеспечить их быструю и эффективную реализацию.
Во-первых, величину ж-1 в функции SubBytes можно эффективно вычислить с помощью табличного поиска: можно однажды построить маленькую таблицу, состоящую из 28 = 256 пар байтов, а затем постоянно ее использовать. (Например, такую таблицу можно "зашить" в электронную схему или реализовать в виде
274
Часть III. Основные методы криптографии1
программы). В этой таблице нулевая пара соответствует нулевому байту, а остальные 255 пар соответствуют 255 парам (х, х-1), в которых обращение выполняется в поле F2s. Метод табличного поиска не только эффективен, но и предотвращает атаку на основе временного анализа (timing analysis attack), которая использует разность между временем выполнения операций над разными данными и позволяет распознать, к какому биту применялась операция — 0 или 1 (см. раздел 12.5.4).
Поскольку матрица А и вектор Ь в выражении (7.7.1) являются постоянными,, метод табличного поиска можно распространить на все преобразование (7.7.1), включив в таблицу все пары элементов х, у€?2&, причем пара (0. Ь) представляет собой частный случай пары (х, у).
Очевидно, что обратное преобразование должно использовать обратную таблицу. Следовательно, функцию SubBytes можно реализовать с помощью двух маленьких таблиц, размер каждой из которых равен 256 байт.
Далее, умножение элементов поля F2e в функции MixColumn, т.е. коэффициентов полиномов с(х) и s(x), а точнее — элементов фиксированной матрицы и столбца в выражении (7.7.4) также можно реализовать с помощью метода табличного поиска: z = х - у (умножение в поле), где х ? {'01', '02', '03'} и у Е F2s. Кроме того, байт '0Г представляет собой единицу относительно операции умножения в поле F2s, т.е. '01' • у = у. Таким образом, для реализации (аппаратной или программной) необходима таблица с 2 х 256 = 512 ячейками. Это довольно маленькая таблица. Описанная выше реализация является не только эффективной, но и снижает риск атаки на основе временного анализа.
Линейные алгебраические операции в выражении (7.7.4) и их инверсии также! можно эффективно реализовать в виде аппаратного обеспечения. Читатели могут найти подробное изложение этой темы в книге [87].
7.7.5 Благотворное влияние алгоритма AES на прикладную криптографию
Изобретение алгоритма AES привело к позитивным изменениям в состоянии прикладной криптографии.
Во-первых, многократное шифрование, например, с помощью тройного алго-| ритма DES, с появлением алгоритма AES стало излишним, а переменный размер ключа и блоков сообщения, равный 128, 192 и 256 бит, предоставляет широкий выбор решений, обеспечивающих стойкость в разнообразных приложениях. Поскольку в многократном шифровании используется большое количество ключей, появление AES облегчило управление криптографическими ключами и упростило процесс разработки протоколов и систем защиты данных.
Во-вторых, широкое применение алгоритма AES привело к изобретению но-^ вых хэш-функций, имеющих сравнимую степень стойкости. В некотором смысле алгоритмы блочного шифрования напоминают хэш-функции (см. раздел 10.3.1).
Глава 7. Шифрование — симметричные методы
275
Стало повседневной практикой применять блочные алгоритмы шифрования в качестве однонаправленных функций хэширования. В качестве примера можно назвать протокол регистрации пользователей в операционной системе UNIX1 [206]. В разделе 11.5.1 описывается типичное применение функции алгоритма DES для реализации управления паролями в системе UNIX. Другой пример использования блочных алгоритмов шифрования для реализации однонаправленных функций хэширования, снабженных ключами, описан в разделе 10.3.3. На практике хэш-функции часто применяются в качестве датчиков псевдослучайных чисел для генерации ключей блочных алгоритмов шифрования. Для генерации ключей и блоков данных в алгоритме AES нужны хэш-функции сравнимых размеров. Однако из-за возможности атаки на основе метода квадратного корня (square-root attack), или атаки на основе парадокса "дней рождения" (разделы 3.6 и 10.3.1) размер хэш-функции должен вдвое превышать размер ключа и блока данных. Следовательно, для размеров, равных 128, 192 и 256 бит, хэш-функция должна генерировать данные, имеющие размеры 256, 384 и 512 бит. В настоящее время организация ISO/IES разрабатывает стандарты хэш-функций SHA-256, SHA-384 и SHA-512 [151].
