Предварительные математические понятия

Алгоритм Rijndael

Практически все операции Rijndael определяются на уровне байта. Байты можно рассматривать как элементы конечного поля GF (2⁸). Некоторые операции определены в терминах четырехбайтных слов. Введем основные математические понятия, необходимые для обсуждения алгоритма.

Поле GF(2⁸)

Элементы конечного поля могут быть представлены несколькими различными способами. Для любой степени простого числа существует единственное конечное поле, поэтому все представления GF (2⁸) являются изоморфными. Несмотря на подобную эквивалентность, представление влияет на сложность реализации. Выберем классическое полиномиальное представление.

Байт b, состоящий из битов b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀, представляется в виде полинома с коэффициентами из {0, 1}:

b₇х⁷ + b₆х⁶ + b₅х⁵ + b₄х⁴ + b₃х³ + b₂х² + b₁х¹ + b₀

Пример: байт с шестнадцатеричным значением '57' (двоичное 01010111) соответствует полиному

х⁶ + х⁴ + х² + х + 1

Сложение

В полиномиальном представлении сумма двух элементов является полиномом с коэффициентами, которые равны сумме по модулю 2 (т.е. 1 + 1 = 0) коэффициентов слагаемых.

Пример: '57' + '83' = 'DA' или в полиномиальной нотации:

(х⁶ + х⁴ + х² + х + 1) + (х⁷ + х + 1) = х⁷ + х⁶ + х⁴ + х²

В бинарной нотации мы имеем: 01010111 + 10000011 = 11010100. Очевидно, что сложение соответствует простому XOR (обозначается как ) на уровне байта.

Выполнены все необходимые условия Абелевой группы: операция сложения (каждой паре элементов сопоставляется третий элемент группы, называемый их суммой), ассоциативность, нулевой элемент ('00'), обратный элемент (относительно операции сложения) и коммутативность.

Умножение

В полиномиальном представлении умножение в GF (2⁸) соответствует умножению полиномов по модулю неприводимого двоичного полинома степени 8. Полином является неприводимым, если он не имеет делителей, кроме 1 и самого себя. Для Rijndael такой полином называется m(x) и определяется следующим образом:

m(x) = x⁸ + x⁴ + x³ + x + 1

или '11B' в шестнадцатеричном представлении.

Пример: '57' • '83' = 'C1'

Или

(x⁶ + x⁴ + x² + х + 1) (x⁷ + х + 1) =

= x¹³ + x¹¹ + x⁹ + x⁸ + x⁷ + x⁷ + x⁵ + x³ + x² + x + x⁶ + x⁴ + x² + х + 1 =

= x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1

(x⁸ + x⁴ + x³ + х + 1) (x⁵ + x³) + x⁷ + x⁶ + 1 = x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ +1

Следовательно,

x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x⁸ + 1 mod (x⁸ + x⁴ + x³ + х + 1) = x⁷ + x⁶ + 1

Ясно, что результат является двоичным полиномом не выше 8 степени. В отличие от сложения, простой операции умножения на уровне байтов не существует.

Умножение, определенное выше, является ассоциативным, и существует единичный элемент ('01'). Для любого двоичного полинома b(x) не выше 8-й степени можно использовать расширенный алгоритм Евклида для вычисления полиномов a(x) и c(x) таких, что

b(x) a(x) + m(x) c(x) = 1

Следовательно,

a(x) • b(x) mod m(x) = 1

или

b^-1(x) = a(x) mod m(x)

Более того, можно показать, что

a(x) • (b(x) + c(x)) = a(x) • b(x) + a(x) • c(x)

Из всего этого следует, что множество из 256 возможных значений байта образует конечное поле GF (2⁸) c XOR в качестве сложения и умножением, определенным выше.

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

Если умножить b(x) на полином х, мы будем иметь:

b₇x⁸ + b₆x⁷ + b₅x⁶ + b₄x⁵ + b₃x⁴ + b₂x³ + b₁x² + b₀x

x • b(x) получается понижением предыдущего результата по модулю m(x). Если b₇ = 0, то данное понижение является тождественной операцией. Если b₇ = 1, m(x) следует вычесть (т.е. XORed). Из этого следует, что умножение на х может быть реализовано на уровне байта как левый сдвиг и последующий побитовый XOR c '1B'. Данная операция обозначается как b = xtime (a).

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