Pseudo-code for MixColumns

MixColumns()

T. Jameson Little
CS 465
MixColumns Pseudo code homework

Globals
=======

    mix_column_matrix = [
        [02, 03, 01, 01],
        [01, 02, 03, 01],
        [01, 01, 02, 03],
        [03, 01, 01, 02]
    ]

    // represents x^8 + x^4 + x^3 + x + 1
    m = 0x011b

Helpers
=======

    // a mod m, where a and m are both binary polynomials
    // this function simulates polynomial long division:
    //   _____
    // m | a
    // 
    // long division continues as long as the degree of a
    // is greater-than or equal to m
    def poly_mod(a):
        while a.degree() >= m.degree():
            // get the degree of the next result
            diff = a.degree() - m.degree()

            // same as adding diff to each element in m
            t = m.shift(diff)

            // toggle all bits in a that are set in t
            // this will decrease the power of a by the way we defined t
            a = t.xor(a)

        return a

    // multiply two binary polynomials
    def poly_mul(a, b):
        ret = 0
        // iterate over the bits that are set
        for i in a.bits_set():
            // polynomial multiplication is just xor with b shifted by this bits index
            ret = ret.xor(b << i)
        return poly_mod(ret)

MixColumns()
============

    def mix_columns(state):
        // for each column in the state
        for i,col in state.cols():
            ret = col.copy()
            // multiply it by mix_column_matrix
            for j,row in mix_column_matrix.rows():
                v = 0
                for k in 0 .. 4:
                    // finite field multiply
                    prod = poly_mul(col[k], row[k])
                    
                    // in finite field math, addition is an xor
                    v = v.xor(prod)
                ret[j] = v
            state.set_col(i, ret)