Rijndael MixColumns

The MixColumns step up jointly with the ShiftRows - step the primary Verschleierungsakt the Rijndael algorithm (AES ) dar. This article aims to show how this step works.

The matrix multiplication

In this step, a matrix multiplication of a column vector of the States with an MDS matrix takes place, so that all four input bytes affect every output byte.

The arithmetic, however, does not take place on the natural numbers, but on the Galois Field of Rijndael.

The Galois body of the Rijndael

The Galois body of the Rijndael, the Galois field.

Is the set of all polynomials up 7.Grades with coefficients from the residue field.

A general polynomial of has the form As is easy to see added, each of these polynomials represent by one byte, where each bit represents the -th coefficient.

The addition is defined analogously to the body as a XOR operation, she finds coefficient-wise or bit instead. The subtraction corresponds to the addition because the XOR operation is its own inverse. example:

The multiplication () takes place modulo the irreducible polynomial. To this end, we multiply the two polynomials and then calculated by means of a polynomial division the remainder, which must be noted that represent addition and subtraction XOR operations.

Example

For example, the calculation will be carried out by using. Figures unless otherwise specified, in hexadecimal.

It follows

The terms and are trivial.

As a result of XOR:

The reversal of the MixColums step

Decryption can in this step be carried out in the same manner as the encryption. However, one must multiply this by the inverse matrix. It reads ( numbers in hexadecimal):

Because

Ways to implement

The fact that the Rijndael for encryption to take place only multiplications, or, the algorithm can be very efficient and easy to implement on a computer.

The multiplication is trivial. The multiplication by means of binary shift by 1 bit to the left ( the modulo calculation needs to be considered separately ), and multiplication by can be in with a multiplication and split subsequent addition with itself. If an overflow occurs, so you have the intermediate result even with XOR link to obtain the correct result.

The following C code is just an example for a possible simple implementation and is not a reliable reference implementation

Unsigned char mul123 (unsigned char a, unsigned char b ) {    if ( b == 1)      return a;    else if ( b == 2)    {      unsigned char c = a << 1;      if ( a & 0x80)        c ^ = 0x1b;      return c;    }    else if ( b == 3 )    {      return mul123 (a, 2) ^ a;    }    else { exit EXIT_FAILURE }; } When decrypting However, this requires the multiplication with other numbers where the above approach is useless.

For suitable applies is bijective. The inverse function name. One such suitable is called a generator Examples would be the 3 or 5, but there are still some more.

Proof: Since finally, can the check through the math.

Since is bijective, applies to:

For valid

Now we create ourselves for the exponential and logarithm multiplication one for a generator, so we can implement to effectively using these general Multipliakation. The table can either be calculated at run time - with the above function, the generator 3 offers - or include source code.

Unsigned char RijndaelGaloisMul (unsigned char a, unsigned char b ) {    if ( a && b) / / if a! = 0 and b! = 0      return exp_table [( ln_table [a ] ln_table [b ] ) % 0xff ];    else      return 0; } Subsequently, the exponential and logarithm for the generator 3:

Powers:    | * 0 * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * a * b * c * d * e * f | -------------------------------------------------- -------------------- 0 * | 01 03 05 0f 11 33 55 ff 72 96 a1 f8 1a 2e 13 35 | 0 * 1 * | 5f e1 38 48 d8 73 95 f7 02 a4 06 22 66 0a 1e aa | 1 * 2 * | e5 34 37 59 eb 26 e4 5c 6a be d9 70 90 from e6 31 | 2 * 3 * | 53 f5 04 14 0c 44 cc 3c 4f b8 d1 68 d3 6e b2 cd | 3 * 4 * | 4 c d4 67 e0 a9 d7 3b 4d a6 62 f1 08 18 28 78 88 | 4 * 5 * | 83 9e b9 d0 6b bd dc 7f 81 98 b3 ce 49 db 76 9 | 5 * 6 * | b5 c4 57 f9 10 30 50 f0 27 0b 1d d6 61 69 bb a3 | 6 * 7 * | fe 19 7d 2b 87 92 ad ec 2f 71 93 ae e9 20 60 a0 | 7 * 8 * | fb 16 3a 4e 6d d2 b7 e7 5d c2 32 56 fa 15 3f 41 | 8 * 9 * | c3 5e e2 3d 47 c9 40 c0 5b ed 74 9c 2c bf since 75 | 9 * a * | 9f ba ac ef d5 64 2a 7e 82 9d bc df 7a 8e 89 80 | a * b * | 9b b6 c1 e8 58 23 65 6f 25 ea af b1 c8 43 54 c5 | b * c * | fc 1f 21 63 a5 07 09 f4 1b 2d 77 99 46 b0 cb ca | c * d * | 45 cf 4 de 79 8b 86 91 a8 e3 42 3e f3 c6 51 0e | d * e * | 12 36 ee 29 5a 7b 8d 8c 8f 8a 85 94 a7 f2 0d 17 | e * f * | 39 dd 4b 7c 84 97 24 6c 1c a2 fd b4 f6 c7 52 01 | f * logarithms:    | * 0 * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * a * b * c * d * e * f | -------------------------------------------------- -------------------- 0 * | - 00 19 01 32 02 1a 1b 68 33 c6 c7 4b ee df 03 | 0 * 1 * | 64 04 0e e0 34 8d 4c 81 ef 71 08 c8 69 f8 1c c1 | 1 * 2 * | 7d 1d b5 c2 f9 b9 27 6a 4d e4 a6 9a c9 72 09 78 | 2 * 3 * | 65 2f 05 21 8a e1 0f 24 12 f0 82 45 35 93 since 8e | 3 * 4 * | 96 db 8f d0 bd 36 ce 94 13 5c d2 f1 40 46 83 38 | 4 * 5 * | 66 dd fd 30 06 8b 62 bf b3 e2 25 98 22 88 91 10 | 5 * 6 * | 48 6e 7e c3 a3 b6 42 1e 3a 6b 28 54 fa 85 3d ba | 6 * 7 * | 0a 2b 79 15 9b 9f 5e ca 4e d4 e5 f3 73 ac a7 57 | 7 * 8 * | af 58 a8 f4 50 ea ae e9 d5 d6 4f 74 e6 e7 e8 ad | 8 * 9 * | 2c d7 7a 75 16 0b eb f5 59 cb 5f 9c a9 b0 51 a0 | 9 * a * | 7f 0c f6 c4 49 17 6f ec d8 43 1f 2d a4 b7 76 7b | a * b * | cc bb 3e 5a fb 60 86 3b 52 b1 a1 aa 6c 55 29 9d | b * c * | 97 b2 87 90 61 be dc fc bc cf cd 95 37 3f 5b d1 | c * d * | 53 39 84 41 3c 6d a2 47 14 2a 56 9e 5d f2 d3 from | d * e * | 44 11 92 d9 23 20 2e 89 b4 7c b8 26 77 99 a5 e3 | e * f * | 67 4a ed de fe c5 31 18 0d 63 c0 80 8c f7 70 07 | f * Web Links

• Tutorial on the AES encryption

• Symmetric Cryptosystem