Rijndael MixColumns
MixColumns-operationen som utförs av Rijndael -chifferet, tillsammans med ShiftRows-steget, är den primära spridningskällan i Rijndael. Varje kolumn behandlas som ett fyrtermspolynom som är element inom fältet . Polynomens koefficienter är element inom det primtal delfältet .
Varje kolumn multipliceras med ett fast polynom modulo ; inversen av detta polynom är .
Demonstration
Polynomet kommer att uttryckas som .
Polynom multiplikation
var:
Modulär reduktion
Resultatet är ett sjutermspolynom, som måste reduceras till ett fyrabyteord, vilket görs genom att multiplicera modulo .
Om vi gör några grundläggande polynom modulära operationer kan vi se att:
Generellt kan vi säga att
Så
var
Matrisrepresentation
Koefficienten , , och kan också uttryckas enligt följande :
Och när vi ersätter koefficienterna för med konstanterna som används i chifferet skaffa följande:
Detta visar att själva operationen liknar ett Hill-chiffer . Det kan utföras genom att multiplicera en koordinatvektor med fyra tal i Rijndaels Galois-fält med följande cirkulerande MDS-matris :
Implementeringsexempel
Detta kan förenklas något i den faktiska implementeringen genom att ersätta multiplicera med 2 med ett enda skift och villkorlig exklusiv eller, och ersätta en multiplicera med 3 med en multiplicera med 2 kombinerat med en exklusiv eller. Ett C- exempel på en sådan implementering följer:
0
0 0
0
0
0 0
void gmix_column ( unsigned char * r ) { unsigned char a [ 4 ]; osignerad char b [ 4 ]; osignerad char c ; osignerad char h ; /* Arrayen 'a' är helt enkelt en kopia av inmatningsarrayen 'r' * Arrayen 'b' är varje element i arrayen 'a' multiplicerat med 2 * i Rijndaels Galois-fält * a[n] ^ b[n ] är element n multiplicerat med 3 i Rijndaels Galois-fält */ för ( c = ; c < 4 ; c ++ ) { a [ c ] = r [ c ]; /* h är 0xff om den höga biten av r[c] är satt, 0 annars */ h = ( r [ c ] >> 7 ) & 1 ; /* aritmetisk högerförskjutning, alltså skiftning i antingen nollor eller ettor */ b [ c ] = r [ c ] << 1 ; /* tar implicit bort hög bit eftersom b[c] är ett 8-bitars tecken, så vi xor med 0x1b och inte 0x11b på nästa rad */ b [ c ] ^= h * 0x1B ; /* Rijndaels Galois-fält */ } r [ ] = b [ ] ^ a [ 3 ] ^ a [ 2 ] ^ b [ 1 ] ^ a [ 1 ]; /* 2 * a0 + a3 + a2 + 3 * a1 */ r [ 1 ] = b [ 1 ] ^ a [ ] ^ a [ 3 ] ^ b [ 2 ] ^ a [ 2 ]; /* 2 * a1 + a0 + a3 + 3 * a2 */ r [ 2 ] = b [ 2 ] ^ a [ 1 ] ^ a [ ] ^ b [ 3 ] ^ a [ 3 ]; /* 2 * a2 + a1 + a0 + 3 * a3 */ r [ 3 ] = b [ 3 ] ^ a [ 2 ] ^ a [ 1 ] ^ b [ ] ^ a [ ]; /* 2 * a3 + a2 + a1 + 3 * a0 */ }
AC# exempel
0
0
0
0 0
0
0
0
0 0 0 0
0 0 0
0 0 0
0 0 0
0
privat byte GMul ( byte a , byte b ) { // Galois Field (256) Multiplikation av två byte byte p = ; for ( int räknare = ; räknare < 8 ; räknare ++) { if (( b & 1 ) != ) { p ^= a ; } bool hi_bit_set = ( a & x80 ) != ; a <<= 1 ; if ( hi_bit_set ) { a ^= x1B ; /* x^8 + x^4 + x^3 + x + 1 */ } b >> = 1 ; } returnera p ; } private void MixColumns () { // 's' är huvudtillståndsmatrisen, 'ss' är en tempmatris med samma dimensioner som 's'. Array . Klar ( ss , ss . Längd ) ; för ( int c = ; c < 4 ; c ++) { ss [ , c ] = ( byte )( GMul ( x02 , s [ , c ]) ^ GMul ( x03 , s [ 1 , c ]) ^ s [ 2 , c ] ^ s [ 3 , c ]); ss [ 1 , c ] = ( byte ) ( s [ , c ] ^ GMul ( x02 , s [ 1 , c ]) ^ GMul ( x03 , s [ 2 , c ]) ^ s [ 3 , c ]); ss [ 2 , c ] = ( byte ) ( s [ , c ] ^ s [ 1 , c ] ^ GMul ( x02 , s [ 2 , c ]) ^ GMul ( x03 , s [ 3 , c ])); ss [ 3 , c ] = ( byte ) ( GMul ( x03 , s [ , c ]) ^ s [ 1 , c ] ^ s [ 2 , c ] ^ GMul ( x02 , s [ 3 , c ])); } ss . CopyTo ( s , ); }
Testvektorer för MixColumn()
Hexadecimal | Decimal | ||
---|---|---|---|
Innan | Efter | Innan | Efter |
db 13 53 45
|
8e 4d a1 f.Kr
|
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 |
InverseMixColumns
Operationen MixColumns har följande invers (siffror är decimaler):
Eller:
Galois Multiplikationsuppslagstabeller
Vanligtvis, snarare än att implementera Galois-multiplikation, använder Rijndael-implementeringar helt enkelt förberäknade uppslagstabeller för att utföra bytemultiplikationen med 2, 3, 9, 11, 13 och 14.
Till exempel, i C# kan dessa tabeller lagras i Byte[256]-arrayer. För att beräkna
p * 3
Resultatet erhålls så här:
resultat = table_3[(int)p]
Några av de vanligaste fallen av dessa uppslagstabeller är följande:
Multiplicera med 2:
0x00,0x02,0x04,0x06,0x08,0x0a,0x0c,0x0e,0x10,0x12,0x14,0x16,0x18,0x1a,0x1c,0x1e, 0x20,0x22,0x2x,x,x 0x30, 0x32,0x34,0x36,0x38,0x3a,0x3c,0x3e, 0x40,0x42,0x44,0x46,0x48,0x4a,0x4c,0x4e,0x50,0x52,0x54,0x50,x 0x 50,0x50,x 0x 0x50,x ,0x62, 0x64,0x66,0x68,0x6a,0x6c,0x6e,0x70,0x72,0x74,0x76,0x78,0x7a,0x7c,0x7e, 0x80,0x82,0x84,0x86,0x08,x90,0x80,0x9 0x94, 0x96,0x98,0x9a,0x9c,0x9e, 0xa0,0xa2,0xa4,0xa6,0xa8,0xaa,0xac,0xae,0xb0,0xb2,0xb4,0xb6,0xb8,0xba,0x,x0x,c c6, 0xc8,0xca,0xcc,0xce,0xd0,0xd2,0xd4,0xd6,0xd8,0xda,0xdc,0xde, 0xe0,0xe2,0xe4,0xe6,0xe8,0xea,0xec,0f0,0xea,0xec,0f0,0x,fx0f,fx0f,8fx0f,fx0f,fx0f,fx0f,8 0xfa,0xfc,0xfe, 0x1b,0x19,0x1f,0x1d,0x13,0x11,0x17,0x15,0x0b,0x09,0x0f,0x0d,0x03,0x01,0x07,0x305,x,30,30,30,30,30 x31, 0x37,0x35,0x2b,0x29,0x2f,0x2d,0x23,0x21,0x27,0x25, 0x5b,0x59,0x5f,0x5d,0x53,0x51,0x57,0x55,0x40,x,x 0x47, 0x45, 0x7b,0x79,0x7f,0x7d,0x73,0x71,0x77,0x75,0x6b,0x69,0x6f,0x6d,0x63,0x61,0x67,0x65, 0x9b,9x90,x ,0x95, 0x8b,0x89,0x8f,0x8d,0x83,0x81,0x87,0x85, 0xbb,0xb9,0xbf,0xbd,0xb3,0xb1,0xb7,0xb5,0xab,0xa9,0x0xaf,ax,0x,0x,0xa9,0xaf,0x,0x,0x b, 0xd9,0xdf,0xdd,0xd3,0xd1,0xd7,0xd5,0xcb,0xc9,0xcf,0xcd,0xc3,0xc1,0xc7,0xc5, 0xfb,0xf9,0xff,0xfd,0xf,xfx,0xf,5fx,0xf,0xf,0xf,5 e9, 0xef,0xed,0xe3,0xe1,0xe7,0xe5
Multiplicera med 3:
0x00,0x03,0x06,0x05,0x0c,0x0f,0x0a,0x09,0x18,0x1b,0x1e,0x1d,0x14,0x17,0x12,0x11, 0x30,0x33,0x30,x,x30,0x33,0x30,x,x30,0x33,0x30,x 0x28, 0x2b,0x2e,0x2d,0x24,0x27,0x22,0x21, 0x60,0x63,0x66,0x65,0x6c,0x6f,0x6a,0x69,0x78,0x7b,0x7e,0x70,x 0x70,0x70,x 0x70,0x70,x ,0x53, 0x56,0x55,0x5c,0x5f,0x5a,0x59,0x48,0x4b,0x4e,0x4d,0x44,0x47,0x42,0x41, 0xc0,0xc3,0xc6,0xc5,0x0x,xc,xc00x,xc5,0x00,ca de, 0xdd,0xd4,0xd7,0xd2,0xd1, 0xf0,0xf3,0xf6,0xf5,0xfc,0xff,0xfa,0xf9,0xe8,0xeb,0xee,0xed,0xe4,0xe7,01,a,0xe,0xe,a,0xe,0xe,a 5, 0xac,0xaf,0xaa,0xa9,0xb8,0xbb,0xbe,0xbd,0xb4,0xb7,0xb2,0xb1, 0x90,0x93,0x96,0x95,0x9c,0x9f,0x9a,809,8x,809,8x,809,x , 0x87,0x82,0x81, 0x9b,0x98,0x9d,0x9e,0x97,0x94,0x91,0x92,0x83,0x80,0x85,0x86,0x8f,0x8c,0x89,0ab,0x7 xa4, 0xa1,0xa2,0xb3,0xb0,0xb5,0xb6,0xbf,0xbc,0xb9,0xba, 0xfb,0xf8,0xfd,0xfe,0xf7,0xf4,0xf1,0xf2,0xe3,0x,xe5,0xe3,0xe5,0xe3,0xe,0xe5,0xe5 , 0xea, 0xcb,0xc8,0xcd,0xce,0xc7,0xc4,0xc1,0xc2,0xd3,0xd0,0xd5,0xd6,0xdf,0xdc,0xd9,0xda, 0x5b,0x505,xd,5050,xd x52, 0x43,0x40,0x45,0x46,0x4f,0x4c,0x49,0x4a, 0x6b,0x68,0x6d,0x6e,0x67,0x64,0x61,0x62,0x73,0x70,0x70,x,x,x,x,x,x,x,x,x 0x3b, 0x38,0x3d,0x3e,0x37,0x34,0x31,0x32,0x23,0x20,0x25,0x26,0x2f,0x2c,0x29,0x2a, 0x0b,0x08,0x0d,0x00,x,000,0x,0x,00,0x,x 0x10, 0x15,0x16,0x1f,0x1c,0x19,0x1a
Multiplicera med 9:
0x00,0x09,0x12,0x1b,0x24,0x2d,0x36,0x3f,0x48,0x41,0x5a,0x53,0x6c,0x65,0x7e,0x77, 0x90,0x99,0x02,x00,b,x00,b,x00,b,x00,b,x xd8, 0xd1,0xca,0xc3,0xfc,0xf5,0xee,0xe7, 0x3b,0x32,0x29,0x20,0x1f,0x16,0x0d,0x04,0x73,0x7a,0x61,0x70,0x,0x60,0x,0x60,x xa2, 0xb9,0xb0,0x8f,0x86,0x9d,0x94,0xe3,0xea,0xf1,0xf8,0xc7,0xce,0xd5,0xdc, 0x76,0x7f,0x64,0x6d,0x500,x,05b,70x,x304x,0x30x,0x30x,0x30x,0x30x,0x30x,x x2c, 0x25,0x1a,0x13,0x08,0x01, 0xe6,0xef,0xf4,0xfd,0xc2,0xcb,0xd0,0xd9,0xae,0xa7,0xbc,0xb5,0x8a,0x804x,x,0x809,x,0x809,x,x,x, 0x56, 0x69,0x60,0x7b,0x72,0x05,0x0c,0x17,0x1e,0x21,0x28,0x33,0x3a, 0xdd,0xd4,0xcf,0xc6,0xf9,0xf0,0xeb,xf0,0xeb,xf0,0xeb,xf0,0xeb,8x09,8x09 xb1, 0xb8,0xa3,0xaa, 0xec,0xe5,0xfe,0xf7,0xc8,0xc1,0xda,0xd3,0xa4,0xad,0xb6,0xbf,0x80,0x89,0x92,0x9b, 7x07,x, 7x0,x, 7x50,x 1, 0x4a,0x43,0x34,0x3d,0x26,0x2f,0x10,0x19,0x02,0x0b, 0xd7,0xde,0xc5,0xcc,0xf3,0xfa,0xe1,0xe8,0x9f,x20bb,x209,8x9b,x9b,x20bb,x20bb,x9b , 0xa0, 0x47,0x4e,0x55,0x5c,0x63,0x6a,0x71,0x78,0x0f,0x06,0x1d,0x14,0x2b,0x22,0x39,0x30, 0x90a,0x70,b,x9a,809,b,x xa5, 0xd2,0xdb,0xc0,0xc9,0xf6,0xff,0xe4,0xed, 0x0a,0x03,0x18,0x11,0x2e,0x27,0x3c,0x35,0x42,0x4b,0x50,0x,7x,0x50,60,x,7 xa1, 0xa8,0xb3,0xba,0x85,0x8c,0x97,0x9e,0xe9,0xe0,0xfb,0xf2,0xcd,0xc4,0xdf,0xd6, 0x31,0x38,0x23,0x2a,00x,7x23,0x2a,000x,7 x70, 0x6b,0x62,0x5d,0x54,0x4f,0x46
Multiplicera med 11 (0xB):
0x00,0x0b,0x16,0x1d,0x2c,0x27,0x3a,0x31,0x58,0x53,0x4e,0x45,0x74,0x7f,0x62,0x69, 0xb0,0xbb,0xa90x,8x090x,8x090,8 e8, 0xe3,0xfe,0xf5,0xc4,0xcf,0xd2,0xd9, 0x7b,0x70,0x6d,0x66,0x57,0x5c,0x41,0x4a,0x23,0x28,0x35,0x3e,x00,1x00,1x0 0xc0, 0xdd, 0xd6,0xe7,0xec, 0xf1,0xfA, 0x93,0x98,0x85,0x8e, 0xbf, 0xb4,0xa9,0xa2, 0xf6,0xfd, 0xED 0xb3,0x82,0x89,0x94,0x9f, 0x46,0x4d,0x50,0x5b,0x6a,0x61,0x7c,0x77,0x1e,0x15,0x08,0x03,0x32,02x30,x,x,x,x,x,x,x,x ,0x90, 0xa1,0xaa,0xb7,0xbc,0xd5,0xde,0xc3,0xc8,0xf9,0xf2,0xef,0xe4, 0x3d,0x36,0x2b,0x20,0x11,0x1a,0x07,x,7x,0x,0x,0x,0x,0x,70x,x700 49, 0x42,0x5f,0x54, 0xf7,0xfc,0xe1,0xea,0xdb,0xd0,0xcd,0xc6,0xaf,0xa4,0xb9,0xb2,0x83,0x88,0x95,0x40,x,x,50x,50x,50x,6 0x60, 0x7d,0x76,0x1f,0x14,0x09,0x02,0x33,0x38,0x25,0x2e, 0x8c,0x87,0x9a,0x91,0xa0,0xab,0xb6,0xbd,0xd00c,x,f000x,fx200x,xf00x,f xee, 0xe5. ,0x30, 0x59,0x52.0x4f a, 0x71,0x6c,0x67,0x56,0x5d,0x40,0x4b,0x22,0x29,0x34,0x3f,0x0e,0x05,0x18,0x13, 0xca,0xc1,0xdc,0xd7,x,f,x00,f,x,f,x,f,x,f 99, 0x84,0x8f,0xbe,0xb5,0xa8,0xa3
Multiplicera med 13 (0xD):
0x00,0x0d,0x1a,0x17,0x34,0x39,0x2e,0x23,0x68,0x65,0x72,0x7f,0x5c,0x51,0x46,0x4b, 0xd0,0xdd,0xca,0x4c,0x4c,0x4c 8, 0xb5,0xa2,0xaf,0x8c,0x81,0x96,0x9b, 0xbb,0xb6,0xa1,0xac,0x8f,0x82,0x95,0x98,0xd3,0xde,0xc9,0xc4,0x,0x,0x,0x,0x,0x,0x,f 6, 0x71,0x7c,0x5f,0x52,0x45,0x48,0x03,0x0e,0x19,0x14,0x37,0x3a,0x2d,0x20, 0x6d,0x60,0x77,0x7a,0x40,x,x,0x40,x,0x40,x 0x1f, 0x12,0x31,0x3c,0x2b,0x26, 0xbd,0xb0,0xa7,0xaa,0x89,0x84,0x93,0x9e,0xd5,0xd8,0xcf,0xc2,0xe1,0x0x,0x0fcc,dx6fcc,0x0x,0x0fcc,dx xc1, 0xe2,0xef,0xf8,0xf5,0xbe,0xb3,0xa4,0xa9,0x8a,0x87,0x90,0x9d, 0x06,0x0b,0x1c,0x11,0x32,0x3f,0x28,60,x,70x,70x,0x28,4x,70x,70x,70x,700x,60x,x70x,x500x,9 5a, 0x57,0x40,0x4d. 0x33, 0x24,0x29,0x62,0x6f,0x78,0x75,0x56,0x5b,0x4c,0x41, 0x61,0x6c,0x7b,0x76,0x55,0x58,0x4f,0x42,0x09,x,x,0x,0x,0x,0x,0x,0 0x27, 0x2a, 0xb1,0xbc, 0xab, 0xa6,0x85,0x88,0x9f, 0x92,0xd9,0xd4,0xc3,0xce, 0xed, 0xE0,0,0xFA, 0xb7,0xba, 0xad, 0xa0,03,03,0x8, 0x8, 0x, 0xb7,0xba, 0xad, 0xa0,03,03,0x8, 0x, 0x, 0xb7,0xba, 0xad, 0xa0,03,03,0x8, 0x8, 0x, 0xb7,0xba, 0xad, 0xa0,03,03,0x8, 0x8, 0x, 0x9,0xba, 0xad, 0xa0,0,03,0x8,0x8E9, 0,0xa, 0xa0,0,0,03,03,0x8,0xer 0xdf,0xd2,0xc5,0xc8,0xeb,0xe6,0xf1,0xfc, 0x67,0x6a,0x7d,0x70,0x53,0x5e,0x49,0x44,0x0f,0x02,0x20,x,x02,0x10,x,x,x02,1x10,x,x 0x0c, 0x01,0x16,0x1b,0x38,0x35,0x22,0x2f,0x64,0x69,0x7e,0x73,0x50,0x5d,0x4a,0x47, 0xdc,0xd1,0xc6,0xcff,x0x0b,x0x0b,x0x0b,x0x0b,x0x0b,x0x0,x xb9, 0xae,0xa3,0x80,0x8d,0x9a,0x97
Multiplicera med 14 (0xE):
0x00,0x0e,0x1c,0x12,0x38,0x36,0x24,0x2a,0x70,0x7e,0x6c,0x62,0x48,0x46,0x54,0x5a, 0xe0,0xee,0x00d,x00d,x00d,x00d,x00d,x00d,x00d,x0x0d,x0x0d,x0x0d,xd x90, 0x9e,0x8c,0x82,0xa8,0xa6,0xb4,0xba, 0xdb,0xd5,0xc7,0xc9,0xe3,0xed,0xff,0xf1,0xab,0xa5,0xb7,0xb0xc9,x,f3030x,8x30x1 5, 0x27,0x29,0x03,0x0d,0x1f,0x11,0x4b,0x45,0x57,0x59,0x73,0x7d,0x6f,0x61, 0xad,0xa3,0xb1,0xbf,0x90x,xd,x900x,xd,xd c1, 0xcf,0xe5,0xeb,0xf9,0xf7, 0x4d,0x43,0x51,0x5f,0x75,0x7b,0x69,0x67,0x3d,0x33,0x21,0x2f,0x05,0x0b,0x,70x,70x,60x70 ,0x64, 0x4e,0x40,0x52,0x5c,0x06,0x08,0x1a,0x14,0x3e,0x30,0x22,0x2c, 0x96,0x98,0x8a,0x84,0xae,0xa0,0bc0x,x0,0x00,f xde, 0xd0,0xc2,0xcc, 0x41,0x4f,0x5d,0x53,0x79,0x77,0x65,0x6b,0x31,0x3f,0x2d,0x23,0x09,0x07,0x15,0x1b,x0af,x0af,x0af,x0af,x0af,x0af,x0af,x0af,x x97, 0x85,0x8b,0xd1,0xdf,0xcd,0xc3,0xe9,0xe7,0xf5,0xfb, 0x9a,0x94,0x86,0x88,0xa2,0xac,0xbe,0xb0,0x40ea,x0xd,xfxea,xfxea,xfxea,xfxd ce, 0xc0, 0x7a,0x74,0x66,0x68,0x42,0x4c,0x5e,0x50,0x0a,0x04,0x16,0x18,0x32,0x3c,0x2e,0x20, 0xec,0x00,x02,x02,x02,x02,x02,xd c6, 0x9c,0x92,0x80,0x8e,0xa4,0xaa,0xb8,0xb6, 0x0c,0x02,0x10,0x1e,0x34,0x3a,0x28,0x26,0x7c,0x72,0x50,x,x,0x,40,0x60,x,x 0x37, 0x39,0x2b,0x25,0x0f,0x01,0x13,0x1d,0x47,0x49,0x5b,0x55,0x7f,0x71,0x63,0x6d, 0xd7,0xd9,0xcb,0xc0x,fx,0x0x,f xa9, 0xbb,0xb5,0x9f,0x91,0x83,0x8d