AES MixColumns with Python

Question

I am trying to create an aes mix column function in python. But the result is not as expected. What am I doing wrong?

Here I test on the first column.

[2, 3, 1, 1, 1, 2, 3, 1, 1, 1, 2, 3, 3, 1, 1, 2]
[0, 17, 34, 51, 68, 85, 102, 119, 136, 153, 170, 187, 204, 221, 238, 255]

print((0*2)^(17*3)^(34*1)^(51*1))
print((0*1)^(17*2)^(34*3)^(51*1))
print((0*1)^(17*1)^(34*2)^(51*3))
print((0*3)^(17*1)^(34*1)^(51*2))

The result is as follows:

34
119
204
85

What I think is the expected result is:

34
119
0
85

Is the expected result wrong or am I doing wrong?

Answer 1

In the posted code, the multiplication is implemented wrongly. Multiplication is modulo irreducible polynomial x⁸ + x⁴ + x³ + x + 1 in the Galois field GF(2⁸). This is described in detail in the Wikipedia article Rijndael MixColumns. Here you can also find various implementations. Another, easier to understand description can be found on SO in the accepted answer to the post How to solve MixColumns?.

In the following implementation the multiplication (with 1, 2 and 3) is implemented in the function gmul():

def mixColumns(a, b, c, d):
    printHex(gmul(a, 2) ^ gmul(b, 3) ^ gmul(c, 1) ^ gmul(d, 1))
    printHex(gmul(a, 1) ^ gmul(b, 2) ^ gmul(c, 3) ^ gmul(d, 1))
    printHex(gmul(a, 1) ^ gmul(b, 1) ^ gmul(c, 2) ^ gmul(d, 3))
    printHex(gmul(a, 3) ^ gmul(b, 1) ^ gmul(c, 1) ^ gmul(d, 2))
    print()

def gmul(a, b):
    if b == 1:
        return a
    tmp = (a << 1) & 0xff
    if b == 2:
        return tmp if a < 128 else tmp ^ 0x1b
    if b == 3:
        return gmul(a, 2) ^ a

def printHex(val):
    return print('{:02x}'.format(val), end=' ')

# test vectors from https://en.wikipedia.org/wiki/Rijndael_MixColumns#Test_vectors_for_MixColumn()
mixColumns(0xdb, 0x13, 0x53, 0x45) # 0x8e 0x4d 0xa1 0xbc
mixColumns(0xf2, 0x0a, 0x22, 0x5c) # 0x9f 0xdc 0x58 0x9d
mixColumns(0x01, 0x01, 0x01, 0x01) # 0x01 0x01 0x01 0x01 
mixColumns(0xc6, 0xc6, 0xc6, 0xc6) # 0xc6 0xc6 0xc6 0xc6 
mixColumns(0xd4, 0xd4, 0xd4, 0xd5) # 0xd5 0xd5 0xd7 0xd6 
mixColumns(0x2d, 0x26, 0x31, 0x4c) # 0x4d 0x7e 0xbd 0xf8

# example from question
mixColumns(0, 17, 34, 51) # 0x22 0x77 0x00 0x55 = 34 119 0 85

with the output:

8e 4d a1 bc 
9f dc 58 9d 
01 01 01 01 
c6 c6 c6 c6 
d5 d5 d7 d6 
4d 7e bd f8 
22 77 00 55 

The first 6 lines are the results to the test vectors from the Wikipedia article. The last line corresponds to the example from the posted question: 0x22, 0x77, 0x00, 0x55 or 34, 119, 0, 85 decimal. As you can see, the third value is 0 not 204.