從 SBox 生成 ANF
給定一個 SBox，我如何生成它的分量方程（在ANF中）？
例如，假設我有這個 SBox：
6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11
那麼，方程是：
$ y_0 = x_1 \oplus x_0x_1 \oplus x_0x_2 \oplus x_1x_2 \oplus x_0x_3 \oplus x_0x_2x_3 \oplus x_1x_2x_3 $
$ y_1 = 1 \oplus x_0 \oplus x_2 \oplus x_0x_2 \oplus x_1x_2 \oplus x_0x_3 \oplus x_1x_3 $
$ y_2 = 1 \oplus x_0x_1 \oplus x_2 \oplus x_0x_2 \oplus x_0x_3 \oplus x_0x_1x_3 \oplus x_2x_3 \oplus x_1x_2x_3 $
$ y_3 = x_0x_1 \oplus x_3 \oplus x_0x_3 \oplus x_0x_1x_3 \oplus x_0x_2x_3 $
從 TRUTH TABLE 到 ANF
先寫
$$ 6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11 $$這樣：矩陣的列是那些數字 $ \mathbb{F_2^4} $ . $$ \begin{bmatrix} 0&0&1&0&0&1&0&0&0&1&1&1&0&1&1&1\ 1&0&1&0&0&0&1&1&1&1&0&0&0&1&0&1\ 1&1&1&0&0&1&0&0&1&0&1&0&1&1&0&0\ 0&0&0&1&0&0&0&1&1&0&1&0&1&1&1&1 \end{bmatrix} $$ 然後將其與 Moebius 變換矩陣相乘： $$ M_1 = \begin{bmatrix} 1 \end{bmatrix}, M_2 = \begin{bmatrix} 1&1\ 0&1 \end{bmatrix}, \cdots, M_{2^k} = M_2 \otimes M_{2^{k-1}} = \begin{bmatrix} M_{2^{k-1}}&M_{2^{k-1}}\ 0&M_{2^{k-1}} \end{bmatrix}. $$ 因此對於 $ k=4 $ ，矩陣為： $$ \begin{bmatrix} 1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 \ 0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 \ 0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1\ 0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1\ 0 &0 &0 &0 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1\ 0 &0 &0 &0 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1\ 0 &0 &0 &0 &0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1\ 0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1\ 0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &1 &1 &1 &1 &1 &1\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &1 &0 &1 &0 &1\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &0 &0 &1 &1\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &1\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &1 &1\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &1\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 \end{bmatrix} $$ 然後你有這個矩陣： $$ \begin{bmatrix} 0&0&1&1&0&1&1&0&0&1&0&0&0&1&1&0\ 1&1&0&0&1&1&1&0&0&1&1&0&0&0&0&0\ 1&0&0&1&1&1&0&0&0&1&0&1&1&0&1&0\ 0&0&0&1&0&0&0&0&1&1&0&1&0&1&0&0 \end{bmatrix} $$ 每行給出座標函式 $ S_1,S_2,S_3 $ 和 $ S_4 $ 分別 每行的條目是係數 $ 1, x_0, x_1, x_0x_1, x_2, x_0x_2, x_1x_2, x_0x_1x_2, x_3, x_0x_3, x_1x_3, x_0x_1x_3, x_2x_3, x_0x_2x_3, x_1x_2x_3, x_0x_1x_2x_3 $ . 從 ANF 到 TRUTH TABLE (TT)
正好是操作的逆。注意 $ M_{2^k}^{-1}=M_{2^k} $ 對於任何 $ k $ .
IE
$$ TT $$* $ [M] $ =$$ ANF $$和$$ TT $$=$$ ANF $$* $ [M] $ .
注意：算術取模 2。