By definition, branch number
Definition: The branch number of a linear transformation $F$ is $$min_{a\neq0}(W(a) + W(F(a)))$$
Source here (7.3.1)
For AES MixColumns $a \in GF(2^8)^4$ since the input is the four bytes in a column of the state.
Where $W(a)$ is a weight vector i.e. the number of nonzero components of the vector
$$a \in GF(2^m)^4, a = (a_1, \ldots, a_4)\\ W(a) \iff ||a|| = |\{i | a_i\neq 0 \}|, i = 1,\ldots,4$$
In AES uses a pre-defined matrix operations MixColumns. I need prove (like the proof of a theorem) that the branch number of matrix is equal to 5.
Questions:
In the same article (7.3.1) is said
the output can have at most 4 active bytes
and
Hence, the upper bound for the branch number is 5
In such a way that $W(F(a))$ the maximum can be $4$ (why?) and $W(a) = 1$. Why $W(a) = 1$, because the number of non-zero component can be greater than $1$? Or it is there to pay attention to $min()$?
How to calculate $W(F(a))$, for each $a \in GF(2^m)$ ?
The final answer:
Use theorem No. 2 (on page 4) here
is MDS if and only if every square submatrix of A is nonsingular
Ok, the initial data taken from here.
To test, I wrote a script test.py (see below) that:
- Defines all sub-matrices of the original
- For each of the sub-matrices calculate the determinant in GF(2^8)
- The result is an array of values of the determinant of each submatrix.
test.py
from functools import reduce
import sys
# ===========================Galois field===========================
# constants used in the multGF2 function
mask1 = mask2 = polyred = None
def setGF2(degree, irPoly):
# Define parameters of binary finite field GF(2^m)/g(x)
# - degree: extension degree of binary field
# - irPoly: coefficients of irreducible polynomial g(x)
def i2P(sInt):
# Convert integer into a polynomial
return [(sInt >> i) & 1
for i in reversed(range(sInt.bit_length()))]
global mask1, mask2, polyred
mask1 = mask2 = 1 << degree
mask2 -= 1
polyred = reduce(lambda x, y: (x << 1) + y, i2P(irPoly)[1:])
def multGF2(p1, p2):
# Multiply two polynomials in GF(2^m)/g(x)
p = 0
while p2:
if p2 & 1:
p ^= p1
p1 <<= 1
if p1 & mask1:
p1 ^= polyred
p2 >>= 1
return p & mask2
def determinant(matrix, mul):
width = len(matrix)
if width == 1:
return multGF2(mul, matrix[0][0])
else:
sign = 1
total = 0
for i in range(width):
m = []
for j in range(1, width):
buff = []
for k in range(width):
if k != i:
buff.append(matrix[j][k])
m.append(buff)
total = total ^ (multGF2(mul, determinant(m, multGF2(sign, matrix[0][i]))))
return total
# ===========================All submatrix===========================
import numpy as np
def get_all_sub_mat(mat):
rows = len(mat)
cols = len(mat[0])
def ContinSubSeq(lst):
size=len(lst)
for start in range(size):
for end in range(start+1,size+1):
yield (start,end)
for start_row,end_row in ContinSubSeq(list(range(rows))):
for start_col,end_col in ContinSubSeq(list(range(cols))):
yield [i[start_col:end_col] for i in mat[start_row:end_row] ]
def swap_cols(arr, frm, to):
arr = np.matrix(arr)
arr[:,[frm, to]] = arr[:,[to, frm]]
return arr.tolist()
def swap_rows(arr, frm, to):
arr = np.matrix(arr)
arr[[frm, to],:] = arr[[to, frm],:]
return arr.tolist()
def print_matrix(matrix):
matrix = np.matrix(matrix)
print matrix
submatrix = []
def foo(matrix):
for i in get_all_sub_mat(matrix):
if len(i) == len(i[0]) and len(i) != 1:
submatrix.append(i)
# Initial matrix
matrix = [
[2, 3, 1, 1],
[1, 2, 3, 1],
[1, 1, 2, 3],
[3, 1, 1, 2]
]
# All submatrix here
for i in [[0,0], [1,2], [1,3], [2,3]]:
_matrix = swap_cols(matrix, i[0], i[1])
for j in [[0,0], [1,2], [1,3], [2,3]]:
_matrix = swap_rows(matrix, i[0], i[1])
foo(_matrix)
# print len(submatrix) # 224
if __name__ == "__main__":
setGF2(8, 0b10001) # 0b10001 equal modulo x^4+1 from https://en.wikipedia.org/wiki/Rijndael_mix_columns
data = []
N = 2 ** 8
result = []
for m in submatrix:
result.append(determinant(m, 1))
print 'Final result: ', result
print '0 in result: ', 0 in result
Thanks @kodlu for the help!
