VD Net

!!! Сообщение со старого блога !!!

Здравствуй дорогой друг! Прошло достаточно продолжительное время с момента публикации первой части статьи о AES, и настало время написать собственно о самом процессе шифрование. Итак, давайте начнем.
Все шифрование, по сути, сводится к работе над блоками данных размером ровно в 16 байт, по 1 байту на символ. Это легко представить в виде матрицы размером 4x4 (рисунок 1).

Рисунок 1 – Единичный блок данных.
Для большой наглядности будем представлять числа в блоке в шестнадцатеричном виде. Над таким вот блоком и определены 4 преобразования, о которых будет рассказано ниже.
1) Сложение с раундовым ключом (AddRoundKey)
2) Замена байтов (SubBytes)
3) Сдвиг строк (ShiftRows)
4) Перемешивание столбцов (MixColumns)
1) Сложение с раундовым ключом (AddRoundKey)
Самая простая операция над блоком, которая заключается в сложении по модулю 2 (XOR) обрабатываемого блока с Раундовым ключом, об алгоритме выработки которого будет рассказано в следующей статье. Операция сложения определена аналогично операции сложения матриц. Пример сложения представлен на рисунке 2.

Рисунок 2 – Операция сложения блока с раундовым ключом.
2) Замена байтов (SubBytes)
Данное преобразование представляет собой замену всех 16 значений блока данных значениями из константной таблицы, сформированной по определенному правилу. Будем называть данную таблицу замен S-Блок, принцип формирования которой я оставляю за рамками данной статьи. Заинтересованный читатель может найти данную информацию в книге-источнике, название которой в финале цикла статей. Сама константная таблица представлена на рисунке 3:

Рисунок 3 – S-блок.
Принцип замены значений из этой таблицы довольно прост, чем то он мне напомнил таблицу умножения.

• Из блока данных поочередно берутся значения ячеек
• Числовое значение в каждой ячейке блока можно представить как пару XY, где Y –значение первого разряда числа, X- значение второго разряда числа.
• В S-блоке мы ищем число, стоящее на пересечении  X строки и Y колонки
• Найденное число ставиться на место числа XY

Допустим, в ячейке хранится число 19. В таблице S-блока ищем число, стоящее на пересечении 1ой строки и 9ого столбцы. Таким числом оказывается d4.Заменяем число 19 в блоке данных на d4 и так со всеми числами блока. Пример преобразования блока на рисунке 4:

Рисунок 4 – Преобразование SubBytes.
3)   Сдвиг строк (ShiftRows)
Данная трансформация представляет собой операцию циклического сдвига строк блока на определенное количество позиций влево. Операция циклического сдвига продемонстрирована на рисунке 5.

Рисунок 5 – Преобразование ShiftRows.
И на десерт осталась самая сложная трансформация. В матричном виде трансформацию можно представить следующим образом:

• Исходный блок данных запишем в виде матрицы 
• Будим работать со столбцами матрицы 
• Введем операцию умножения в поле Галуа
• Преобразование можно описать следующей формулой:

Данное умножение можно расписать в виде:

Здесь  - операция сложения по модулю 2 (XOR), а  - операция умножения  в  конечном поле (поле Галуа GF(2⁸)), о которой будет рассказано ниже.
Значение в каждой ячейке блока можно рассматривать как 1 байт. Следовательно, этот байт можно мыслить как многочлен седьмой степени:

Умножая данный многочлен на x получим:

Приводя полученный многочлен по модулю  (Запись  обозначает, что присутствует «лишний» девятый бит). Для этого при  достаточно вычесть (применить операцию поразрядного XOR)  из полученного выше многочлена. Если же , то результат уже получается приведенным. В итоге умножение на x (т.е. {00000010} в двоичной или {02} в шестнадцатеричной форме) получается сдвигом влево и возможно последующим применением XOR c .
Для любого ненулевого многочлена  также справедливо .
Уравнение можно переписать в виде:

Ниже на рисунке 6 показано как отработает MixColumns:

Рисунок 6 – Преобразование MixColumns.
Так, с трансформациями вроде разобрались :). Теперь будем разбираться с Т-Таблицами.
Все преобразования, выполняемые за один раунд шифрования, могут быть объединены в несколько обращений к вычисляемым таблицам замены (Т-таблицам), что позволяет добиться значительной эффективности при программной реализации алгоритма.
Если обозначить через матрицу  выходные данные, получающиеся на выходе одного раунда преобразования (иначе говоря, одной итерации цикла преобразований) блока открытого текста, тогда имеем следующие соотношения для AddRoundKey() и
MixColumns(), записанные в матричной форме:

где  – результат преобразования MixColumns(),  - результат преобразования ShiftRows().
Для преобразований ShiftRows() и SubBytes() записать следующее отношение:

где  – результат преобразования SubBytes(), 
Подставляя последовательно промежуточные результаты в формулу выходных данных, получим:

Данное выражение может быть переписано в следующем виде:


где  – подстановка соответствующих байт, получаемых из таблицы замен S-Блока.
Таким образом, мы можем определить четыре Т-таблицы подстановки:


Путем использования этих таблиц один раунд процедуры зашифрования может быть выражен следующим образом:

Таким образом, посредством использования таблиц общим объемом 4 Кбайт, один раунд процедуры шифрования может осуществлятся все шестнадцатью обращениями к Т-таблицам и четырьмя сложениями по модулю 2.
Псевдокод алгоритма для работы с одним блоком данных представлен ниже:

Criptos(входной блок)
{
    AddRoundKey(входной блок,0);
    for(short i=1;i<10;i++)
    {
        Ttables(входной блок,i);
    }
    SubBytes(входной блок);
    ShiftRows(входной блок);
    AddRoundKey(входной блок,10);
}

Исходный файл в простейшем случае разбивается на блоки, и каждый его блок шифруется данным алгоритмом независимо. Последний блок файла, в случае если его длина не равна 16, дополняется нулями.