MixColumns Rijndael

Langkah MixColumns dan langkah ShiftRows adalah sumber penghamburan utama dalam penyandian Rijndael. Tiap kolom dianggap sebagai suku banyak berderajat empat b ( x ) = b 3 x 3 + b 2 x 2 + b 1 x + b 0 {\displaystyle b(x)=b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}} yang suku-sukunya berada dalam GF ⁡ ( 2 8 ) {\displaystyle \operatorname {GF} (2^{8})} .

Tiap kolom dikali dengan suku banyak tetap a ( x ) = 3 x 3 + x 2 + x + 2 {\displaystyle a(x)=3x^{3}+x^{2}+x+2} modulus x 4 + 1 {\displaystyle x^{4}+1} . Inversi suku banyaknya adalah a − 1 ( x ) = 11 x 3 + 13 x 2 + 9 x + 14 {\displaystyle a^{-1}(x)=11x^{3}+13x^{2}+9x+14} .

MixColumns

Operasi ini terdiri dari perkalian modulus dua suku banyak berderajat empat yang koefisiennya ada dalam GF ⁡ ( 2 8 ) {\displaystyle \operatorname {GF} \left(2^{8}\right)} . Pembagi yang dipakai dalam operasi ini adalah x 4 + 1 {\displaystyle x^{4}+1} .

Koefisien suku banyak pertama didefinisikan sebagai kolom status [ b 3 b 2 b 1 b 0 ] {\displaystyle {\begin{bmatrix}b_{3}&b_{2}&b_{1}&b_{0}\end{bmatrix}}} yang berisi empat bita. Tiap bita adalah koefisien dari suku banyak tersebut.

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

Suku banyak kedua adalah suku banyak tetap a ( x ) = 3 x 3 + x 2 + x + 2 {\displaystyle a(x)=3x^{3}+x^{2}+x+2} . Koefisiennya juga ada dalam GF ⁡ ( 2 8 ) {\displaystyle \operatorname {GF} \left(2^{8}\right)} . Inversinya adalah a − 1 ( x ) = 11 x 3 + 13 x 2 + 9 x + 14 {\displaystyle a^{-1}(x)=11x^{3}+13x^{2}+9x+14} .

Dalam halaman ini, kita definisikan beberapa notasi berikut:

⊗ {\displaystyle \otimes } berarti perkalian modulus x 4 + 1 {\displaystyle x^{4}+1} .

⊕ {\displaystyle \oplus } berarti pertambahan dalam GF ⁡ ( 2 8 ) {\displaystyle \operatorname {GF} \left(2^{8}\right)} .

∙ {\displaystyle \bullet } berarti perkalian dalam GF ⁡ ( 2 8 ) {\displaystyle \operatorname {GF} \left(2^{8}\right)} .

Pertambahan dalam GF ⁡ ( 2 8 ) {\displaystyle \operatorname {GF} \left(2^{8}\right)} memiliki sifat berikut:

( a 3 x 3 + a 2 x 2 + a 1 x + a 0 ) + ( b 3 x 3 + b 2 x 2 + b 1 x + b 0 ) = ( a 3 ⊕ b 3 ) x 3 + ( a 2 ⊕ b 2 ) x 2 + ( a 1 ⊕ b 1 ) x + ( a 0 ⊕ b 0 ) {\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}}}

Pembuktian bentuk matriks

Suku banyak a ( x ) = 3 x 3 + x 2 + x + 2 {\displaystyle a(x)=3x^{3}+x^{2}+x+2} akan dinyatakan sebagai a ( x ) = a 3 x 3 + a 2 x 2 + a 1 x + a 0 {\displaystyle a(x)=a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}} .

Perkalian suku banyak

a ( x ) ∙ b ( x ) = c ( x ) = ( a 3 x 3 + a 2 x 2 + a 1 x + a 0 ) ∙ ( b 3 x 3 + b 2 x 2 + b 1 x + b 0 ) = 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 {\displaystyle {\begin{aligned}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{aligned}}}

dengan

c 0 = a 0 ∙ b 0 c 1 = a 1 ∙ b 0 ⊕ a 0 ∙ b 1 c 2 = a 2 ∙ b 0 ⊕ a 1 ∙ b 1 ⊕ a 0 ∙ b 2 c 3 = a 3 ∙ b 0 ⊕ a 2 ∙ b 1 ⊕ a 1 ∙ b 2 ⊕ a 0 ∙ b 3 c 4 = a 3 ∙ b 1 ⊕ a 2 ∙ b 2 ⊕ a 1 ∙ b 3 c 5 = a 3 ∙ b 2 ⊕ a 2 ∙ b 3 c 6 = a 3 ∙ b 3 {\displaystyle {\begin{aligned}c_{0}&=a_{0}\bullet b_{0}\\c_{1}&=a_{1}\bullet b_{0}\oplus a_{0}\bullet b_{1}\\c_{2}&=a_{2}\bullet b_{0}\oplus a_{1}\bullet b_{1}\oplus a_{0}\bullet b_{2}\\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}\\c_{4}&=a_{3}\bullet b_{1}\oplus a_{2}\bullet b_{2}\oplus a_{1}\bullet b_{3}\\c_{5}&=a_{3}\bullet b_{2}\oplus a_{2}\bullet b_{3}\\c_{6}&=a_{3}\bullet b_{3}\end{aligned}}}

Reduksi modulus

Hasil c ( x ) {\displaystyle c(x)} adalah suku banyak berderajat tujuh sehingga harus direduksi menjadi kata empat bita. Hal itu dilakukan dengan melakukan perkalian dengan modulus x 4 + 1 {\displaystyle x^{4}+1} .

Bila kita melakukan perkalian modulus suku banyak, kita bisa lihat bahwa

x 6 mod ( x 4 + 1 ) = − x 2 = x 2  dalam  GF ⁡ ( 2 8 ) x 5 mod ( x 4 + 1 ) = − x = x  dalam  GF ⁡ ( 2 8 ) x 4 mod ( x 4 + 1 ) = − 1 = 1  dalam  GF ⁡ ( 2 8 ) {\displaystyle {\begin{aligned}x^{6}{\bmod {\left(x^{4}+1\right)}}&=-x^{2}=x^{2}{\text{ dalam }}\operatorname {GF} \left(2^{8}\right)\\x^{5}{\bmod {\left(x^{4}+1\right)}}&=-x=x{\text{ dalam }}\operatorname {GF} \left(2^{8}\right)\\x^{4}{\bmod {\left(x^{4}+1\right)}}&=-1=1{\text{ dalam }}\operatorname {GF} \left(2^{8}\right)\end{aligned}}}

Secara umum, kita bisa nyatakan bahwa x i mod ( x 4 + 1 ) = x i mod 4 . {\displaystyle x^{i}{\bmod {\left(x^{4}+1\right)}}=x^{i{\bmod {4}}}.}

Jadi,

a ( x ) ⊗ b ( x ) = c ( x ) mod ( x 4 + 1 ) = ( 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 ) mod ( x 4 + 1 ) = c 6 x 6 mod 4 + c 5 x 5 mod 4 + c 4 x 4 mod 4 + c 3 x 3 mod 4 + c 2 x 2 mod 4 + c 1 x 1 mod 4 + c 0 x 0 mod 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 + ( c 2 ⊕ c 6 ) x 2 + ( c 1 ⊕ c 5 ) x + c 0 ⊕ c 4 = d 3 x 3 + d 2 x 2 + d 1 x + d 0 {\displaystyle {\begin{aligned}&a(x)\otimes b(x)=c(x){\bmod {\left(x^{4}+1\right)}}\\={}&\left(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{aligned}}}

dengan

d 0 = c 0 ⊕ c 4 d 1 = c 1 ⊕ c 5 d 2 = c 2 ⊕ c 6 d 3 = c 3 {\displaystyle {\begin{aligned}d_{0}&=c_{0}\oplus c_{4}\\d_{1}&=c_{1}\oplus c_{5}\\d_{2}&=c_{2}\oplus c_{6}\\d_{3}&=c_{3}\end{aligned}}}

Bentuk matriks

Koefisien d 3 {\displaystyle d_{3}} , d 2 {\displaystyle d_{2}} , d 1 {\displaystyle d_{1}} , dan d 0 {\displaystyle d_{0}} dapat dinyatakan sebagai berikut:

d 0 = a 0 ∙ b 0 ⊕ a 3 ∙ b 1 ⊕ a 2 ∙ b 2 ⊕ a 1 ∙ b 3 d 1 = a 1 ∙ b 0 ⊕ a 0 ∙ b 1 ⊕ a 3 ∙ b 2 ⊕ a 2 ∙ b 3 d 2 = a 2 ∙ b 0 ⊕ a 1 ∙ b 1 ⊕ a 0 ∙ b 2 ⊕ a 3 ∙ b 3 d 3 = a 3 ∙ b 0 ⊕ a 2 ∙ b 1 ⊕ a 1 ∙ b 2 ⊕ a 0 ∙ b 3 {\displaystyle {\begin{aligned}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}\\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}\\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}\\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}\end{aligned}}}

Ketika kita ganti koefisien a ( x ) {\displaystyle a(x)} dengan tetapan [ 3 1 1 2 ] {\displaystyle {\begin{bmatrix}3&1&1&2\end{bmatrix}}} yang dipakai oleh penyandian ini, kita dapatkan hasil berikut:

d 0 = 2 ∙ b 0 ⊕ 3 ∙ b 1 ⊕ 1 ∙ b 2 ⊕ 1 ∙ b 3 d 1 = 1 ∙ b 0 ⊕ 2 ∙ b 1 ⊕ 3 ∙ b 2 ⊕ 1 ∙ b 3 d 2 = 1 ∙ b 0 ⊕ 1 ∙ b 1 ⊕ 2 ∙ b 2 ⊕ 3 ∙ b 3 d 3 = 3 ∙ b 0 ⊕ 1 ∙ b 1 ⊕ 1 ∙ b 2 ⊕ 2 ∙ b 3 {\displaystyle {\begin{aligned}d_{0}&=2\bullet b_{0}\oplus 3\bullet b_{1}\oplus 1\bullet b_{2}\oplus 1\bullet b_{3}\\d_{1}&=1\bullet b_{0}\oplus 2\bullet b_{1}\oplus 3\bullet b_{2}\oplus 1\bullet b_{3}\\d_{2}&=1\bullet b_{0}\oplus 1\bullet b_{1}\oplus 2\bullet b_{2}\oplus 3\bullet b_{3}\\d_{3}&=3\bullet b_{0}\oplus 1\bullet b_{1}\oplus 1\bullet b_{2}\oplus 2\bullet b_{3}\end{aligned}}}

Hal ini menunjukkan bahwa operasi ini mirip dengan sandi Hill. Ia dapat digambarkan sebagai perkalian matriks berikut:

[ d 0 d 1 d 2 d 3 ] = [ 2 3 1 1 1 2 3 1 1 1 2 3 3 1 1 2 ] [ b 0 b 1 b 2 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}}}

InverseMixColumns

Operasi MixColumns memiliki inversi berikut (bilangan dalam desimal).

[ b 0 b 1 b 2 b 3 ] = [ 14 11 13 9 9 14 11 13 13 9 14 11 11 13 9 14 ] [ d 0 d 1 d 2 d 3 ] {\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}}}

atau

b 0 = 14 ∙ d 0 ⊕ 11 ∙ d 1 ⊕ 13 ∙ d 2 ⊕ 9 ∙ d 3 b 1 = 9 ∙ d 0 ⊕ 14 ∙ d 1 ⊕ 11 ∙ d 2 ⊕ 13 ∙ d 3 b 2 = 13 ∙ d 0 ⊕ 9 ∙ d 1 ⊕ 14 ∙ d 2 ⊕ 11 ∙ d 3 b 3 = 11 ∙ d 0 ⊕ 13 ∙ d 1 ⊕ 9 ∙ d 2 ⊕ 14 ∙ d 3 {\displaystyle {\begin{aligned}b_{0}&=14\bullet d_{0}\oplus 11\bullet d_{1}\oplus 13\bullet d_{2}\oplus 9\bullet d_{3}\\b_{1}&=9\bullet d_{0}\oplus 14\bullet d_{1}\oplus 11\bullet d_{2}\oplus 13\bullet d_{3}\\b_{2}&=13\bullet d_{0}\oplus 9\bullet d_{1}\oplus 14\bullet d_{2}\oplus 11\bullet d_{3}\\b_{3}&=11\bullet d_{0}\oplus 13\bullet d_{1}\oplus 9\bullet d_{2}\oplus 14\bullet d_{3}\end{aligned}}}

Contoh implementasi

Operasi ini dapat disederhanakan dalam implementasinya dengan mengganti perkalian dengan dua dengan geseran tunggal dan XOR bersyarat serta mengganti perkalian dengan tiga dengan perkalian dengan dua yang digabung dengan XOR. Berikut contoh implementasi dalam bahasa C.

voidgmix_column(unsignedchar*r){
unsignedchara[4];
unsignedcharb[4];
unsignedcharc;
unsignedcharh;
/* Larik a adalah salinan dari larik r.
	 * Larik b adalah larik a yang dikali dua dalam medan berhingga Rijndael.
	 * a[n] ^ b[n] adalah perkalian dengan tiga dalam medan berhingga Rijndael.
	 */
for(c=0;c<4;c++){
a[c]=r[c];
/* h adalah 0xff jika bit tinggi r[c] diatur; nilainya 0 jika tidak */
h=(unsignedchar)((signedchar)r[c]>>7);/* geseran aritmetika kanan */
b[c]=r[c]<<1;/* secara tersirat menghapus bit tinggi karena b[c] adalah char 8 bit,
		                   * maka di-XOR dengan 0x1B dan bukan 0x11B pada baris selanjutnya */
b[c]^=0x1B&h;/* medan berhingga Rijndael */
}
r[0]=b[0]^a[3]^a[2]^b[1]^a[1];/* 2 * a0 + a3 + a2 + 3 * a1 */
r[1]=b[1]^a[0]^a[3]^b[2]^a[2];/* 2 * a1 + a0 + a3 + 3 * a2 */
r[2]=b[2]^a[1]^a[0]^b[3]^a[3];/* 2 * a2 + a1 + a0 + 3 * a3 */
r[3]=b[3]^a[2]^a[1]^b[0]^a[0];/* 2 * a3 + a2 + a1 + 3 * a0 */
}

Vektor uji untuk MixColumns

Daftar pustaka

• FIPS PUB 197: Dokumen resmi AES