Математические операции алгоритма

Байтовые операции. Байты рассматриваются как элементы конеч­ного поля Галуа GF(2⁸) порядка 2⁸, где байту b =(b ₇, b ₆, b ₅, b ₄, b ₃, b ₂, b ₁, b ₀) соот­ветствует полином

b (x) = b ₇ х ⁷+ b ₆ х ⁶+… b ₁ х + b₀.

В этом поле определены бинарные операции Å и ×.

Ø операция Å представляет со­бой поразрядное суммирование байтов по модулю 2 (или Х0R-суммирование).

Ø операция × это умножение полиномов, соответствующих байтам, по модулю не­при­водимого двоичного полинома m (х)= х ⁸+ х ⁴+ х ³+ х +1.

Ø и существует обратный элемент по умножению, который можно найти с помощью расширенного алгоритма Евклида.

Произведение многочлена b (x)на х равно полиному

b (x)× x = b ₇ х ⁸ + b ₆ х ⁷ + b ₅ х ⁶ + b ₄ х ⁵ + b ₃ х ⁴ + b ₂ х ³ + b ₁ х ² + b₀ х,

приведенному по модулю т(х).

Замечание. Приведение по модулю т(х) означает вычисление остатка от деления на т(х), то есть результат должен иметь степень не выше 7. При этом

Ø если b ₇ = 0, результатом будет сдвинутый влево на одну позицию байт b, к которому приписывается справа 0:

b ¢=(b ₆, b ₅, b ₄, b ₃, b ₂, b ₁, b ₀,0);

Ø если b ₇ = 1, то ре­зультат полу­чается с помощью Х0R-суммирования полиномов b (x)× x и m (х) длиной по 9 бит с отбрасыванием старшего бита или, что равно­сильно, байтов b ¢и байта ¢0В¢ (в шестнадцатеричном представлении), так как полиному т(х) соот­ветствуют биты ¢1 0000 1011¢, две младших четверки бит равны шестнадцатеричным цифрам 0₁₆ и В₁₆(11₁₀).

Операцию умножения х на многочлен b (x)обозначают x time(b). Умножение многочлена b (x)на x^k равносильно k -кратной компози­ции операции x time(b).

Операции с 4-байтовыми векторами. Состояния, представляю­щие собой 4-байтовые векторы можно представлять с помощью полиномов степени не выше 3 с ко­эффициентами из поля Галуа GF(2⁸), которые сами являются полиномами степени не выше 7. Сложение 4-байтовых векторов производится путем Х0R-суммирова­ния, что равносильно суммированию в поле GF(2⁸) коэффициентов при соответ­ствую­щих степенях полиномов.

Умножение двух полиномов производится с последующим приве­дением произведения по модулю полинома М (х) = х⁴+ 1. При этом, если

с(х) = а(х) + b(х), где

        

      , то

Полином М (х)не является неприводимым над GF(2⁸), следова­тельно, умноже­ние на фиксированный полином не всегда является обратимым. Однако в шифре Rijndael умножение реализуется на фиксированный полином, для которого обрат­ный существует.

Произведение многочлена b (x)на x равно полиному

b (x) × x = b ₃ х ⁴ + b ₂ х ³ + b ₁ х ² + b₀ х,

приведенному по модулю М(х). Результатом приведения является по­лином

b ₂ х ³ + b ₁ х ² + b₀ х + b ₃.

Таким образом, умно­жение на х равносильно левому циклическому сдвигу байтов внутри вектора.

Функция зашифрования

Слои, составляющие каждый цикл (кроме последнего цикла), peaлизованы следующими четырьмя преобразованиями:

I) заменой байтов - SubBytes(S) - побайтовая нелинейная подстановка в State -блоках (S-Box) с использованием фиксированной таблицы замен (affain map table);

II) сдвигом строк - ShiftRows(S) - циклический сдвиг строк массива State на различное количество байт;

III) перемешиванием столбцов - MixColumns(S) - умножение столбцов состояния, рассматриваемых как многочлены над GF (2⁸);

IV) наложением циклового ключа - AddRoundKey(S) - поразрядное XOR содержи­мого State с текущим фрагментом развернутого ключа.

I) Замена байтов (нелинейная подстановка SubBytes) действует на все бай­ты b состояния независимо и определяется функцией l, имеющей вид

l(b)=((x ⁴+ x ³+ x ²+ x +1)× b (x)+ x ⁶+ x ⁵+ x +1) mod (x ⁸+1).

Обратное ему преобразование выглядит как

l^-1(b)=((x ⁶+ x ³+ x) × b (x)+ x ²+1) mod (x ⁸+1).

Результаты всех прочих операций над байтами приводятся не по модулю x ⁸+1, а по модулю m (х)= х ⁸+ х ⁴+ х ³+ х +1.

Многократное вычисление в процессе зашифрования данного выра­жения оказы­вало бы неоправданную вычислительную нагрузку на испол­няющую систему, поэтому для практической реализации наиболее прием­лемым решением является использование предварительно вычисленной таблицы замены S-Box. Ее использо­вание сводит операцию SubBytes() к простейшей выборке байта из массива l(b)= Sbox (b). Логика работы S-Box при преобразовании байта b ={xy} отражена в шестнадцатеричном виде на рисунке 4.15.

Рисунок 4.15 Таблица S-Box замены байт

Рисунок 4.16. Таблица S-Box инверсной замены байт.

В функциях расшифрования применяется операция, обратная SubBytes() - InvSubBytes(), которая реализуется так же просто, как и предыдущая пос­редством инверсной таблицы S-Box - l^-1(b)= InvSbox (b), ее логика работы при преобразова­нии байта {xy} отражена в шестнадцате­ричном виде на рисунке 4.16.

В другом варианте реализации подстановки преобразование байта состоит их двух операций:

1) для каждого байта состояния (представленного двоичным по­линомом b (x) степени не выше 7) находим обратный элемент b^-1 (x) в поле GF(2⁸), при этом '00' переходит в '00';

2) к полученному байту, представленному двоичным вектором (b ₀, b ₁, ..., b ₇), применяем невырожденное аффинное преобразование А нaд GF(2):

II)Сдвиг строк состояния ShiftRows(S) относится к слою линейного пере­ме­шивания и реализуется как циклический сдвиг вправо трех послед­них строк матрицы состояния на С₁ С₂ и С₃ байт соответственно. Значения С₁ С₂ и С₃ зависят от величины N_b:

	C1	C2	C3
Nb =4	1	2	3	AES
Nb =6	1	2	3
Nb = 8	1	3	4

state
s0	s4	s8	s12
s1	s5	s9	s13
s2	s6	s10	s14
s3	s7	s11	s15

III)Перемешивание столбцов состояния MixColumns(S) относится также к слою линейного перемешивания и реализуется так. Столбцы рас­сматриваются как полиномы степени не выше 3 над полем GF (2⁸) и умно­жаются по модулю полинома M (x)= x ⁴+1 на фиксированный полином c (x):

.

Здесь ¢03¢ означает запись константы длиной 8 бит в виде двух шестнад­цатерич­ных цифр от 0 до Е, каждая длиной 4 бита. Это преобразование может быть представлено в матричном виде следующим образом:

.

IV)Наложение i-го циклового ключа. В данной операции раундовый ключ добавляется к состоянию посредством пораз­рядного XOR. Длина ключа равна числу бит в состоянии (N_b. в 32-разрядных словах)

Далее, в зависимости от величины N_k, массив State подвергается раундовой трансформации Np раз (в AES 10, 12 или 14), причем финаль­ный раунд является несколько укороченным - в нем отсутствует преобра­зование MixColumns().

Выходными данными описанной последовательности операций является шифртекст – результат действия функции зашифрования AES.

Ключевое расписание

Генерация цикловых (раундовых) ключей из ключа шифра включает две про­цедуры:

1. расширение ключа(Key Expansion) и

2. выбор цикловых ключей(Round Key Selection).

Генерация реализуется на основе следующих принципов:

² ключ шифра k преобразуется в расширенный ключ(Expanded Key);

² общее количество бит цикловых ключей равно длине блока, умноженной на N_r +1, где N_r - число циклов шифрования;

² цикловые ключи образуются из расширенного ключа следую­щим образом:

1-й цикловой ключ состоит из первых N_b слов,

2-й - из следующих N_b слов и т. д.

Расширение ключа шифра k происходит с использованием одного из двух вариантов рекуррентного закона. Представим расширенный ключ как последо­вательность 4-байтовых слов {w[ i ]}, i = 0,1,2,...

Первые N_k слов содержат ключ шифрования. Каждое последующее слово w [ i ] получается посредством XOR предыдущего слова w [ i -1] и слова на N_k позиций ранее (при N_k< 6):

Для слов, позиция i которых кратна N_k, перед XOR применяется пре­образова­ние к w [ i -1], а затем еще прибавляется раундовая константа RС [ i ]

,

где Т - циклический сдвиг байтовой последовательности на 1 байт, С(t) есть 4-байтовый вектор (RC[ t ],'00', '00', '00'), 1-й байт которого вычисляется по закону

,

где x time(b) мы обозначили операцию умножения х на многочлен b (x),

RС [ ]– массив 32-битных раундовых констант; значение RС [ j ]=2 ^{j- 1}.

Если N_k>6, то рекуррентный закон отличается от ранее заданных только при i, для которых i -4 кратно N_k, а именно

.

На выбор ключа k никаких ограничений не накладывается, но расширенный ключ необходимо вычислять из ключа шифра k и нель­зя определять другим способом.

Таким образом, алгоритм шифрования rijndael состоит из на­чаль­ного наложения циклового ключа, N_r -1 идентичных циклов шиф­рования и последнего цикла, в котором отсутствует перемешивание столбцов.