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!
