Математическая модель алгоритма RIJNDAEL

 

Байты можно рассматривать как элементы конечного поля GF(28) -

 

многочлены степени не более 7

 

а7х7 + а6х6 + а5х5 + а4х4 + а3х3 + а2х2 + а1х1 + а0х0,

 

которые могут быть заданы строкой коэффициентов

 

{а7, a6, a5, a4, а3, а2, а1, a0}, аi Î{0, 1}, i = 0, 7 .

 

Например, байту в двоичном виде 110010112 (или cb16) ставится в соответствие многочлен х7 + х6 + х3 + х + 1.

В раундах шифрования используются 32-битные слова, представленные в виде многочленов a(х) с коэффициентами аi ÎGF(28)

размером в байт, i =0, 3 :

 

а(х) = а3х3 + а2х2 + а1х + a0.

 

Операция сложения многочленов с коэффициентами из GF(28). Сложение двух многочленов а(х) и b(х) с коэффициентами из GF(28) заключается в поразрядном сложении по операции XOR коэффициентов при неизвестных одинаковой степени:

а(х) + b(х) = (а3 Å b3)х3 + (а2 Å b2)х2 + (а1 Å b1)х + (a0 Å b0).

 

При задании полиномов в виде 4-байтовых слов сложение заключается в поразрядной операции XOR всех разрядов складываемых слов.

Операция умножения многочленов с коэффициентами из GF(28).

 

Пусть перемножаются 2 многочлена

 

а(х) = а3х3 + a2х2 + а1х + a0 и b(х) = b3х3 + b2х2 + b1х + b0.

 

Результатом умножения с(х) = а(х)? b(х) будет многочлен

 

c(х) = c6x6 + c5x5 + c4x4 + c3x3 + c2x2 + c1x + c0, где

 

c0 = a0b0,

 

c1 = a1b0 Å a0b1,

 

с2 = а2b0 Å а1b1 Å a0b2,

 

с3 = а3b0 Å a2b1 Å а1b2 Å a0b3,

 

с4 = а3b1 Å а2b2 Å a1b3,


 

 

с5 = а3b2 Å а2b3,

 

с6 = а3b3.

 

Для того чтобы результат умножения мог быть представлен 4-

байтовым словом, его нормируют по модулю - многочленом степени не более 4 - многочленом

 

x4+1.

 

Результатом d(x) умножения двух многочленов по модулю х4 + 1

 

d(x) = a(x) ? b(х) mod (х4 + 1)

 


будет многочлен


 

 

d(x) = d3x3 + d2x2 + d1x + d0, где d0 = a0b0 Å a3b1 Å a2b2 Å a1b3, d1 = a1b0 Å a0b1 Å a3b2 Å a2b3, d2 = a2b0 Å a1b1 Å a0b2 Å a3b3,

d3 = a3b0 Å a2b1 Å a1b2 Å a0b3,


 

Или в матричной форме:

 

éd0 ù


 

éa0 a3 a2 a1 ù


 

éb0 ù


êd ú


êa a


a a ú


êb ú


ê1 ú=ê1


0 3 2 ú´ê


1 ú.


êd2 ú


êa2 a1 a0 a3 ú


êb2 ú


ê ú ê


ú ê ú


ëd3 û


ëa3 a2 a1 a0 û


ëb3 û


 


Многочлен b(х) = b3x3 + b2x2 + b1x + b0 (bi ÎGF(28),


i = 0, 3 ) можно


умножить на х по модулю х4+1 следующим образом. Умножение аналогично циклическому сдвигу коэффициентов bi влево, в сторону старшей степени b(х):

(х ? b(х)) mod (х4 + 1) = b2x3 + b1x2 + b0x + b3.