Как и в DES, в Rijndael применяются замены и перестановки. И там, и там используются несколько итераций, их число зависит от размера ключа и блока и равно 10 для 128-разрядного ключа и 128-битных блоков; для максимального размера ключа и блоков число итераций равно 14. Однако, в отличие от DES, все операции

выполняются над целыми байтами, что позволяет создавать эффективные реализации как в аппаратном, так и в программном исполнении. Схематичный алгоритм метода Rijndael приведен в листинге 8.1. Обратите внимание, что данный код используется в иллюстративных целях. Хорошие реализации кода, обеспечивающего безопасность, должны следовать определенным дополнительным практикам, таким как стирание восприимчивой памяти после использования. Для примера, см. Ferguson и др. (2010).

Листинг 8.1. Схематичный алгоритм метода Rijndael

У функции rijndael три аргумента: plaintext — массив размером 16 байт, содержащий входные данные, ciphertext — массив размером 16 байт, в который будет возвращен шифр, а также key — массив размером 16 байт, содержащий ключ. В процессе вычислений текущее состояние данных сохраняется в байтовом массиве state, размер которого равен NROWS * NCOLS. Для 128-битных блоков данных размер этого массива равен 4 х 4 байта. В 16 байтах целиком уместится один блок.

Массив state изначально содержит открытый текст и модифицируется на каждом этапе вычислений. На некоторых этапах выполняется побайтовая подстановка. На других этапах — перестановка байтов внутри массива. Могут выполняться и другие преобразования. В конечном итоге содержимое state представляет собой зашифрованный текст, который и возвращается в качестве результата функции.

Алгоритм начинается с распространения ключа по 11 массивам одинакового размера с массивом, представляющим состояние (state). Эти массивы хранятся в rk — массиве структур, содержащих массивы состояний. Одна из этих структур будет использована в начале вычислений, а остальные 10 — во время 10 итераций (по одному на итерацию). Вычисление ключа для каждой итерации производится довольно сложным образом, и мы не будем рассматривать детали этого процесса. Достаточно сказать, что для этого осуществляются циклические повороты и суммирования по модулю 2 различных групп разрядов ключа. Подробности можно узнать в (Daemen и Rijmen, 2002).

Следующий шаг состоит в копировании открытого текста в массив state для того, чтобы его можно было обрабатывать во время последующих итераций. Копируется текст в колонки по 4 байта: первые 4 байта попадают в колонку 0, вторые — в колонку 1 и т. д. И колонки, и строки нумеруются с нуля, а итерации — с единицы. Процесс создания 12 байтовых массивов размером 4 х 4 показан на рис. 8.8.

Рис. 8.8. Создание массивов state и rk

Перед началом основного цикла вычислений производится еще одно действие: rk[0] поразрядно складывается по модулю 2 с массивом state. Другими словами, каждый из 16 байт в массиве state заменяется суммой по модулю 2 от него самого и соответствующего байта в rk[0].

Только после этого начинается главное развлечение. В цикле проводятся 10 итераций, в каждой из которых массив state подвергается преобразованию. Каждый раунд (итерация) состоит из четырех шагов. На шаге 1 в state производится посимвольная подстановка. Каждый байт по очереди используется в качестве индекса для S-блока, заменяющего его значение на соответствующую запись S-блока. На этом шаге получается прямой моноалфавитный подстановочный шифр. В отличие от DES, где используются несколько S-блоков, в Rijndael S-блок всего один.

На шаге 2 каждая из четырех строк поворачивается влево. Строка 0 поворачивается на 0 байт (то есть не изменяется), строка 1 — на 1 байт, строка 2 — на 2 байта, а строка 3 — на 3 байта. Смысл заключается в разбрасывании данных вокруг блока. Это аналогично перестановкам, показанным на рис. 8.5.

На шаге 3 происходит независимое перемешивание всех колонок. Делается это с помощью операции матричного умножения, в результате которого каждая новая колонка оказывается равной произведению старой колонки на постоянную матрицу. При этом умножение выполняется с использованием конечного поля Галуа, GF(28). Несмотря на то что все это кажется довольно сложным, алгоритм устроен так, что каждый эле-

мент матрицы вычисляется посредством всего лишь двух обращений к таблице и трех суммирований по модулю 2 (Daemen и Rijmen, 2002, Appendix E).

Наконец, на шаге 4 ключ данной итерации складывается по модулю 2 с массивом state для использования в следующем раунде.

Благодаря обратимости всех действий расшифровка может быть выполнена с помощью такого же алгоритма, но с обратным порядком следования всех шагов. Однако, есть одна хитрость, которая позволяет заниматься расшифровкой, используя алгоритм шифрования с измененными таблицами.

Данный алгоритм обладает не только очень высокой защищенностью, но и очень высокой скоростью. Хорошая программная реализация на машине с частотой 2 ГГц может шифровать данные со скоростью 700 Мбит/с. Такой скорости достаточно для шифрования видео в формате MPEG-2 в реальном масштабе времени. Аппаратные реализации работают еще быстрее.

8.2.3. Режимы шифрования

Несмотря на всю свою сложность, AES (или DES, или любой другой блочный код) представляет собой, по сути дела, моноалфавитный подстановочный шифр с большими длинами символов (в AES используются 128-битные символы, в DES — 64-битные). Для любого отрывка открытого текста шифр при прогоне через один и тот же шифрующий блок будет получаться всегда одинаковым. Скажем, если вы будете 100 раз пытаться зашифровать текст abcdefgh, задавая всякий раз один и тот же ключ для алгоритма DES, вы получите 100 одинаковых копий шифра. Взломщик может попытаться использовать этот недостаток при попытке расшифровки текста.

Режим электронного шифроблокнота

Чтобы понять, каким образом это свойство моноалфавитного подстановочного шифра может быть использовано для частичного взлома шифра, мы рассмотрим (тройное) кодирование по стандарту DES только лишь потому, что изображать 64-разрядные блоки проще, чем 128-разрядные. Надо иметь при этом в виду, что AES сталкивается с теми же самыми проблемами. Самый очевидный способ кодирования длинного сообщения заключается в разбиении его на отдельные блоки по 8 байт (64 бита) с последующим кодированием этих блоков по очереди одним и тем же ключом. Последний блок при необходимости можно дополнить до 64 бит. Такой метод называется режимом электронного шифроблокнота (Electronic Code Book mode — ECB mode), по аналогии со старомодными шифроблокнотами, содержавшими слова и соответствующие им шифры (обычно это были пятизначные десятичные числа).

На рис. 8.9 показано начало компьютерного файла, в котором перечислены поощрительные премии сотрудникам компании. Этот файл состоит из последовательных 32-разрядных записей, по одной на сотрудника, следующего формата: 16 байт на имя, 8 байт на должность и 8 байт на премию. Каждый из шестнадцати 8-байтовых блоков (пронумерованных от 0 до 15) кодируется шифром DES.

Лесли только что поругалась с боссом и не рассчитывает на большую премию. Ким, напротив, — любимица босса, что всем известно. Лесли может получить доступ к файлу, после того как он будет зашифрован, но до того, как он будет отослан в банк. Может ли Лесли исправить ситуацию, имея доступ только к зашифрованному файлу?

Рис. 8.9. Открытый текст файла, зашифрованного в виде 16 DES-блоков

В данном случае это очень просто. Все, что нужно сделать Лесли, — это скопировать зашифрованный блок 12 (содержащий премию Ким) и заменить им блок 4 (содержащий премию Лесли). Даже не зная содержимого блока 12, Лесли может рассчитывать на значительно более веселое Рождество. (Скопировать зашифрованный блок 8 тоже можно, но вероятность, что это будет обнаружено, выше; кроме того, Лесли, в общем-то, не жадная.)