Раздаточный материал 6 - Алгоритм AES

–1–AES (Rijndael) Joan Daemen, Vincent RijmenДлина блока и длина ключа могут быть независимо выбраны в 128, 192 или 256 бит.Промежуточный результат криптоалгоритма называется Состоянием.Состояние может быть представлено как прямоугольный массив байтов. В таком массивечетыре строки, а количество столбцов, обозначаемое Nb, равно длине блока, деленной на 32.Ключ шифра также можно представить в виде прямоугольного массива с четырьмястроками. Количество столбцов в таком представлении Ключа шифра обозначается Nk иравно длине ключа деленной на 32.a0 , 0a1, 0a2, 0a 3, 0a0,1a1,1a2,1a3,1a0 , 2a1, 2a2, 2a 3, 2a0 , 3a1,3a2,3a 3, 3a0 , 4a1, 4a2, 4a 3, 4a0 , 5a1,5a2,5a 3, 5k 0, 0k1, 0k 2, 0k 3, 0k 0,1k1,1k 2,1k 3,1k 0, 2k1, 2k 2, 2k 3, 2k 0,3k1,3k 2,3k 3, 3Пример компоновки Состояния (с Nb = 6) и Ключа шифра (с Nk = 4).Число раундов обозначается Nr и зависит от величин Nb и Nk.

Это показано в Таблице 1.NrNb  4 Nb  6 Nb  8Nk  4101214Nk  6121214Nk  8141414Раундовое преобразованиеРаундовое преобразование состоит из четырех различных преобразований.Round (State, RoundKey){ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State, RoundKey);}Последний раунд немного отличается. Он выглядит так:FinalRound(State, RoundKey){ByteSub(State);ShiftRow(State);AddRoundKey(State, RoundKey);}Преобразование ByteSubПреобразование ByteSub – это нелинейная замена байтов, применяемая отдельно вкаждому байту состояния. Таблица замен (или S-блок) обратима и составляется путемкомпозиции двух преобразований:1. Сначала берется мультипликативный обратный в поле GF(28) с представлением,описанным в разделе 2.1. ‘00’ отображается в себя.2.

Затем применяется аффинное (над GF(28)) преобразование, определяемое как:–2– y 0  1 0 0y   1  1 1 0 y 2  1 1 1   y 3  = 1 1 1 y  1 1 1 4  y 5  0 1 1 y  0 0 1 6  y 7  0 0 00001111110001111110001111110001111110001 x0  1 x    1  1  x 2  0     x3  + 0  x  0  4   x5  1  x  1  6   x7  0 Рисунок иллюстрирует результат применения преобразования ByteSub к Состоянию.Обратное к ByteSub – это подстановка байтов, где применяется таблица обращения. Этополучаетсяобращениемаффинногоотображенияспоследующимвзятием8мультипликативно обратного в GF(2 ).Преобразование ShiftRowПри ShiftRow строки Состояния циклически сдвигаются на различное число байтов.Строка 0 не сдвигается, строка 1 сдвигается на С1 байтов, строка 2 – на С2 байтов и строка 3– на С3 байтов.Nb C1 C 2 C 3412361238134Преобразование MixColumnПри MixColumn столбцы Состояния рассматриваются как многочлены над GF(28) иумножаются по модулю x4 + 1 на фиксированный многочлен c(x):c(x) = ‘03’x3 + ‘01’x2 + ‘01’x + ‘02’.Этот многочлен – взаимно простой с x4 + 1 и поэтому обратим.

Как описывалось вразделе 2.2, эта операция может быть записана как перемножение матриц.Пусть b(x) = c(x)  a(x):–3–b0  02b   1  =  01b2   01  b3  03030201010103020101010302a0 a  1a2   a3 Преобразование, обратное к MixColumn, действует подобно самому MixColumn. Каждыйстолбец умножается на особый многочлен d(x), определяемый как:('03'x3+'01'x2+'01'x+'02') d(x)='01', где d(x)='0B'x3+'0D'x2+'09'x+'0E'.Прибавление раундового ключаПри этой операции раундовый ключ действует на состояние путем простого поразрядногоEXOR. Раундовый ключ получается из ключа шифра посредством таблицы ключей.

Длинаключа раунда равна блоковой длине Nb.Раундовый ключ получается из ключа шифра посредством таблицы ключей. Она состоит израсширения ключа и выбора раундового ключа. Основной принцип заключается вследующем: Суммарное число битов раундового ключа равно длине блока, умноженной на числораундов плюс 1 (т.е. для длины блока 128 бит и 10 раундов для раундового ключанеобходимо 1408 бит). Ключ шифра расширяется до расширенного ключа.. Раундовые ключи выбираются из этого расширенного ключа следующим образом:первый раундовый ключ состоит из первых Nb слов, второй - из следующих Nb слови т.д.Расширение ключаРасширенный ключ - это одномерный массив четырехбайтовых слов, обозначаемыйW[Nb*(Nr+1)].

Первые Nk слов содержат ключ шифра. Все остальные слова определяютсярекурсивно через слова с меньшими индексами. Функция расширения ключа зависит отвеличины Nk: один случай, когда Nk  6, и другой для Nk > 6:Для Nk  6 имеем:KeyExpansion (byte Key[4*Nk] word W[Nb*(Nr+1)]){for (i = Nk;i < Nb*Nr(Nr+1); i++ )W[i] = (Key[4*i], Key[4*i + 1], Key[4*i + 2], Key[4*i + 3]);for (i = Nk; i < Nb*(Nr+1); i++ ){temp = W[i - 1];–4–if (i % Nk == 0)temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];W[i] = W[i - Nk] ^ temp;}}Здесь SubByte(W) - функция, возвращающая четырехбайтовое слово, в котором каждыйбайт есть результат применения S-блока Rijndael на место байта в соответствующей позицииво входном слове.

Функция RotByte(W) возвращает слово, в котором байты полученыциклической перестановкой из байтов входного слова, таким образом, что входное слово(a,b,c,d) преобразуется в выходное (b,c,d,a).Можно заметить, что первые Nk слов заполнены ключом шифра. Каждое следующее словоW[i] равно результату применения EXOR к предыдущему слову W[i-1] и слову,находящемуся на Nk позиций ранее, W[i-Nk].Для слов в позициях, кратных Nk, преобразование применяется к W[i-1], после примененияEXOR, затем EXOR применяется к константе.

Указанное преобразование состоит изциклического сдвига байтов в слове (RotByte), за которым следует применение табличногопоиска для всех четырех байтов слова (SubByte).Случай Nk > 6 отличается от случая Nk  6 состоит в том, что для i-4, кратных Nk, SubByteприменяется к W[i-1] до EXOR.Раундовые константы не зависят от Nk и определяются следующим образом:Rcon[i]=(RC[i],'00','00','00'),где RC[i] представляет элемент поля GF(28) со значением x(i-1), так что RC[1]=1(т.е.

'01')RC[i]=x (т.е. '02')  (RC[i-1])=x(i-1)Выбор раундового ключаРаундовый ключ i задается буферными словами раундового ключа от W[Nb*i] доW[Nb*(i+1)].Расширение ключа и выбор раундового ключа для Nb =6 и Nk =4.ШифрШифр Рейндал состоит из: начального прибавления раундового ключа; Nr-1 раундов; финального раунда.Rjindael(State, ExpandedKey){AddRoundKey(State, ExpandedKey);For ( i = 1; i < Nr; i++ ) Round(State, ExpandedKey + Nb*i);FinalRound(State, ExpandedKey + Nb*Nr);}.