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

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 

Se även