Skip to content

Instantly share code, notes, and snippets.

@beatgammit
Created September 10, 2013 20:47
Show Gist options
  • Save beatgammit/6515458 to your computer and use it in GitHub Desktop.
Save beatgammit/6515458 to your computer and use it in GitHub Desktop.
Pseudo-code for 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment