證明高級加密標準數的分支
在高級加密標準 (AES) 文件中：第 27 頁第 7.3.1 節，它定義了分支號。它說
" 設 F 為作用於字節向量的線性變換，向量的字節權重為非零字節數。向量的字節權重表示為 $ W(a) $ .
定義：線性變換的分支數 $ F $ 是
$$ min_{a\neq0}(W(a) + W(F(a))) $$ 如果分支編號為 5，則 1 個輸入（或輸出）字節的差異傳播到所有 4 個輸出（或輸入）字節，2 個字節的輸入（或輸出）差異傳播到至少 3 個輸出（或輸入）字節。此外，輸入和輸出位之間的線性關係涉及來自輸入和輸出的至少 5 個不同字節的位。”
AES 選擇多項式 $ c(x)=03x^3+01x^2+01x+02 $ 構造 MixColumn 操作，其中係數是數字的十六進製表示 $ GF_{256} $ （例如 $ 03_{hexadecimal}= 0000 0011_{binary} =\alpha+1_{polynomial,representation} $ ) MixColumn 操作是通過乘法來完成的 $ c(x) $ 和模組 $ x^4+1 $
但是，該文件沒有給出數學證明。我的問題是
- 證明最大分支數為 $ 5 $ . 此外，AES MixColumn 可以達到最大值為 $ 5 $ .
- 給定一個分支號，如何構造線性變換 $ F(,) $ （在 AES 的情況下，它是 $ 5 $ ) ?
- 反過來，給定 $ F $ （一個矩陣），如何估計它的分支數？
例如，我應該如何證明如果線性變換是自逆的
（ $ ;(c(x))^2\equiv 1 ;mod,x^4+1 $ 或者 $ F^2=I $ )，那麼分支號最多為 $ 4 $ ?
我想這些問題與矩陣範數有關，但我不知道從哪裡開始解決這些問題。
親愛的使用者@kodlu 已經通過出色的討論回答了類似的問題，但我想用線性代數參數來回答。
MDS（最大距離可分離）矩陣有兩個定義：
**第一個定義：**矩陣 $ M $ 有秩序的 $ n $ 是 MDS 矩陣當且僅當 $ M $ 是非奇異的。
**第二個定義：**矩陣 $ M_{n\times n} $ 是 MDS 當且僅當
$$ Y_{n\times 1}=M_{n \times n}, X_{n \times 1} \Longrightarrow \mathop{\rm min}{X\neq 0}(W(Y)+W(X))=n+1 $$ 在哪裡 $ X={[x_0,x_1,\cdots , x{n-1}]}^T $ 和 $ Y={[y_0,y_1,\cdots , y_{n-1}]}^T $ 是任意域中的向量，並且 $ W(X) $ 是非零元素的數量 $ X $ .
現在，假設我們使用 MDS 矩陣（根據第一個定義）的順序 $ 4 $ 我們想通過第二個定義證明它的分支數是5。考慮我們的MDS矩陣如下
$$ M=\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] $$ 條目 $ m_{i,j} $ 非零，因為 $ M $ 首先定義是 MDS。現在考慮以下等式 $$ MX=Y \Longrightarrow \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\x_{{2}} \ x_{{3}}\ x_{{4}}\end {array} \right]= \left[ \begin {array}{c} y_{{1}}\ y_{{2}} \ y_{{3}}\ y_{{4}}\end {array} \right] $$ 在哪裡 $ x_i $ ‘沙 $ y_i $ 是有限域的元素。按第二個定義 $ X $ 應該是非零。為簡單起見，考慮 $ x_1\neq0 $ 和別的 $ x_i $ 可以為零或非零。 我們應該考慮一些案例來證明對於每一個選擇 $ x_2 $ , $ x_3 $ 和 $ x_4 $ ，至少有四個元素 $ x_2,x_3,x_4,y_1,y_2,y_3,y_4 $ 非零。
第一種情況是 $ x_2=x_3=x_4=0 $ . 在這種情況下，我們有：
$$ \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\0 \ 0\ 0\end {array} \right]= \left[ \begin {array}{c} x_1,m_{1,1}\ x_1,m_{2,1} \ x_1,m_{3,1}\ x_1,m_{4,1}\end {array} \right]= \left[ \begin {array}{c} y_{{1}}\ y_{{2}} \ y_{{3}}\ y_{{4}}\end {array} \right] $$ 因為 $ m_{i,j} $ ‘沙 $ x_1 $ 非零則元素 $ y_1,y_2,y_3,y_4 $ 是非零的。下一種情況是有非零值 $ x_2,x_3,x_4 $ 這樣 $$ \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\x_{{2}} \ x_{{3}}\ x_{{4}}\end {array} \right]= \left[ \begin {array}{c} 0\ 0 \ 0\ 0\end {array} \right] $$ 因為 $ M $ 矩陣是非奇異的，我們可以得出結論 $$ \left[ \begin {array}{c} x_{{1}}\x_{{2}} \ x_{{3}}\ x_{{4}}\end {array} \right]= \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right]^{-1}\left[ \begin {array}{c} 0\ 0 \ 0\ 0\end {array} \right]=\left[ \begin {array}{c} 0\ 0 \ 0\ 0\end {array} \right] $$ 這與我們的假設相矛盾 $ x_1,x_2,x_3,x_4\neq 0 $ 所以其中之一 $ y_1,y_2,y_3,y_4 $ 應該是非零。 下一個案例是：例如 $ x_1\neq0, x_2\neq0 ,x_3=x_4=0 $ 結果 $ y_1\neq0, y_2\neq0 ,y_3=y_4=0 $ . 考慮有這種情況如下
$$ \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\x_2 \ 0\ 0\end {array} \right]= \left[ \begin {array}{c} y_{{1}}\ y_{{2}} \ 0\ 0\end {array} \right] $$ 所以我們有 $$ \left[ \begin {array}{cc} m_{{3,1}}&m_{{3,2}}\ m_{ {4,1}}&m_{{4,2}}\end {array} \right] \left[ \begin {array}{c} x_{{1}}\ x_{{2}} \end {array} \right]= \left[ \begin {array}{c} 0\ 0\end {array} \right] $$ 從第一個定義的所有子矩陣 $ M $ 具有非零行列式，因此我們可以從上面的等式得出結論， $ x_1=x_2=0 $ 這與我們的假設相矛盾。 其他情況與提到的情況類似，並且從這個事實來看，所有的子矩陣 $ M $ 有非零行列式。
希望對你有幫助。