Rijndael MixColumns - Rijndael MixColumns

Operace MixColumns prováděná Rijndael šifra, spolu s krokem ShiftRows, je primárním zdrojem difúze v Rijndael. Každý sloupec je považován za čtyřčlenný polynom ${ displaystyle b (x) = b_ {3} x ^ {3} + b_ {2} x ^ {2} + b_ {1} x + b_ {0}}$ což jsou prvky v poli ${ displaystyle operatorname {GF} (2 ^ {8})}$. Koeficienty polynomů jsou prvky v prvočísle dílčí pole ${ displaystyle operatorname {GF} (2)}$.

Každý sloupec je vynásoben pevným polynomem ${ displaystyle a (x) = 3x ^ {3} + x ^ {2} + x + 2}$ modulo ${ displaystyle x ^ {4} +1}$; inverzní hodnota tohoto polynomu je ${ displaystyle a ^ {- 1} (x) = 11x ^ {3} + 13x ^ {2} + 9x + 14}$.

MixColumns

Operace spočívá v modulárním násobení dvou čtyřčlenných polynomů, jejichž koeficienty jsou prvky ${ displaystyle operatorname {GF} vlevo (2 ^ {8} vpravo)}$. Modul použitý pro tuto operaci je ${ displaystyle x ^ {4} +1}$.

První čtyřčlenné polynomické koeficienty jsou definovány sloupcem stavu ${ displaystyle { begin {bmatrix} b_ {3} & b_ {2} & b_ {1} & b_ {0} end {bmatrix}}}$, který obsahuje čtyři bajty. Každý bajt je koeficient čtyřčlenného tak, že

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

Druhý čtyřčlenný polynom je konstantní polynom ${ displaystyle a (x) = 3x ^ {3} + x ^ {2} + x + 2}$. Jeho koeficienty jsou také prvky ${ displaystyle operatorname {GF} vlevo (2 ^ {8} vpravo)}$. Jeho inverzní je ${ displaystyle a ^ {- 1} (x) = 11x ^ {3} + 13x ^ {2} + 9x + 14}$.

Musíme definovat nějaký zápis:

${ displaystyle otimes}$ označuje násobení modulo ${ displaystyle x ^ {4} +1}$.

${ displaystyle oplus}$ označuje přidání nad ${ displaystyle operatorname {GF} vlevo (2 ^ {8} vpravo)}$.

${ displaystyle bullet}$ označuje násobení (obvyklé násobení polynomů mezi polynomy a násobením nad ${ displaystyle operatorname {GF} vlevo (2 ^ {8} vpravo)}$ pro koeficienty).

Přidání dvou polynomů, jejichž koeficienty jsou prvky ${ displaystyle operatorname {GF} vlevo (2 ^ {8} vpravo)}$ má následující pravidlo:

${ displaystyle { begin {aligned} & 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 {aligned}}}$

Demonstrace

Polynom ${ displaystyle a (x) = 3x ^ {3} + x ^ {2} + x + 2}$ bude vyjádřena jako ${ displaystyle a (x) = a_ {3} x ^ {3} + a_ {2} x ^ {2} + a_ {1} x + a_ {0}}$.

Polynomiální násobení

${ displaystyle { begin {zarovnáno} a (x) odrážka b (x) = c (x) & = doleva (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 {aligned}}}$

kde:

${ displaystyle c_ {0} = a_ {0} odrážka b_ {0}}$

${ displaystyle c_ {1} = a_ {1} odrážka b_ {0} oplus a_ {0} odrážka 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 b_ {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} odrážka b_ {2} oplus a_ {2} odrážka b_ {3}}$

${ displaystyle c_ {6} = a_ {3} odrážka b_ {3}}$

Modulární redukce

Výsledek ${ displaystyle c (x)}$ je sedmičlenný polynom, který musí být redukován na čtyřbajtové slovo, což se děje pomocí multiplikačního modulo ${ displaystyle x ^ {4} +1}$.

Pokud provedeme několik základních polynomiálních modulárních operací, zjistíme, že:

${ displaystyle { begin {aligned} 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 {aligned}}}$

Obecně to můžeme říci ${ displaystyle x ^ {i} { bmod { left (x ^ {4} +1 right)}} = x ^ {i { bmod {4}}}.}$

Tak

${ displaystyle { begin {aligned} & a (x) otimes b (x) = c (x) { bmod { left (x ^ {4} +1 right)}} = {} & vlevo (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 {zarovnáno}}}$

kde

${ 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}}$

Maticová reprezentace

Koeficient ${ displaystyle d_ {3}}$, ${ displaystyle d_ {2}}$, ${ displaystyle d_ {1}}$ a ${ displaystyle d_ {0}}$ lze také vyjádřit takto:

${ displaystyle d_ {0} = a_ {0} bullet b_ {0} oplus a_ {3} bullet b_ {1} oplus a_ {2} bullet b_ {2} oplus a_ {1} bullet b_ {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 b_ {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 b_ {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 b_ {3}}$

A když nahradíme koeficienty ${ displaystyle a (x)}$ s konstantami ${ displaystyle { begin {bmatrix} 3 & 1 & 1 & 2 end {bmatrix}}}$ použité v šifře získáme následující:

${ displaystyle d_ {0} = 2 kulka b_ {0} oplus 3 kulka b_ {1} oplus 1 kulka b_ {2} oplus 1 kulka b_ {3}}$

${ displaystyle d_ {1} = 1 kulka b_ {0} oplus 2 kulka b_ {1} oplus 3 kulka b_ {2} oplus 1 kulka b_ {3}}$

${ displaystyle d_ {2} = 1 kulka b_ {0} oplus 1 kulka b_ {1} oplus 2 kulka b_ {2} oplus 3 kulka b_ {3}}$

${ displaystyle d_ {3} = 3 kulka b_ {0} oplus 1 kulka b_ {1} oplus 1 kulka b_ {2} oplus 2 kulka b_ {3}}$

To ukazuje, že samotná operace je podobná a Hill šifra. To lze provést vynásobením a vektor souřadnic čtyř čísel v Rijndaelovo pole Galois následující oběhový Matice MDS:

${ 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}}}$

Příklad implementace

To lze ve skutečné implementaci poněkud zjednodušit nahrazením násobení o 2 jednou směnou a podmíněným výlučným nebo a nahrazením násobení 3 množstvím 2 kombinovaným s výlučným nebo. A C následuje příklad takové implementace:

 1 prázdnota gmix_column(nepodepsaný char *r) { 2     nepodepsaný char A[4]; 3     nepodepsaný char b[4]; 4     nepodepsaný char C; 5     nepodepsaný char h; 6     / * Pole 'a' je jednoduše kopií vstupního pole 'r' 7      * Pole 'b' je každý prvek pole 'a' vynásobený 2 8      * v Rijndaelově poli Galois 9      * a [n] ^ b [n] je prvek n vynásobený 3 v Rijndaelově Galoisově poli * / 10     pro (C = 0; C < 4; C++) {11         A[C] = r[C];12         / * h je 0xff, pokud je nastaven vysoký bit r [c], 0 jinak * /13         h = (nepodepsaný char)((podepsaný char)r[C] >> 7); / * aritmetický pravý posun, tedy posun v nulách nebo jednotkách * /14         b[C] = r[C] << 1; / * implicitně odstraňuje vysoký bit, protože b [c] je 8bitový znak, takže jsme xor o 0x1b a ne 0x11b v dalším řádku * /15         b[C] ^= 0x1B & h; / * Rijndaelovo pole Galois * /16     }17     r[0] = b[0] ^ A[3] ^ A[2] ^ b[1] ^ A[1]; / * 2 * a0 + a3 + a2 + 3 * a1 * /18     r[1] = b[1] ^ A[0] ^ A[3] ^ b[2] ^ A[2]; / * 2 * a1 + a0 + a3 + 3 * a2 * /19     r[2] = b[2] ^ A[1] ^ A[0] ^ b[3] ^ A[3]; / * 2 * a2 + a1 + a0 + 3 * a3 * /20     r[3] = b[3] ^ A[2] ^ A[1] ^ b[0] ^ A[0]; / * 2 * a3 + a2 + a1 + 3 * a0 * /21 }

Příklad C #

 1 soukromé byte GMul(byte A, byte b) { // Galoisovo pole (256) Násobení dvou bajtů 2     byte p = 0; 3  4     pro (int čelit = 0; čelit < 8; čelit++) { 5         -li ((b & 1) != 0) { 6             p ^= A; 7         } 8  9         bool hi_bit_set = (A & 0x80) != 0;10         A <<= 1;11         -li (hi_bit_set) {12             A ^= 0x1B; / * x ^ 8 + x ^ 4 + x ^ 3 + x + 1 * /13         }14         b >>= 1;15     }16 17     vrátit se p;18 }19 20 soukromé prázdnota MixColumns() { // 's' je hlavní stavová matice, 'ss' je dočasná matice stejných rozměrů jako 's'.21     Pole.Průhledná(ss, 0, ss.Délka);22 23     pro (int C = 0; C < 4; C++) {24         ss[0, C] = (byte)(GMul(0x02, s[0, C]) ^ GMul(0x03, s[1, C]) ^ s[2, C] ^ s[3, C]);25         ss[1, C] = (byte)(s[0, C] ^ GMul(0x02, s[1, C]) ^ GMul(0x03, s[2, C]) ^ s[3,C]);26         ss[2, C] = (byte)(s[0, C] ^ s[1, C] ^ GMul(0x02, s[2, C]) ^ GMul(0x03, s[3, C]));27         ss[3, C] = (byte)(GMul(0x03, s[0,C]) ^ s[1, C] ^ s[2, C] ^ GMul(0x02, s[3, C]));28     }29 30     ss.Kopírovat do(s, 0);31 }

Testovací vektory pro MixColumn ()

InverseMixColumns

Operace MixColumns má následující inverzní funkce (čísla jsou desetinná):

${ displaystyle { begin {bmatrix} b_ {0} b_ {1} b_ {2} b_ {3} end {bmatrix}} = { begin {bmatrix} 14 & 11 & 13 & 9 9 & 14 & 11 & 13 13 & 9 & 14 & 11 11 & 13 & 9 & 14 end {bmatrix}} { begin {bmatrix} d_ {0} d_ {1} d_ {2} d_ {3} end {bmatrix}}}$

Nebo:

${ displaystyle b_ {0} = 14 bullet d_ {0} oplus 11 bullet d_ {1} oplus 13 bullet d_ {2} oplus 9 bullet d_ {3}}$

${ displaystyle b_ {1} = 9 kulka d_ {0} oplus 14 kulka d_ {1} oplus 11 kulka d_ {2} oplus 13 kulka d_ {3}}$

${ displaystyle b_ {2} = 13 kulka d_ {0} oplus 9 kulka d_ {1} oplus 14 kulka d_ {2} oplus 11 kulka d_ {3}}$

${ displaystyle b_ {3} = 11 bullet d_ {0} oplus 13 bullet d_ {1} oplus 9 bullet d_ {2} oplus 14 bullet d_ {3}}$

Reference

• FIPS PUB 197: oficiální standard AES (PDF soubor)

Viz také

• Advanced Encryption Standard