Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In Advanced Encryption Std, say after a ShiftRow operation, I want to perform MixColumns.

      State             MixColumn Matrix             Mixed
┏             ┓       ┏             ┓       ┏             ┓
┃ d4 e0 b8 1e ┃       ┃ 02 03 01 01 ┃       ┃ 04 e0 48 28 ┃ 
┃ bf b4 41 27 ┃       ┃ 01 02 03 01 ┃       ┃ 66 cb f8 06 ┃ 
┃ 5d 52 11 98 ┃       ┃ 01 01 02 03 ┃       ┃ 81 19 d3 26 ┃ 
┃ 30 ae f1 e5 ┃       ┃ 03 01 01 02 ┃       ┃ e5 9a 7a 4c ┃ 
┗             ┛       ┗             ┛       ┗             ┛

Example taken from this flash file. I'm puzzled by the description at Wikipedia.

The flash told that after MixColumns, the 1st column of State is turned into the 1st column of the Mixed matrix. How is this so?

First of all, how to multiply a column by a matrix? The shapes don't match, or is there anything special in cryptography? Well, if we transpose the column, I still don't understand: ($\cdot$ means dot product, and here are my Attempts)

# 1: [d4 bf 5d 30]$\cdot$[02 01 01 03] = d4+d4+bf+5d+30+30+30 = 54 != 04

# 2: [d4 bf 5d 30]$\cdot$[02 01 01 03] = d4+d4+bf+5d+((30<<1) ^ 30) = 14 != 04

# 3: [d4 bf 5d 30]$\cdot$[02 03 01 01] = d4+d4+bf+bf+bf+5d+30 = 72 != 04

# 4: [d4 bf 5d 30]$\cdot$[02 03 01 01] = d4+d4+((bf<<1)^30)^11b+5d+30 = 0F != 04

What's happening?

share|improve this question
    
11b here means 0x11b. I'm not sure if it's what Wikipedia means. ^ is xor. –  FrenzY DT. Dec 1 '12 at 5:06

1 Answer 1

up vote 1 down vote accepted

All the matrix entries are elements of the Galois field $GF(2^8)$, using field poynomial $x^8 + x^4 + x^3 + x + 1$. There is an excellent Wikipedia article Rijndael mix columns which explains this very clearly.

share|improve this answer
    
Thank you, it worked! But what is a Galois field, and what's the magic about $+$ being $\oplus$ and that polynomial? –  FrenzY DT. Dec 1 '12 at 8:34
    
A Galois field is just another name for a finite field. There is another Wikipedia article, Finite field arithmetic, which uses Rijndael's field as an example. –  TonyK Dec 1 '12 at 9:55
    
I'll take a look at it. You and Wikipedia really saved me today. –  FrenzY DT. Dec 1 '12 at 10:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.