了解寬徑設計策略
我試圖了解寬徑設計策略。我已經閱讀了從 AES 的角度描述它的論文（免費預印本）。據我了解，這是一種以特定方式增加擴散以抵抗差分和線性密碼分析的技術。我的背景是資訊安全而不是密碼學，所以我對一些更重數學的描述的理解是有限的。任何人都可以解釋寬徑設計策略的基礎知識，以及它為什麼以及如何工作？
鑑於寬徑策略在現代對稱密鑰密碼學中的重要性，這個問題確實值得回答（並且得分更高）。由於沒有其他人嘗試過，我將給出一個簡短的總結和一些背景資訊。希望這將幫助您更好地理解Daemen 和 Rijmen 的論文（免費預印本）。
自從（公開）發現差分和線性密碼分析以來，對稱密鑰密碼學中的一個活躍研究領域一直致力於限制實際構造中的差分機率和線性近似的相關性。這條工作線的目標是證明（或啟發式地論證）構造對線性和差分密碼分析的安全性。實現這一目標最成功的方法是寬徑戰略。
差分和線性密碼分析
這不是解釋差分和線性密碼分析的正確位置（您可以在其他地方找到介紹），但必須在本文的其餘部分引入一些符號。回想一下，差分密碼分析研究差異的傳播 $ \Delta_0 \to \Delta_r $ . 這種差異有一個相關的機率，我將表示為 $ p(\Delta_0, \Delta_r) $ . 線性密碼分析考慮由一對遮罩描述的線性近似 $ (u_0, u_r) $ . 它們具有相關的相關性 $ c(u_0, u_r) $ ，這是偏差的兩倍。
在實踐中，人們發現的不是微分而是微分特徵，即更容易理解的密碼部分的輸入和輸出差異序列（通常是輪函式）。所以一個微分特徵可以定義為一個元組 $ (\Delta_0, \Delta_1 \ldots, \Delta_r) $ . 類似地，線上性密碼分析中有線性軌跡，這些是輸入和輸出遮罩序列 $ (u_0, u_1, \ldots, u_r) $ . 在某些情況下，微分的機率和線性近似的相關性可以估計如下：
$$ p(\Delta_0, \Delta_r) \approx \prod_{i = 1}^r p(\Delta_{i-1}, \Delta_i) $$ $$ c(u_0, u_r) \approx \prod_{i = 1}^r c(u_{i-1}, u_i), $$
其中中間差異/遮罩的選擇被理解為最佳選擇。
我必須再次強調，這些是近似值，在許多情況下這些是無效的。例如，很明顯，人們經常需要考慮多個特徵或軌跡。事實上，有一個完整的研究分支致力於在微分和線性設置中完善上述估計。我不會涉及這些問題，因為它們（大部分）超出了您的問題範圍。
在這篇文章的其餘部分，我將重點關注啟發式安全論點，這些論點基於表明所有特徵都有小機率，並且所有軌跡都具有小的相關性。我也不會真正討論“小”應該有多小（這是基於差分/線性攻擊的成本估計）。
特徵和軌蹟的界限
從這裡開始，假設我們正在處理一個 SPN（但這個論點也適用於其他幾個結構）。假設輪函式由一個非線性S盒層、一個線性層和一個鍵加法組成。
假設非線性層由 $ m $ 並行應用的 S-box。S-box 有一些最大差分機率 $ p_{max} $ 和最大絕對相關 $ c_{max} $ . 我的意思是所有非零輸入差異和非零遮罩的最大值。這很重要，因為零輸入差異總是產生零輸出差異，並且對於線性近似（假設我們正在處理排列）也是如此。
很明顯，我們有上限
$$ \prod_{i = 1}^r p(\Delta_{i-1}, \Delta_i) \le (p_{max})^{n_D} $$ $$ \left|\prod_{i = 1}^r c(u_{i-1}, u_i)\right| \le (c_{max})^{n_L}. $$
在這裡，數 $ n_D $ 等於特徵中具有非零輸入差異的 S 盒的數量。我們稱之為差分主動 S 盒。相似地， $ n_L $ 是軌跡中線性活躍的 S-box 的數量。
非線性層的作用
很多早期的工作都集中在非線性層的選擇上。也就是說，試圖最小化數量 $ p_{max} $ 和 $ c_{max} $ . 當然，仍然需要有某種約束 $ n_D $ 和 $ n_L $ ，但這不是這一行的主要關注點。例如，Nyberg 和 Knudsen 於 1995 年發表的這篇論文（paywall-free preprint）使用了類似 DES 的結構，然後討論瞭如何選擇非線性函式來最小化 $ p_{max} $ . 請注意，他們的安全論點比我在這裡描述的更強大，因為他們考慮（用更現代的術語）EDP（預期差異機率）而不是個人特徵。
因為效率往往會限制可用於構造的 S-box 的大小， $ p_{max} $ 和 $ c_{max} $ 不能做得很小。自然的結論是我們需要增加 $ n_D $ 和 $ n_L $ 不知何故。這將是線性層的作用。
線性層的作用
回想一下，S-box 層由 $ m $ 並行應用的 S-box。因此，將差異和遮罩拆分為 $ m $ 部分： $ \Delta_i = \Delta_i^{(1)} | \Delta_i^{(2)} | \cdots | \Delta_i^{(m)} $ 和 $ u_i = u_i^{(1)} | u_i^{(2)} | \cdots | u_i^{(m)} $ . 讓我們表示非零的數量 $ \Delta^{(j)} $ 在 $ \Delta = \Delta^{(1)} | \cdots | \Delta^{(m)} $ 經過 $ \mathrm{wt}(\Delta) $ 同樣對於 $ \mathrm{wt}(u) $ .
該組 $ j $ 這樣 $ \Delta^{(j)} \neq 0 $ 通常被稱為活動模式 $ \Delta $ . 一個對面具有類似的定義。
活躍 S-box 的數量 $ n_D $ 和 $ n_L $ 在特徵/軌跡中可以表示為 $$ n_D = \sum_{i = 0}^{r-1} \mathrm{wt}(\Delta_i), $$ $$ n_L = \sum_{i = 1}^r \mathrm{wt}(u_i). $$
記住一個人想要最大化 $ n_D $ 和 $ n_L $ ，所以權重 $ \mathrm{wt}(\Delta_i) $ 和 $ \mathrm{wt}(\Delta_i) $ 應該做大。這可以使用線性層來完成，因為線性層限制了哪些轉換 $ \Delta_i \to \Delta_{i + 1} $ 和 $ u_i \to u_{i + 1} $ 是可能的。也就是說，如果 S-box 層有差分 $ \Delta_i \to \Delta_i^\ast $ 以非零機率，則 $ \Delta_{i + 1} = L(\Delta_i^\ast) $ 對於線性層 $ L $ . 沒有 S-box 的滴滴涕，我們真的不知道什麼 $ \Delta_i^\ast $ 是，但我們確實知道它具有相同的活動模式，尤其是相同的權重。所以我們可以優化 $ L $ 通過最大化數量獨立於 S 盒
$$ \mathcal B_D(L) = \min_{\Delta \neq 0} [\mathrm{wt}(\Delta) + \mathrm{wt}(L(\Delta))] $$
這個數量，稱為分支號，是由 Daemen 在 他的博士論文中介紹的。之後， $ \mathcal B_D $ 與下面定義的線性分支數相比，稱為差分分支數。
類似的想法適用於線性密碼分析：線性層限制了哪些遮罩活動模式轉換是可能的。如果 $ L $ 是可逆的（為簡單起見我們假設這個），那麼 $ u_{i + 1} = L^{-\top}(u_i) $ 在哪裡 $ \top $ 表示轉置。因此，可逆的線性分支數 $ L $ 定義為 $$ \mathcal B_L(L) = \mathcal B_D(L^{-\top}) = \mathcal B_D{(L^\top)}. $$ 請注意，也可以定義不可逆映射的線性分支數。
所以我們要最大化 $ \mathcal B_D $ 和 $ \mathcal B_L $ . 在他的博士論文中，Rijmen 將分支編號與編碼理論聯繫起來。這裡就不贅述了，但是這就導致使用MDS程式碼來獲取 $ L $ . 第一個使用這些想法的密碼可能是 Rijmen 等人的SHARK。在實踐中，整個線性層 $ L $ 通常不是 MDS 矩陣。取而代之的是，將按列的 MDS 線性層與按單元排列的排列組合在一起，以確保列之間的擴散。
寬徑策略
寬徑策略是結合上述想法時得到的設計策略（儘管我做了一些簡化。）引用論文：
上述推理提出了兩種可能的機制來消除低權重軌跡：
- 選擇具有高最小差分和相關權重的 S-box。
- 設計圓形變換，使得沒有低捆綁重量的相關路徑。
第一部分是 S-box 的作用，第二部分與線性層有關（原則上也可以考慮非線性擴散層，但這超出了範圍）。寬路徑策略與早期/其他方法（例如 Nyberg 和 Knudsen）之間的一個重要區別是對線性層的強調：
寬路徑策略不是將大部分資源花費在大型 S-box 上，而是旨在設計輪轉換，使得沒有具有低捆綁權重的路徑。在由寬路徑策略設計的密碼中，線上性步驟中花費了相對大量的資源來提供高多輪擴散。
兩輪這種密碼的特徵機率的直接界限是 $ (p_{max})^{\mathcal B_D} $ 並且 2 輪軌蹟的絕對相關性上限為 $ (c_{max})^{\mathcal B_L} $ . 通常可以在 4 輪中獲得更好的邊界（這裡單元排列的影響變得相關）。我不會詳細介紹。
寬路徑策略導致了分組密碼 SHARK、Square 以及最終的 Rijndael（後來成為 AES）。在 AES 競賽之後，許多其他密碼都是基於（或至少受其啟發）寬軌方法設計的。
超越寬闊的小徑
儘管這篇文章很長，但我只描述了非常基礎的內容。
已經開發了新技術（例如基於 SAT 和 MILP 求解器）來計算活動 S-box 的數量。研究還沒有結束，但在這裡嘗試概述發展情況確實不可行。
限定特徵和路徑是不夠的，因為它只會導致啟發式安全論證。例如，可以嘗試計算分組密碼的 MEDP（最大預期差分機率）和 MELP（最大預期線性電位）。這種計算通常依賴於輪密鑰是獨立的假設。儘管對這些攻擊的安全性有很好的啟發式論證，但仍有一些設計被破壞（使用線性/差分攻擊）的例子。