目標分組密碼輪函式安全措施
在嘗試評估分組密碼的輪函式的安全性時可能出現的一個問題是，對輪函式的分析並未將輪密鑰空間和消息空間僅視為集合，而是視為更複雜的結構。例如，如果消息空間是 $ {0,1}^{n} $ ，則消息空間具有額外的數學結構，因為 $ {0,1}^{n} $ 始終是布爾代數。此外，輪函式可能不被視為簡單的函式，而是被視為用於計算函式的電路。這可能是一個問題，因為分組密碼可能看起來或多或少比實際安全，因為這樣的分組密碼已經在輪密鑰空間和消息空間的附加結構的上下文中進行了評估。
以什麼方式可以評估分組密碼的輪函式，同時將輪密鑰空間和消息空間視為簡單的集合，除了輪函式本身之外沒有任何額外的數學結構？
讓 $ K,X $ 是有限集。讓 $ F:K\times X\rightarrow X $ 是一個函式，如果 $ k\in K $ ，然後讓 $ F_{k}:X\rightarrow X $ 是定義的函式 $ F_{k}(x)=F(k,x) $ 每當 $ x\in X $ . 假設每個 $ F_{k} $ 是雙射。那我們就說 $ F $ 是分組密碼輪函式。
假設 $ F_{i}:K_{i}\times X_{i}\rightarrow X_{i} $ 是分組密碼輪函式 $ i\in{1,2} $ . 假設 $ \phi:K_{1}\rightarrow K_{2},\psi:X_{1}\rightarrow X_{2} $ 是雙射。然後我們說 $ (\phi,\psi) $ 是來自的同構 $ F_{1} $ 至 $ F_{2} $ 如果 $ \psi(F_{1}(k,x))=F_{2}(\phi(k),\psi(x)) $ 每當 $ k\in K_{1},x\in X_{1} $ ，我們說 $ F_{1} $ 和 $ F_{2} $ 是同構的，如果有一些同構來自 $ F_{1} $ 至 $ F_{2} $ . 我們將說一個函式 $ M $ 是圓函式不變參數 if $ M(F)=M(G) $ 每當 $ F,G $ 是同構分組密碼輪函式。
輪函式不變參數 $ M $ 被認為是一種客觀的安全措施，如果 $ M(F)\in[-\infty,\infty] $ 對於每個輪函式 $ F $ 並且其中較高的值 $ M(F) $ 表明圓函式 $ F $ 更安全。
現代輪函式評估或估計了哪些客觀的安全措施？在評估分組密碼、密碼散列函式或其他密碼對象（例如在 NIST 密碼競賽中）的密碼安全性時，是否考慮了這些客觀的安全措施？
在這篇文章中，我不僅對用於對稱加密的分組密碼感興趣，而且對用於其他目的的分組密碼感興趣，例如使用 Davies-Meyer 構造建構密碼散列函式。
例子
在某些情況下，可以恢復一些數學結構 $ K,X $ 從輪函式 $ F $ 並使用這個附加結構來獲得輪函式不變參數。
假設 $ K,X $ 是場上的向量空間 $ F_{p} $ 和 $ p $ 一些素數的元素 $ p $ . 假設 $ \iota:K\rightarrow X $ 是向量空間同構。讓 $ P:X\rightarrow X $ 是一個排列，並假設 $ F:K\times X\rightarrow X $ 是通過讓定義的分組密碼輪函式 $ F(k,x)=\iota(k)+P(x) $ . 定義三元運算 $ L,M $ 在集 $ K,X $ 這樣 $ L(j,k,l)=j-k+l $ 每當 $ j,k,l\in K $ 和 $ M(x,y,z)=x-y+z $ 每當 $ x,y,z\in M $ . 然後是操作 $ L,M $ 在兩個排序結構中是一階可定義的 $ (K,X,F) $ . 操作 $ L,M $ 應該被認為是類似於向量空間操作的操作，但是空間 $ (K,L),(X,M) $ 沒有可以設置為原點的已定義基點。
現在，假設 $ s $ 是一個正整數。為了使我們的構造更方便，假設 $ \dim(K)=\dim(X)=p^{N}-1 $ . 現在，讓 $ V $ 是一個隨機選擇的製服 $ N $ -維仿射子空間 $ X $ ， 然後讓 $ k_{1},\dots,k_{u} $ 是均勻隨機選擇的元素 $ K $ . 然後定義$$ \mathcal{R}{s}=\dim({F{k_{1}}\circ\dots\circ F_{k_{u}}(v)\mid v\in V}). $$
因此可以定義一個輪函式不變參數 $ M_{s} $ 以便 $ M_{s}(F)=E(\mathcal{R}{s}) $ （並且可以設置 $ M{s}(F)=0 $ 每當隨機變數 $ \mathcal{R}{s} $ 對於分組密碼輪函式沒有意義 $ F $ ）。這裡的值更高 $ M{s}(F) $ 建議分組密碼輪函式具有更高級別的非線性和密碼安全性 $ F $ . 可以定義許多其他類似的輪函式不變參數 $ N $ 以便 $ N(F) $ 是分組密碼輪函式非線性的度量 $ F $ .
相當多的結構實際上可以根據分組密碼輪函式定義，並且從這個結構中，可以產生測量密碼安全性的分組密碼輪函式不變數。
這個答案的一部分與我之前的答案基本相同，所以在這種情況下，我們將省略結果的證明。
如果 $ G,H $ 是組，那麼我們說一個函式 $ \phi:G\rightarrow H $ 如果存在群同態，則為堆同態 $ \psi:G\rightarrow H $ 連同一個 $ b\in H $ 在哪裡 $ \phi(g)=b\psi(g) $ 對所有人 $ b\in B. $ 等效地，映射 $ \phi:G\rightarrow H $ 是堆同態當且僅當 $ \phi(xy^{-1}z)=\phi(x)\phi(y)^{-1}\phi(z) $ 每當 $ x,y,z\in G $ . 雙射堆同態被稱為堆自同態。
對於這篇文章，讓 $ U_{0},\dots,U_{n-1},V_{0},\dots,V_{n-1} $ 成為團體。假設 $ I_{i}:U_{i}\rightarrow V_{i} $ 是群同構 $ 0\leq i<n $ . 讓 $ K=U_{0}\times\dots\times U_{n-1},X=V_{0}\times\dots\times V_{n-1} $ . 然後定義一個群同構 $ \iota:K\rightarrow X $ 通過讓 $ \iota(u_{0},\dots,u_{n-1})=(I_{0}(u_{0}),\dots,I_{n-1}(u_{n-1})) $ .
如果 $ 0\leq i<n $ ，然後讓 $ s_{i}:V_{i}\rightarrow V_{i} $ 是任意雙射。定義映射 $ S:V_{0}\times\dots\times V_{n-1}\rightarrow V_{0}\times\dots\times V_{n-1} $ 通過讓 $ S(v_{0},\dots,v_{n-1})=(s_{0}(v_{0}),\dots,s_{n-1}(v_{n-1})) $ . 讓 $ \Gamma:X\rightarrow X $ 是一個堆自同構。讓 $ P=\Gamma\circ S $ , 並定義一個映射 $ F:K\times X\rightarrow X $ 通過讓 $ F(k,x)=\iota(k)P(x) $ .
命題：映射 $ K^{2}\times X\rightarrow X,(j,k,x)\mapsto\iota(jk^{-1})x $ 和 $ X^{3}\rightarrow X,(x,y,z)\mapsto xy^{-1}z $ 是一階可定義的 $ (K,X,F) $ .
讓 $ \pi_{i}:X\rightarrow V_{i} $ 為投影群同態。讓 $ \simeq_{i} $ 是上的等價關係 $ X $ 我們設置的地方 $ x\simeq_{i}y $ 當且僅當 $ \pi_{i}(x)=\pi_{i}(y) $ . 我聲稱等價關係的集合 $ {\simeq_{0},\dots,\simeq_{n-1}} $ 是高階可定義的 $ (K,X,F) $ 在關於分組密碼的合理假設下 $ F $ ，但為了證明這一說法，我們需要復習一些引理。從可定義性 $ {\simeq_{0},\dots,\simeq_{n-1}} $ ，我們可以產生許多測量非線性和雪崩效應的分組密碼輪函式不變數。
為了 $ 0\leq i<n $ ， 和 $ j\in U_{i} $ ， 讓 $ s_{i}^{j} $ 是的排列 $ V_{i} $ 通過讓定義 $ s_{i}^{j}(v)=I_{i}(j)s_{i}(v) $ .
如果 $ 0\leq i<n $ ，然後讓 $ H_{i} $ 是所有排列的群 $ V_{i} $ 由產生 $ s_{i}^{j}\circ(s_{i}^{k})^{-1},(s_{i}^{j})^{-1}\circ s_{i}^{k} $ .
讓 $ H $ 是所有排列的群 $ X $ 由形式的所有排列生成 $ F_{j}^{-1}\circ F_{k},F_{j}\circ F_{k}^{-1} $ . 請注意 $ F_{j}\circ F_{k}^{-1}(x)=\iota(jk^{-1})(x) $ 和 $ F_{j}^{-1}\circ F_{k}(x)=S^{-1}[\Gamma^{-1}[\iota(j^{-1}k)]S(x)] $ . 尤其是， $ H $ 由形式的排列生成 $ x\mapsto\iota(m)(x) $ 連同形式的排列 $ S^{-1}[\iota(m)S(x)] $ . 換個說法， $ H $ 由形式的排列生成 $$ (x_{0},\dots,x_{n-1})\mapsto(I_{0}(m_{0})(x_{0}),\dots,I_{n-1}(m_{n-1})(x_{n-1})) $$和 $$ (x_{0},\dots,x_{n-1})\mapsto(s_{0}^{-1}[I_{0}(m_{0})(s_{0}(x_{n-1}))],\dots,s_{n-1}^{-1}[I_{n-1}(m_{n-1})(s_{n-1}(x_{n-1}))]). $$ 因此， $ H $ 由形式的所有排列組成 $ h_{0}\times\dots\times h_{n-1} $ 在哪裡 $ h_{i}\in H_{i} $ 每當 $ 0\leq i<n $ .
所以 $ H\simeq H_{0}\times\dots\times H_{n-1} $ 作為外部直接產品。我們也可以寫 $ H $ 作為內部直接產品 $ H_{0}^{\sharp},\dots,H_{n-1}^{\sharp} $ 在哪裡 $ H_{i}^{\sharp} $ 由所有映射組成 $ h\in H $ 如果在哪裡 $ h_{0},\dots,h_{n-1} $ 是映射在哪裡 $ h(x_{0},\dots,x_{n-1})=(h_{0}(x_{0}),\dots,h_{n-1}(x_{n-1})) $ 對所有人 $ x_{0},\dots,x_{n-1} $ ， 然後 $ h_{j} $ 是恆等函式 $ j\neq i $ . 然後 $ H_{i}^{\sharp}\simeq H_{i} $ 每當 $ 0\leq i<n. $
我們說一組 $ G $ 是超不可分解的，如果 $ A,B $ 是的子群 $ G $ 和 $ ab=ba $ 每當 $ a\in A,b\in B $ 和 $ G=AB $ ， 然後 $ |A|=1 $ 或者 $ |B|=1 $ （如果您能想到比“superindecomposible”更好的詞，請在評論中告訴我）。
定理 (Krull-Schmidt)：假設 $ G $ 是一個在正規子群上滿足升鏈條件和降鏈條件的群（任何有限群都滿足這個性質）。此外，假設 $ G $ 以兩種不同的方式寫成非平凡直接不可分解子群的內部直積，即 $ G=G_{0}\times\dots\times G_{n-1} $ 和 $ G=H_{0}\times\dots H_{n-1} $ . 那麼存在一個排列 $ \rho $ 的 $ {0,\dots,n-1} $ 這樣 $ G_{i}\simeq H_{\rho(i)} $ 為了 $ 0\leq i<n $ 和在哪裡 $$ G=G_{0}\times\dots\times G_{r}\times H_{\rho(r+1)}\times\dots H_{\rho(n-1)} $$每當 $ 0\leq r\leq n-1 $ .
引理：假設 $ G $ 是一個有限群。如果 $ G $ 是超不可分解子群的內部直積，那麼每當我們考慮 $ G $ 作為內部直接產品 $ G=G_{0}\times\dots\times G_{m-1} $ 和 $ G=H_{0}\times\dots\times H_{n-1} $ ， 然後 $ m=n $ , 並且有一些排列 $ \rho:{0,\dots,n-1}\rightarrow{0,\dots,n-1} $ 在哪裡 $ H_{i}=G_{\rho(i)} $ 為了 $ 0\leq i<n $ .
定理：存在一個高階公式 $ \phi $ 這樣如果組 $ H_{0},\dots,H_{n-1} $ 是不可分解的，那麼 $ (K,X,F)\models\phi(z) $ 當且僅當 $ z={\simeq_{0},\dots,\simeq_{n-1}} $ .
證明：觀察群 $ H $ 在結構中是高階可定義的 $ (K,X,F) $ . 此外，該組 $ H $ 有一個獨特的向上置換因式分解 $ H^{\sharp}{0}\times\dots\times H^{\sharp}{n-1} $ 成其不可分解的因素。因此，所有不可分解因子的集合 $ {H^{\sharp}{0},\dots,H^{\sharp}{n-1}} $ 可定義為 $ (K,X,F) $ . 現在，對於每個 $ i $ ， 讓 $ \hat{\simeq}{i} $ 是我們設置的等價關係 $ x\hat{\simeq}{i}y $ 當且僅當 $ h(x)=y $ 對於一些 $ h\in H^{\sharp}{i} $ . 讓 $ \simeq{i} $ 是上的等價關係 $ X $ 由產生 $ \bigcup{\hat{\simeq}{j}\mid j\neq i} $ . 然後 $ {\simeq{0},\dots,\simeq_{n-1}} $ 可定義為 $ {H^{\sharp}{0},\dots,H^{\sharp}{n-1}} $ . 因此，集 $ {\simeq_{0},\dots,\simeq_{n-1}} $ 可定義為 $ (K,X,F) $ . $ \square $
從可定義性 $ {\simeq_{0},\dots,\simeq_{n-1}} $ ，我們可以定義相當多的分組密碼輪函式不變數。
如果 $ T_{1},T_{2} $ 是組，並且 $ f_{i}:T_{i}\rightarrow T_{i} $ 為了 $ i\in{1,2} $ ，那麼我們說 $ f_{1},f_{2} $ 如果存在堆自同構，則仿射等價 $ L_{1}:T_{1}\rightarrow T_{2},L_{2}:T_{2}\rightarrow T_{1} $ 在哪裡 $ f_{2}=L_{1}f_{1}L_{2} $ . 我們說一個映射 $ M $ 在仿射等價下是不變的，如果 $ M(f)=M(g) $ 每當 $ f,g $ 是仿射等價的。
我們說一對 $ (k,\Delta) $ 是一個 S 盒化如果 $ \Delta $ 是一個堆自同構並且每當 $ x\simeq_{i}y $ ， 然後 $ \Delta\circ F_{k}(x)\simeq_{i}\Delta\circ F_{k}(y) $ . 所有 S-boxifications 的集合是高階可定義的 $ (K,X,F) $ . 觀察到存在一個 S-boxification，即映射 $ (e,\Gamma^{-1}) $ . 現在假設 $ (k,\Delta) $ 是一個 S 盒化。那麼很容易證明每個 $ \simeq_{i} $ 是關於 $ \Delta\Gamma^{-1} $ . 所以 $ \Delta=E\Gamma^{-1} $ 對於一些堆自同構 $ E $ 其中每個 $ \simeq_{i} $ 是關於 $ E $ . 所以， $ \Delta\circ F_{k}=E’\circ S $ 對於一些堆自同構 $ E’ $ . 因此，商代數 $ (X,\Delta\circ F_{k})/\simeq_{i} $ 仿射等價於 $ (V_{i},s_{i}) $ 為了 $ 0\leq i<n $ . 從這些觀察中，我們得到以下事實。
事實：如果映射 $ M $ 在仿射等價下是不變的並且可以在高階邏輯中定義，那麼映射 $ M^{+} $ 通過讓定義 $ M^{+}(F)={M(s_{0}),\dots,M(s_{n-1})} $ 在結構中是高階可定義的 $ (K,X,F) $ . 所以， $ M^{+} $ 是一個圓函式不變參數。