如何找到 AES 分支編號？
根據定義，分支編號
**定義：**線性變換的分支數 $ F $ 是
$$ min_{a\neq0}(W(a) + W(F(a))) $$
對於 AES MixColumns $ a \in GF(2^8)^4 $ 因為輸入是狀態列中的四個字節。
在哪裡 $ W(a) $ 是一個權重向量，即向量的非零分量的數量
$$ 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 $$ 在 AES 中使用預定義的矩陣運算MixColumns。我需要證明（如證明定理）矩陣的分支數等於 5。
問題：
- 在同一篇文章（7.3.1）中說
輸出最多可以有 4 個活動字節
和
因此，分支編號的上限為 5
以這樣的方式 $ W(F(a)) $ 最大值可以是 $ 4 $ （為什麼？）和 $ W(a) = 1 $ . 為什麼 $ W(a) = 1 $ , 因為非零分量的個數可以大於 $ 1 $ ? 或者有需要注意的地方 $ min() $ ? 2. 如何計算 $ W(F(a)) $ , 對於每個 $ a \in GF(2^m) $ ?
最終答案：
在此處使用第 2 號定理（第 4 頁）
是 MDS 當且僅當 A 的每個平方子矩陣都是非奇異的
好的，從這裡獲取的初始數據。
為了測試，我編寫了一個腳本 test.py（見下文）：
- 定義原始的所有子矩陣
- 對於每個子矩陣，計算 GF(2^8) 中的行列式
- 結果是每個子矩陣的行列式值的數組。
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感謝@kodlu 的幫助！
AES MixColumns 運算符確保 8 個字節（輸入列中的 4 個字節，輸出列中的 4 個字節）構成 MDS 程式碼的程式碼字 $ GF(2^8) $ ，這意味著程式碼的最小權重為 5，等於非零字節數。
根據 Hamming Weight over 的定義，任何 nonzer 字節對最小權重貢獻 1 $ GF(2^8) $ . 一個非零符號的權重為 1，無論八位中有多少位是非零的。
有關更多資訊，請參閱此問題的答案。
**編輯：**單例界規定最小距離至少為 $ n-k+1. $ 這裡 $ n=8, k=4. $ 這樣的程式碼就是 MDS，證明 MDS 取決於程式碼結構。查找 MDS 程式碼和 Reed Solomon 程式碼。
更具體地說，線性碼是其奇偶校驗矩陣的零空間。因此，如果該矩陣具有其所有集合 $ d-1 $ 列線性獨立（超過 $ GF(2^8) $ 這裡）那麼它的最小權重碼字必須是 $ d $ 或者更多。此外，一個程式碼是 MDS 當且僅當它的對偶是 MDS，所以我們可以只考慮生成矩陣並觀察 4 列的所有集合 $ [A| I] $ 確實是線性獨立的。所以， $ d\geq 5. $ 但是通過單例綁定 $ d\leq 5. $ QED。
有關詳細資訊，請參閱以下連結：