Основополагающая концепция алгоритма
Алгоритм AES состоит из часто повторяющихся раундов шифрования, как видно из рисунка 1. Сначала на основе 128-битового ключа получают одиннадцать так называемых ключей раундов, каждый из которых имеет размер 128 бит. Каждый раунд включает в себя преобразование с использованием соответствующего криптографического ключа, для того чтобы обеспечить секретность шифрования.
Рисунок 1. Структура алгоритма AES
После начального раунда, во время которого осуществляется логическая операция исключающего или первого ключа раунда и незашифрованного текста (операция «Addroundkey»), следуют девять одинаково структурированных раундов. Каждый раунд состоит из следующих операций:
- замещение байтов;
- сдвиг строк;
- перемешивание столбцов;
- добавление ключа раунда.
Десятый раунд подобен раундам с первого по девятый, но без операции перемешивания столбцов. Ниже поясняются эти четыре операции.
Структура ключа и исходных данных
И ключ, и исходные данные (называемые также «состоянием») структурированы в виде матрицы байтов размером 4x4. На рисунке 2 показано, как 128-битовый ключ и исходные данные распределяются по байтовым матрицам.
Рисунок 2. Структура ключа и состояния
Замещение байтов (операция «Subbytes»)
Операция «Subbytes» - это нелинейное замещение. Это основная причина надёжности шифрования алгоритма AES. Существуют различные способы интерпретации операции замещения байтов. В этом отчёте достаточно представить этап замещения байтов как поиск по таблице. С помощью этой таблицы поиска 16 байт состояния (исходных данных) замещаются соответствующими значениями, найденными в таблице (рисунок 3).
Рисунок 3. Операция замещения байтов
Сдвиг строк (операция «Shiftrows»)
Как явствует из самого названия, операция сдвига строк обрабатывает различные строки. Эта операция просто осуществляет циклическое смещение на различную величину смещения. Вторая строка исходных данных в виде байтовой матрицы 4x4 (состояния) смещается в матрице на один байт влево, третья строка смещается на два байта влево, а четвёртая строка смещается на три байта влево. Первая строка остаётся без изменений. На рисунке 4 показана работа операции сдвига строк.
Рисунок 4. Операция сдвига строк
Перемешивание столбцов (операция «Mixcolumns»)
Операция перемешивания столбцов, вероятно, является самой сложной с точки зрения её программной реализации. На рисунке 5 показано, как работает операция перемешивания столбцов.
Рисунок 5. Операция перемешивания столбцов
В отличие от операции сдвига строк, которая работает со строками в матрице состояния 4x4, операция перемешивания столбцов обрабатывает столбцы.
В принципе, необходимо выполнить только умножение матрицы. Чтобы сделать эту операцию обратимой, не используются обычные сложение и умножение. В AES используются операции в поле Галуа. В этой статье мы не углубляемся в математические подробности, важно только знать, что в поле Галуа сложение соответствует логической операции исключающего ИЛИ, а умножение имеет более сложный эквивалент.
Тот факт, что в матрице умножения операции перемешивания столбцов много членов вида «01», облегчает реализацию этой операции на компьютере.
Добавление ключа раунда (операция «Addroundkey»)
Операция добавления ключа раунда проста. Здесь осуществляется операция исключающего ИЛИ с соответствующими байтами исходных данных и полученным ключом (рисунок 6).
Рисунок 6. Операция добавления ключа раунда
Формирование ключей (операция «Keyexpansion»)
Как указывалось выше, операция «Keyexpansion» означает процесс, в результате которого из 128 бит изначального ключа формируется одиннадцать ключей раундов длиной 128 бит.
Чтобы получить ключ раунда (n+1) из ключа раунда (n), выполняются следующие действия: 1. Получают новый первый столбец следующего ключа раунда, как показано на рисунке 7.
Рисунок 7. Получение первого столбца следующего ключа раунда
Сначала все байты старого четвёртого столбца необходимо заместить с помощью операции «Subbytes». Эти четыре байта сдвигаются вертикально на один байт, а затем выполняется логическая операция исключающего ИЛИ этих байтов со старым первым столбцом. В результате этих действий получается новый первый столбец. 2. Столбцы со 2 по 4 нового ключа раунда рассчитываются так:
- [новый второй столбец] = [новый первый столбец] XOR [старый второй столбец]
- [новый третий столбец] = [новый второй столбец] XOR [старый третий столбец]
- [новый четвёртый столбец] = [новый третий столбец] XOR [старый четвёртый столбец]
На рисунке 8 показан расчёт столбцов 2-4 нового ключа раунда.
Рисунок 8. Получение других столбцов следующего ключа раунда
