7. Причины выбора алгоритма

Для выбора конкретного алгоритма шифрования я обратился к результатам конкурса на создание нового общенационального стандарта шифрования, который должен прийти на замену DES, проведенным в конце 1996г. национальным институтом стандартов США (NIST). Разрабатываемому стандарту было присвоено рабочее наименование AES (Advanced Encryption Standard). Отбор проходил в два этапа, после первого среди претендентов осталось 15 кандидатов, после второго – 5 (Crypton, Mars, RC6, Rijndael и Seipent). В конце 2000 года был сделан окончательный выбор. В качестве предлагаемого стандарта был выбран алгоритм Rijndael. Этот алгоритм был разработан Винсентом Райманом (Vincent Rijman) и Иоан Дамен (Joan Daemen) и представляет собой алгоритм, не использующий сети Фейстела.

Также исходя из документа «Performance Analysis of AES candidates on the 6805 CPU core», в котором приводятся результаты сравнения кандидатов по затратам ресурсов и времени работы, я пришел к выводу, что Rijndael лучше всех остальных подходит к моему заданию, т.к. является самым быстрым и требует наименьший объем ресурсов во время работы.

Также немаловажным было при выборе то, чтобы размер сектора диска (512 байт) был кратен размеру блока алгоритма. Из-за этого условия сразу отсеиваются алгоритмы MARS и RC6. Из оставшихся Serpent оказался слишком медленным (примерно на порядок медленнее средней скорости Rijndael). Crypton оказался медленнее примерно в 3 раза из-за медленного вычисления преобразования числа p, используемого в нем, а также сложнее в реализации.

Исходя из этого, было принято решение об использовании криптографического алгоритма Rijndael.

8. Алгоритм Rijndael

Самостоятельная и оригинальная разработка молодых, но достаточно широко известных в криптографическом сообществе ученых из Бельгии. Алгоритм демонстрирует превосходную производительность на всех рассматриваемых в состязании платформах. Для шифра характерны быстрое разворачивание ключа и низкие требования к памяти, так что он также хорошо работает и в аппаратной реализации, и в ограниченных по памяти условиях. Простая конструкция схемы и консервативный выбор операций должны облегчить дальнейший криптоанализ шифра. Кроме того, специалистами отдельно отмечается, что избранные конструкторами операции относительно просто защитить от известных опасных атак на физическую реализацию криптоалгоритма. Еще одна важная положительная характеристика (хотя и не рассматривавшаяся при выборе финалистов) - в шифре Rijndael имеется существенный потенциал к распараллеливанию, то есть к получению выгод в производительности благодаря применению компьютерных процессоров, позволяющих одновременно выполнять множество инструкций.

Алгоритм может быть сформулирован в терминах всего лишь двух операций - побитового суммирования по модулю 2 и индексированного извлечения из памяти, выполняемых над байтами - он может быть эффективно реализован на любых компьютерных платформах от младших микроконтроллеров до суперпроцессоров. Прямое и обратное преобразования в шифре имеют одинаковую алгоритмическую структуру и различаются константами сдвига, ключевыми элементами, узлами замен и константами умножения. При аппаратной реализации они могут быть совмещены на 60%, а при программной оптимальное быстродействие может быть достигнуто лишь при полностью раздельных реализациях обеих функций.

В качестве стандарта принят вариант шифра только с размером блока 128 бит (16 байт). Число раундов шифрования определяется в зависимости от размера блока и ключа по следующей таблице:

размер ключа	128	192	256
размер блока
128	10	12	14
192	12	12	14
256	14	14	14

Иными словами, из двух размеров выбирается максимальный, и если он равен 128 бит, то используется 10 раундов, если 192 бита, то 12, и если 256 - то 14 раундов шифрования.

В данном продукте решено использовать стандартный размер блока в 128 бит и размер ключа в 256 бит, как наиболее стойкий вариант. Следовательно, будет 14 раундов шифрования.

Шифр Rijndael выполнен в архитектуре "Квадрат" (Square), получившей свое название от первого, построенного в соответствии с ее принципами, криптоалгоритма. В Rijndael блоки открытых и шифрованных данных, соответственно T и T', представляются в виде массивов из 16, 24 или 32 байтов:

T = (t₁, t₂,...,t_N)

T' = (t'₁, t'₂,...,t'_N)

| t | = | t' | = 8, N {16, 24, 32}.

В соответствии с использованными архитектурными принципами в ходе криптографических преобразований исходный и зашифрованный блоки данных, а также все промежуточные результаты процесса шифрования интерпретируются как матрицы байтов размером 4´n, откуда получаем n = N/4, nÎ{4, 6, 8}. Матрицы заполняются байтами входного блока (открытых данных при шифровании и шифрованных данных при дешифрации соответственно) по столбцам сверху вниз и слева направо, и в точно таком же порядке извлекаются байты из матрицы-результата:

Схема преобразования данных при шифровании:

Схема алгоритма шифрования:

На рисунках использованы следующие обозначения:

T, T' - открытый и зашифрованный блоки данных соответственно;

k_i - i-тый ключевой элемент;

F, F' - регулярное нелинейное преобразование и преобразование последнего раунда соответственно;

X_i - промежуточное состояние шифруемого блока после прибавления i-того ключевого элемента.

Как видно из рисунков, процесс шифрования состоит из чередующихся прибавлений ключевых элементов к блоку данных и нелинейного преобразования этого блока:

T' = E_K(T) = k_R+1 F'(k_R F(k_R-1 ... F(k₂ F(k₁ T))...)).

Число R раундов шифрования переменное и зависит от размера блока данных и ключа. Прибавление ключевых элементов, которым начинается и заканчивается процесс шифрования, а также некоторые другие операции раундового преобразования выполняется побайтно в конечном поле Галуа GF(2⁸), полевой операцией сложения в нем является побитовое суммирование по модулю 2. Соответственно, каждый ключевой элемент является байтовой матрицей того же самого размера, что и блок данных. За один раунд шифрования преобразуется полный блок данных, а не его часть, как в сетях Файстеля. На последнем раунде функция нелинейного преобразования отличается от аналогичной функции, используемой в остальных раундах - это сделано для обеспечения алгоритмической эквивалентности прямого и обратного преобразований шифрования.

Процесс дешифрации блока данных алгоритмически идентичен процессу его шифрования и, следовательно, рисунки 1 и 2 также справедливы и для него, если через T обозначить блок зашифрованных данных, а через T' - открытых. Однако различия между этими двумя процедурами в архитектуре "Квадрат" несколько более существенны, чем в сетях Файстеля - они различаются не только порядком использования ключевых элементов в раундах шифрования, но и самими этими элементами, и некоторыми другими константами, используемыми в алгоритме.

Нелинейное преобразование F матрицы данных состоит из трех шагов: замены байтов матрицы на новые значения (S[]), циклического сдвига строк матрицы влево (R¬), умножения матрицы данных слева на постоянную матрицу-циркулянт M:

X' = F(X) = M´ R¬(S(X)).

Схема преобразования блока данных при нелинейном преобразовании:

Схема алгоритма нелинейного преобразования:

Все входные (X), выходные (X') и промежуточные (Y, Z) значения преобразования являются матрицами байтов одинакового размера 4´n. Функция преобразования последнего раунда F' отличается от регулярной функции преобразования F отсутствием шага умножения матрицы данных слева на постоянную матрицу.

Вся нелинейность преобразования сосредоточена в его первом шаге - замене, второй и третий шаги являются линейными. Первый шаг служит для перемешивания информации внутри байтов, второй обеспечивает "экспорт" изменений в другие столбцы, третий осуществляет диффузию изменений в одном элементе матрицы на весь соответствующий столбец. Таким образом, за два раунда достигается диффузия изменений в одном единственном бите на весь блок данных. Ниже каждый из указанных шагов рассмотрен подробно, при этом некоторые преобразования байтов определены в терминах операций в конечном поле GF(2⁸), порожденном неприводимым полиномом m(x) над полем GF(2): m(x) = x⁸+x⁴+x³+x+1. Операция сложения в этом поле является ни чем иным, как побитовым суммированием по модулю 2, умножение в соответствие с определением поля выполняется как обычное умножение полиномов над GF(2) по модулю полинома m(x). При манипулировании с байтами данных как с элементами поля GF(2⁸) каждый бит соответствует слагаемому вида xⁱ в соответствии со старшинством бита в байте. Можно сказать, что если байт с целочисленным значением b представлен в виде полинома B(x), то справедливо b = B(2).