Rijndael MixКолонны - Rijndael MixColumns

Операция MixColumns, выполняемая Rijndael шифр, наряду с шагом ShiftRows, является основным источником распространение в Rijndael. Каждый столбец рассматривается как четырехчленный многочлен ${ displaystyle b (x) = b_ {3} x ^ {3} + b_ {2} x ^ {2} + b_ {1} x + b_ {0}}$ которые являются элементами в поле ${ displaystyle operatorname {GF} (2 ^ {8})}$ . Коэффициенты полиномов являются элементами в пределах простого подполе ${ displaystyle operatorname {GF} (2)}$ .

Каждый столбец умножается на фиксированный многочлен ${ displaystyle a (x) = 3x ^ {3} + x ^ {2} + x + 2}$ по модулю ${ displaystyle x ^ {4} +1}$ ; обратный к этому многочлену равен ${ displaystyle a ^ {- 1} (x) = 11x ^ {3} + 13x ^ {2} + 9x + 14}$ .

MixColumns

Операция заключается в модульном умножении двух четырехчленных многочленов, коэффициенты которых являются элементами ${ displaystyle operatorname {GF} left (2 ^ {8} right)}$ . Модуль, используемый для этой операции, равен ${ displaystyle x ^ {4} +1}$ .

Первые четырехчленные полиномиальные коэффициенты определяются столбцом состояния ${ displaystyle { begin {bmatrix} b_ {3} & b_ {2} & b_ {1} & b_ {0} end {bmatrix}}}$ , который содержит четыре байта. Каждый байт является коэффициентом четырехчленного, так что

{ displaystyle b (x) = b_ {3} x ^ {3} + b_ {2} x ^ {2} + b_ {1} x + b_ {0}.}

Второй четырехчленный многочлен является постоянным многочленом ${ Displaystyle а (х) = 3х ^ {3} + х ^ {2} + х + 2}$ . Его коэффициенты также являются элементами ${ displaystyle operatorname {GF} left (2 ^ {8} right)}$ . Его обратное ${ displaystyle a ^ {- 1} (x) = 11x ^ {3} + 13x ^ {2} + 9x + 14}$ .

Нам нужно определить некоторые обозначения:

{ displaystyle otimes}

обозначает умножение по модулю

{ displaystyle x ^ {4} +1}

.

{ displaystyle oplus}

обозначает сложение по

{ displaystyle operatorname {GF} left (2 ^ {8} right)}

.

{ displaystyle bullet}

обозначает умножение (обычное умножение многочленов, когда между многочленами и умножение над

{ displaystyle operatorname {GF} left (2 ^ {8} right)}

для коэффициентов).

Сложение двух многочленов, коэффициенты которых являются элементами ${ displaystyle operatorname {GF} left (2 ^ {8} right)}$ имеет следующее правило:

{ displaystyle { begin {align} & left (a_ {3} x ^ {3} + a_ {2} x ^ {2} + a_ {1} x + a_ {0} right) + left ( b_ {3} x ^ {3} + b_ {2} x ^ {2} + b_ {1} x + b_ {0} right) = {} & left (a_ {3} oplus b_ { 3} right) x ^ {3} + left (a_ {2} oplus b_ {2} right) x ^ {2} + left (a_ {1} oplus b_ {1} right) x + left (a_ {0} oplus b_ {0} right) end {align}}}

Демонстрация

Полином ${ Displaystyle а (х) = 3х ^ {3} + х ^ {2} + х + 2}$ будет выражаться как ${ displaystyle a (x) = a_ {3} x ^ {3} + a_ {2} x ^ {2} + a_ {1} x + a_ {0}}$ .

Полиномиальное умножение

{ displaystyle { begin {align} a (x) bullet b (x) = c (x) & = left (a_ {3} x ^ {3} + a_ {2} x ^ {2} + a_ {1} x + a_ {0} right) bullet left (b_ {3} x ^ {3} + b_ {2} x ^ {2} + b_ {1} x + b_ {0} right) & = c_ {6} x ^ {6} + c_ {5} x ^ {5} + c_ {4} x ^ {4} + c_ {3} x ^ {3} + c_ {2} x ^ {2} + c_ {1} x + c_ {0} end {align}}}

куда:

{ displaystyle c_ {0} = a_ {0} bullet b_ {0}}

{ displaystyle c_ {1} = a_ {1} bullet b_ {0} oplus a_ {0} bullet b_ {1}}

{ displaystyle c_ {2} = a_ {2} bullet b_ {0} oplus a_ {1} bullet b_ {1} oplus a_ {0} bullet b_ {2}}

{ displaystyle c_ {3} = a_ {3} bullet b_ {0} oplus a_ {2} bullet b_ {1} oplus a_ {1} bullet b_ {2} oplus a_ {0} bullet б_ {3}}

{ displaystyle c_ {4} = a_ {3} bullet b_ {1} oplus a_ {2} bullet b_ {2} oplus a_ {1} bullet b_ {3}}

{ displaystyle c_ {5} = a_ {3} bullet b_ {2} oplus a_ {2} bullet b_ {3}}

{ displaystyle c_ {6} = a_ {3} bullet b_ {3}}

Модульное сокращение

Результат ${ Displaystyle с (х)}$ является семичленным многочленом, который должен быть уменьшен до четырехбайтового слова, что достигается умножением по модулю ${ displaystyle x ^ {4} +1}$ .

Если мы проделаем некоторые базовые полиномиальные модульные операции, мы увидим, что:

{ displaystyle { begin {align} x ^ {6} { bmod { left (x ^ {4} +1 right)}} & = - x ^ {2} = x ^ {2} { text {over}} operatorname {GF} left (2 ^ {8} right) x ^ {5} { bmod { left (x ^ {4} +1 right)}} & = - x = x { text {over}} operatorname {GF} left (2 ^ {8} right) x ^ {4} { bmod { left (x ^ {4} +1 right)} } & = - 1 = 1 { text {over}} operatorname {GF} left (2 ^ {8} right) end {align}}}

В целом можно сказать, что ${ displaystyle x ^ {i} { bmod { left (x ^ {4} +1 right)}} = x ^ {i { bmod {4}}}.}$

Так

{ Displaystyle { begin {align} & a (x) otimes b (x) = c (x) { bmod { left (x ^ {4} +1 right)}} = {} & слева (c_ {6} x ^ {6} + c_ {5} x ^ {5} + c_ {4} x ^ {4} + c_ {3} x ^ {3} + c_ {2} x ^ {2 } + c_ {1} x + c_ {0} right) { bmod { left (x ^ {4} +1 right)}} = {} & c_ {6} x ^ {6 { bmod {4}}} + c_ {5} x ^ {5 { bmod {4}}} + c_ {4} x ^ {4 { bmod {4}}} + c_ {3} x ^ {3 { bmod {4}}} + c_ {2} x ^ {2 { bmod {4}}} + c_ {1} x ^ {1 { bmod {4}}} + c_ {0} x ^ {0 { bmod {4}}} = {} & c_ {6} x ^ {2} + c_ {5} x + c_ {4} + c_ {3} x ^ {3} + c_ {2} x ^ { 2} + c_ {1} x + c_ {0} = {} & c_ {3} x ^ {3} + left (c_ {2} oplus c_ {6} right) x ^ {2} + left (c_ {1} oplus c_ {5} right) x + c_ {0} oplus c_ {4} = {} & d_ {3} x ^ {3} + d_ {2} x ^ { 2} + d_ {1} x + d_ {0} end {align}}}

куда

{ displaystyle d_ {0} = c_ {0} oplus c_ {4}}

{ displaystyle d_ {1} = c_ {1} oplus c_ {5}}

{ displaystyle d_ {2} = c_ {2} oplus c_ {6}}

{ displaystyle d_ {3} = c_ {3}}

Матричное представление

Коэффициент ${ displaystyle d_ {3}}$ , ${ displaystyle d_ {2}}$ , ${ displaystyle d_ {1}}$ и ${ displaystyle d_ {0}}$ можно также выразить следующим образом:

{ displaystyle d_ {0} = a_ {0} bullet b_ {0} oplus a_ {3} bullet b_ {1} oplus a_ {2} bullet b_ {2} oplus a_ {1} bullet б_ {3}}

{ displaystyle d_ {1} = a_ {1} bullet b_ {0} oplus a_ {0} bullet b_ {1} oplus a_ {3} bullet b_ {2} oplus a_ {2} bullet б_ {3}}

{ displaystyle d_ {2} = a_ {2} bullet b_ {0} oplus a_ {1} bullet b_ {1} oplus a_ {0} bullet b_ {2} oplus a_ {3} bullet б_ {3}}

{ displaystyle d_ {3} = a_ {3} bullet b_ {0} oplus a_ {2} bullet b_ {1} oplus a_ {1} bullet b_ {2} oplus a_ {0} bullet б_ {3}}

И когда мы заменим коэффициенты при ${ Displaystyle а (х)}$ с константами ${ displaystyle { begin {bmatrix} 3 & 1 & 1 & 2 end {bmatrix}}}$ используемое в шифре, получаем следующее:

{ displaystyle d_ {0} = 2 bullet b_ {0} oplus 3 bullet b_ {1} oplus 1 bullet b_ {2} oplus 1 bullet b_ {3}}

{ displaystyle d_ {1} = 1 bullet b_ {0} oplus 2 bullet b_ {1} oplus 3 bullet b_ {2} oplus 1 bullet b_ {3}}

{ displaystyle d_ {2} = 1 bullet b_ {0} oplus 1 bullet b_ {1} oplus 2 bullet b_ {2} oplus 3 bullet b_ {3}}

{ displaystyle d_ {3} = 3 bullet b_ {0} oplus 1 bullet b_ {1} oplus 1 bullet b_ {2} oplus 2 bullet b_ {3}}

Это демонстрирует, что сама операция похожа на Шифр холма. Это можно сделать, умножив вектор координат из четырех номеров в Поле Галуа Риджндаля следующими циркулирующий Матрица МДС:

{ displaystyle { begin {bmatrix} d_ {0} d_ {1} d_ {2} d_ {3} end {bmatrix}} = { begin {bmatrix} 2 & 3 & 1 & 1 1 & 2 & 3 & 1 1 & 1 & 2 & 3 3 & 1 & 1 & 2 end {bmatrix}} { begin {bmatrix} b_ {0} b_ {1} b_ {2} b_ {3} end {bmatrix}}}

Пример реализации

В реальной реализации это можно несколько упростить, заменив умножение на 2 одним сдвигом и условным исключающим или, а также заменив умножение на 3 на умножение на 2 в сочетании с исключающим или. А C пример такой реализации:

 1 пустота gmix_column(беззнаковый char *р) { 2     беззнаковый char а[4]; 3     беззнаковый char б[4]; 4     беззнаковый char c; 5     беззнаковый char час; 6     / * Массив 'a' - это просто копия входного массива 'r' 7      * Массив 'b' - это каждый элемент массива 'a', умноженный на 2 8      * в поле Галуа Риджндала 9      * a [n] ^ b [n] - это элемент n, умноженный на 3 в поле Галуа Риджндала * / 10     за (c = 0; c < 4; c++) {11         а[c] = р[c];12         / * h равно 0xff, если установлен старший бит r [c], в противном случае - 0 * /13         час = (беззнаковый char)((подписанный char)р[c] >> 7); / * арифметический сдвиг вправо, смещая, таким образом, либо нули, либо единицы * /14         б[c] = р[c] << 1; / * неявно удаляет старший бит, потому что b [c] является 8-битным символом, поэтому мы выполняем xor по 0x1b, а не 0x11b в следующей строке * /15         б[c] ^= 0x1B & час; / * Поле Галуа Риджндала * /16     }17     р[0] = б[0] ^ а[3] ^ а[2] ^ б[1] ^ а[1]; / * 2 * a0 + a3 + a2 + 3 * a1 * /18     р[1] = б[1] ^ а[0] ^ а[3] ^ б[2] ^ а[2]; / * 2 * a1 + a0 + a3 + 3 * a2 * /19     р[2] = б[2] ^ а[1] ^ а[0] ^ б[3] ^ а[3]; / * 2 * a2 + a1 + a0 + 3 * a3 * /20     р[3] = б[3] ^ а[2] ^ а[1] ^ б[0] ^ а[0]; / * 2 * a3 + a2 + a1 + 3 * a0 * /21 }

Пример C #

 1 частный байт GMul(байт а, байт б) { // Поле Галуа (256) Умножение двух байтов 2     байт п = 0; 3  4     за (int прилавок = 0; прилавок < 8; прилавок++) { 5         если ((б & 1) != 0) { 6             п ^= а; 7         } 8  9         bool hi_bit_set = (а & 0x80) != 0;10         а <<= 1;11         если (hi_bit_set) {12             а ^= 0x1B; / * х ^ 8 + х ^ 4 + х ^ 3 + х + 1 * /13         }14         б >>= 1;15     }16 17     возвращаться п;18 }19 20 частный пустота MixColumns() { // 's' - это основная матрица состояний, 'ss' - это временная матрица тех же размеров, что и 's'.21     Множество.Прозрачный(SS, 0, SS.Длина);22 23     за (int c = 0; c < 4; c++) {24         SS[0, c] = (байт)(GMul(0x02, s[0, c]) ^ GMul(0x03, s[1, c]) ^ s[2, c] ^ s[3, c]);25         SS[1, c] = (байт)(s[0, c] ^ GMul(0x02, s[1, c]) ^ GMul(0x03, s[2, c]) ^ s[3,c]);26         SS[2, c] = (байт)(s[0, c] ^ s[1, c] ^ GMul(0x02, s[2, c]) ^ GMul(0x03, s[3, c]));27         SS[3, c] = (байт)(GMul(0x03, s[0,c]) ^ s[1, c] ^ s[2, c] ^ GMul(0x02, s[3, c]));28     }29 30     SS.Скопировать в(s, 0);31 }

Тестовые векторы для MixColumn ()

Шестнадцатеричный		Десятичный
Перед	После	Перед	После
`дб 13 53 45`	`8e 4d a1 bc`	219 19 83 69	142 77 161 188
`f2 0a 22 5c`	`9f dc 58 9d`	242 10 34 92	159 220 88 157
`01 01 01 01`	`01 01 01 01`	1 1 1 1	1 1 1 1
`c6 c6 c6 c6`	`c6 c6 c6 c6`	198 198 198 198	198 198 198 198
`d4 d4 d4 d5`	`d5 d5 d7 d6`	212 212 212 213	213 213 215 214
`2d 26 31 4c`	`4d 7e bd f8`	45 38 49 76	77 126 189 248