Rijndael mix columns

Rijndael mix columns

The MixColumns operation performed by the Rijndael cipher, along with the shift-rows step, is the primary source of diffusion in Rijndael. Each column is treated as a polynomial over GF("28") and is then multiplied modulo x^4+1 with a fixed polynomial c(x) = 3x^3 + x^2 + x + 2; the inverse of this polynomial is c^{-1}(x) = 11x^3 + 13x^2 + 9x + 14.

MixColumns

The MixColumns step can be performed by multiplying a coordinate vector of four numbers in Rijndael's Galois field by the following MDS matrix:

:egin{bmatrix}r_0\r_1\r_2\r_3end{bmatrix} =egin{bmatrix}2&3&1&1 \1&2&3&1 \1&1&2&3 \3&1&1&2 end{bmatrix} egin{bmatrix}a_0\a_1\a_2\a_3end{bmatrix}

This can also be seen as the following:

:r_0 = 2a_0 + a_3 + a_2 + 3a_1:r_1 = 2a_1 + a_0 + a_3 + 3a_2:r_2 = 2a_2 + a_1 + a_0 + 3a_3:r_3 = 2a_3 + a_2 + a_1 + 3a_0

Since this math is done in Rijndael's Galois field, the addition above is actually an exclusive or operation, and multiplication is a complicated operation.

Implementation example

This can be simplified somewhat in actual implementation by replacing the multiply by 2 with a single shift and conditional exclusive or, and replacing a multiply by 3 with a multiply by 2 combined with an exclusive or. A C example of such an implementation follows:

void gmix_column(unsigned char *r) { unsigned char a [4] ; unsigned char b [4] ; unsigned char c; unsigned char h; /* The array 'a' is simply a copy of the input array 'r' * The array 'b' is each element of the array 'a' multiplied by 2 * in Rijndael's Galois field * a [n] ^ b [n] is element n multiplied by 3 in Rijndael's Galois field */ for(c=0;c<4;c++) { a [c] = r [c] ; h = r [c] & 0x80; /* hi bit */ b [c] = r [c] << 1; if(h = 0x80) b [c] ^= 0x1b; /* Rijndael's Galois field */ } 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 */}

Note that this implementation is vulnerable to a timing attack.

InverseMixColumns

The MixColumns operation has the following inverse (numbers are decimal):

:egin{bmatrix}14&11&13&9 \9&14&11&13 \13&9&14&11 \11&13&9&14 end{bmatrix} egin{bmatrix}a_0\a_1\a_2\a_3end{bmatrix}

Or:

:r_0 = 14a_0 + 9a_3 + 13a_2 + 11a_1:r_1 = 14a_1 + 9a_0 + 13a_3 + 11a_2:r_2 = 14a_2 + 9a_1 + 13a_0 + 11a_3:r_3 = 14a_3 + 9a_2 + 13a_1 + 11a_0

Test vectors

References

* [http://www.iaik.tu-graz.ac.at/research/krypto/AES/old/%7Erijmen/rijndael/rijndaeldocV2.zip Rijndael specification] (Zip compressed PDF file).
* [http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf FIPS PUB 197: the official AES standard] (PDF file)
* [http://www.samiam.org/mix-column.html Description of Rijndael's mix column operation]

ee also

* Advanced Encryption Standard


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Advanced Encryption Standard — Infobox block cipher name = AES caption = The SubBytes step, one of four stages in a round of AES designers = Vincent Rijmen, Joan Daemen publish date = 1998 derived from = Square derived to = Anubis, Grand Cru related to = certification = AES… …   Wikipedia

  • Advanced Encryption Standard — AES, Rijndael AES, Rijndael Создатель: Винсент Рэймен Йоан Даймен Созда …   Википедия

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • CRYPTON — Создатель: Че Хун Лим (Future Systems, Inc.) Создан: 1998 г …   Википедия

  • Anubis (cipher) — Infobox block cipher name = Anubis caption = designers = Vincent Rijmen and Paulo S. L. M. Barreto publish date = 2000 derived from = Rijndael derived to = key size = 128 to 320 bits in steps of 32 bits block size = 128 bits structure =… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”