Полиномы с коэффициентами из GF

Полиномы могут быть определены с коэффициентами из GF(2⁸). В этом случае четырехбайтный вектор соответствует полиному степени 4.

Полиномы могут быть сложены простым сложением соответствующих коэффициентов. Как сложение в GF(2⁸) является побитовым XOR, так и сложение двух векторов является простым побитовым XOR.

Умножение представляет собой более сложное действие. Предположим, что мы имеем два полинома в GF(2⁸).

a(x) = a₃x³ + a₂x² + a₁x + a₀b(x) = b₃x³ + b₂x² + b₁x + b₀

c(x) = a(x) b(x) определяется следующим образом:

с(x) = с₆x⁶ + с₅x⁵ + с₄x⁴ + с₃x³ + с₂x² + с₁x + с₀ с₀ = a₀ • b₀с₁ = a₁ • b₀ a₀ • b₁с₂ = a₂ • b₀ a₁ • b₁ a₀ • b₂с₃ = a₃ • b₀ a₂ • b₁ a₁ • b₂ a₀ • b₃с₄ = a₃ • b₁ a₂ • b₂ a₁ • b₃с₅ = a₃ • b₂ a₂ • b₃с₆ = a₃ • b₃

Ясно, что в таком виде с(х) не может быть представлен четырехбайтным вектором. Понижая с(х) по модулю полинома 4-й степени, результат может быть полиномом степени ниже 4. В Rijndael это сделано с помощью полинома

M(x) = x⁴ + 1

так как

x^j mod (x⁴ + 1) = x^{j mod 4}

Модуль, получаемый из а(х) и b(x), обозначаемый d(x) = a(x) b(x), получается следующим образом:

d₀ = a₀ • b₀ a₃ • b₁ a₂ • b₂ a₁ • b₃d₁ = a₁ • b₀ a₀ • b₁ a₃ • b₂ a₂ • b₃d₂ = a₂ • b₀ a₁ • b₁ a₀ • b₂ a₃ • b₃d₃ = a₃ • b₀ a₂ • b₁ a₁ • b₂ a₀ • b₃

Операция, состоящая из умножения фиксированного полинома а(х), может быть записана как умножение матрицы, где матрица является циклической. Мы имеем

Замечание: х⁴ + 1 не является несократимым полиномом в GF (2⁸), следовательно, умножение на фиксированный полином необязательно обратимо. В алгоритме Rijndael выбран фиксированный полином, который имеет обратный.

Умножение на х

При умножении b(x) на полином х будем иметь:

b₃x⁴ + b₂x³ + b₁x² + b₀x

x b(x) получается понижением предыдущего результата по модулю 1 + х⁴.

Это дает

b₂x³ + b₁x² + b₀x + b₃

Умножение на х эквивалентно умножению на матрицу, как описано выше со всеми a_i = '00' за исключением а₁ = '01'. Имеем:

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

Дата добавления: 2014-12-23