Шифрование. 
Симметричный блочный криптоалгоритм Rijndael

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

С соответствующими параметрами схема криптопреобразования может быть записана так:

• 1. Расширение ключа KeyExpansion.
• 2. Начальная операция AddRoundKey — суммирование с основным ключом.
• 3. 9 раундов из четырех шагов каждый:
• 3.1 SubBytes — замена байтов state по таблице замен.
• 3.2 ShiftRows — циклический сдвиг строк state.
• 3.3 MixColumns — перестановка столбцов state.
• 3.4 AddRoundKey — суммирование с раундовым ключом.
• 4. Заключительный 10-й раунд:
• 4.1 SubBytes — замена байтов state по таблице замен.
• 4.2 ShiftRows — циклический сдвиг строк state.
• 4.3 AddRoundKey — суммирование с раундовым ключом.

Далее подробно описано каждое из преобразований.

Преобразование SubBytes. Преобразование SubBytes представляет собой нелинейную замену байтов, выполняемую независимо с каждым байтом состояния.

Таблицы замены блока данных являются инвертируемыми и построены из композиции таких двух преобразований как:

1) Получение обратного элемента с помощью расширенного алгоритма Эвклида (неприводимый многочлен относительно умножения в поле GF(2⁸), нулевой элемент `00' переходит сам в себя.

Расширенный алгоритм Эвклида:

1. Находим остатки от деления многочленов:

;

;

;

;

…

;

.

Если, то и не взаимно простые, и уравнение не имеет решений.

2. Формируем таблицу:

Таблица 2

.

.

.

.

…

.

.

3. Решением уравнения есть многочлен:

.

2) Применение преобразования над GF(2⁸), определенного следующим образом:

Другими словами, суть преобразования может быть описана уравнениями:

;

;

;

;

;

;

;

.

Например, осуществим два вышеуказанных преобразования над шестнадцатеричным числом `5A'.

• 1) Так, например, `5А' в шестнадцатеричной форме соответствует байт:
• 1 011 010, а соответственно и многочлен:

.

Находим остатки от деления многочленов:

;

;

;

.

Таблица 2

Решением уравнения есть многочлен:

.

В двоичном виде данный многочлен выглядит следующим образом: 100 010, шестнадцатеричном — `22'.

2) ;

;

;

;

;

;

;

.

Имеем, что у=10 111 110, что в шестнадцатеричном виде представляется, как `BE'.

Выполнив данную процедуру для всех возможных вариантов представления одного байта, получим таблицу замен для преобразования SubBytes.

Таблица 3

Замена байта по таблице 3 производится так:

Байт Z преобразуется в шестнадцатеричную систему счисления, например XYh=`5А', X старший разряд, Y младший разряд. Если старшего разряда нет он заменяется нулем.

В таблице 3 выбирается строка X и столбец Y.

Значение Z' на пересечении строки X и столбца Y таблицы 3 используется как замена Z: Z'= X’Y'h=`В 8'.

Рисунок 2 — Пример замены байта в преобразовании SubBytes.

Преобразование сдвига строк ShiftRows. Последние 3 строки (С 1, С 2, С 3, так как первая С 0) состояния циклически сдвигаются на различное число байтов. Строка 1 сдвигается на С 1 байт, строка 2 — на С 2 байт, строка 3 — на С 3 байт. Значения сдвигов С 1, С 2 и С 3 зависят от длины блока. Их величины приведены в таблице 4.

Таблица 4.

Следующий рисунок показывает влияние преобразования ShiftRows на блок данных при .

Рисунок 3 — Преобразование ShiftRows.

Преобразование MixColumns. В преобразовании MixColumns — перемешивание столбца — столбцы блока рассматриваются как многочлены над полем GF(2⁸) и умножаются по модулю на постоянный многочлен:

.

Процесс умножения многочленов эквивалентен матричному умножению:

.

где С — номер столбца массива данных и .

В результате такого умножения, байты столбца с {} заменяются, соответственно на байты:

;

;

;

.

Данное преобразование применяется к каждому из четырех столбцов блока данных.

Рисунок 4 — Графическое представление процедуры MixColumns.

Преобразование AddRoundKey. В преобразовании AddRoundKey, раундовый ключ RK добавляется к state посредством поразрядного XOR. Каждый раундовый ключ состоит из 16 байт расширенного ключа. Байты раундового ключа записываются в матрицу 44, подобную state. Каждый байт раундового ключа суммируется с соответствующим байтом из state, как показано на рисунке 5.

Рисунок 5 — Суммирование блока данных с раундовым ключом.