Здравствуй дорогой друг! Прошло достаточно продолжительное время с момента публикации первой части статьи о AES, и настало время написать собственно о самом процессе шифрование. Итак, давайте начнем.
Все шифрование, по сути, сводится к работе над блоками данных размером ровно в 16 байт, по 1 байту на символ. Это легко представить в виде матрицы размером 4x4 (рисунок 1).
![image001](https://vladdev.vd42.net/wp-content/uploads/2011/07/image001.jpg)
Рисунок 1 – Единичный блок данных.
Для большой наглядности будем представлять числа в блоке в шестнадцатеричном виде. Над таким вот блоком и определены 4 преобразования, о которых будет рассказано ниже.
1) Сложение с раундовым ключом (AddRoundKey)
2) Замена байтов (SubBytes)
3) Сдвиг строк (ShiftRows)
4) Перемешивание столбцов (MixColumns)
1) Сложение с раундовым ключом (AddRoundKey)
Самая простая операция над блоком, которая заключается в сложении по модулю 2 (XOR) обрабатываемого блока с Раундовым ключом, об алгоритме выработки которого будет рассказано в следующей статье. Операция сложения определена аналогично операции сложения матриц. Пример сложения представлен на рисунке 2.
![image002](https://vladdev.vd42.net/wp-content/uploads/2011/07/image002.jpg)
Рисунок 2 – Операция сложения блока с раундовым ключом.
2) Замена байтов (SubBytes)
Данное преобразование представляет собой замену всех 16 значений блока данных значениями из константной таблицы, сформированной по определенному правилу. Будем называть данную таблицу замен S-Блок, принцип формирования которой я оставляю за рамками данной статьи. Заинтересованный читатель может найти данную информацию в книге-источнике, название которой в финале цикла статей. Сама константная таблица представлена на рисунке 3:
![image003](https://vladdev.vd42.net/wp-content/uploads/2011/07/image003.jpg)
Рисунок 3 – S-блок.
Принцип замены значений из этой таблицы довольно прост, чем то он мне напомнил таблицу умножения.
- Из блока данных поочередно берутся значения ячеек
- Числовое значение в каждой ячейке блока можно представить как пару XY, где Y –значение первого разряда числа, X- значение второго разряда числа.
- В S-блоке мы ищем число, стоящее на пересечении X строки и Y колонки
- Найденное число ставиться на место числа XY
![image004](https://vladdev.vd42.net/wp-content/uploads/2011/07/image004.jpg)
Рисунок 4 – Преобразование SubBytes.
3) Сдвиг строк (ShiftRows)
Данная трансформация представляет собой операцию циклического сдвига строк блока на определенное количество позиций влево. Операция циклического сдвига продемонстрирована на рисунке 5.
![image005](https://vladdev.vd42.net/wp-content/uploads/2011/07/image005.jpg)
Рисунок 5 – Преобразование ShiftRows.
И на десерт осталась самая сложная трансформация. В матричном виде трансформацию можно представить следующим образом:
- Исходный блок данных запишем в виде матрицы
- Будим работать со столбцами матрицы
- Введем операцию умножения в поле Галуа
- Преобразование можно описать следующей формулой:
![image008](https://vladdev.vd42.net/wp-content/uploads/2011/07/image008.png)
Данное умножение можно расписать в виде:
![image009](https://vladdev.vd42.net/wp-content/uploads/2011/07/image009.png)
Здесь
![image010](https://vladdev.vd42.net/wp-content/uploads/2011/07/image010.png)
![image011](https://vladdev.vd42.net/wp-content/uploads/2011/07/image011.png)
Значение в каждой ячейке блока можно рассматривать как 1 байт. Следовательно, этот байт можно мыслить как многочлен седьмой степени:
![image012](https://vladdev.vd42.net/wp-content/uploads/2011/07/image012.png)
Умножая данный многочлен на x получим:
![image013](https://vladdev.vd42.net/wp-content/uploads/2011/07/image013.png)
Приводя полученный многочлен по модулю
![image014](https://vladdev.vd42.net/wp-content/uploads/2011/07/image014.png)
![image015](https://vladdev.vd42.net/wp-content/uploads/2011/07/image015.png)
![image016](https://vladdev.vd42.net/wp-content/uploads/2011/07/image016.png)
![image017](https://vladdev.vd42.net/wp-content/uploads/2011/07/image017.png)
![image018](https://vladdev.vd42.net/wp-content/uploads/2011/07/image018.png)
![image019](https://vladdev.vd42.net/wp-content/uploads/2011/07/image019.png)
Для любого ненулевого многочлена
![image020](https://vladdev.vd42.net/wp-content/uploads/2011/07/image020.png)
![image021](https://vladdev.vd42.net/wp-content/uploads/2011/07/image021.png)
Уравнение можно переписать в виде:
![image022](https://vladdev.vd42.net/wp-content/uploads/2011/07/image022.png)
Ниже на рисунке 6 показано как отработает MixColumns:
![image023](https://vladdev.vd42.net/wp-content/uploads/2011/07/image023.jpg)
Рисунок 6 – Преобразование MixColumns.
Так, с трансформациями вроде разобрались :). Теперь будем разбираться с Т-Таблицами.
Все преобразования, выполняемые за один раунд шифрования, могут быть объединены в несколько обращений к вычисляемым таблицам замены (Т-таблицам), что позволяет добиться значительной эффективности при программной реализации алгоритма.
Если обозначить через матрицу
![image024](https://vladdev.vd42.net/wp-content/uploads/2011/07/image024.png)
MixColumns(), записанные в матричной форме:
![image025](https://vladdev.vd42.net/wp-content/uploads/2011/07/image025.png)
где
![image026](https://vladdev.vd42.net/wp-content/uploads/2011/07/image026.png)
![image027](https://vladdev.vd42.net/wp-content/uploads/2011/07/image027.png)
Для преобразований ShiftRows() и SubBytes() записать следующее отношение:
![image028](https://vladdev.vd42.net/wp-content/uploads/2011/07/image028.png)
где
![image029](https://vladdev.vd42.net/wp-content/uploads/2011/07/image029.png)
![image030](https://vladdev.vd42.net/wp-content/uploads/2011/07/image030.png)
Подставляя последовательно промежуточные результаты в формулу выходных данных, получим:
![image031](https://vladdev.vd42.net/wp-content/uploads/2011/07/image031.png)
Данное выражение может быть переписано в следующем виде:
![image032](https://vladdev.vd42.net/wp-content/uploads/2011/07/image032.png)
![image033](https://vladdev.vd42.net/wp-content/uploads/2011/07/image033.png)
где
![image034](https://vladdev.vd42.net/wp-content/uploads/2011/07/image034.png)
Таким образом, мы можем определить четыре Т-таблицы подстановки:
![image035](https://vladdev.vd42.net/wp-content/uploads/2011/07/image035.png)
![image036](https://vladdev.vd42.net/wp-content/uploads/2011/07/image036.png)
Путем использования этих таблиц один раунд процедуры зашифрования может быть выражен следующим образом:
![image037](https://vladdev.vd42.net/wp-content/uploads/2011/07/image037.png)
Таким образом, посредством использования таблиц общим объемом 4 Кбайт, один раунд процедуры шифрования может осуществлятся все шестнадцатью обращениями к Т-таблицам и четырьмя сложениями по модулю 2.
Псевдокод алгоритма для работы с одним блоком данных представлен ниже:
Criptos(входной блок)
{
AddRoundKey(входной блок,0);
for(short i=1;i<10;i++)
{
Ttables(входной блок,i);
}
SubBytes(входной блок);
ShiftRows(входной блок);
AddRoundKey(входной блок,10);
}
Исходный файл в простейшем случае разбивается на блоки, и каждый его блок шифруется данным алгоритмом независимо. Последний блок файла, в случае если его длина не равна 16, дополняется нулями.