差分密碼分析

差分密碼分析旨在破解基于輪的塊密碼和密碼哈希函數。 為此，她研究了明文塊的差異對加密生成的密文塊的差異的影響。

該過程的核心是分析明文對的差異對所得密文對差異的影響。

使用 XOR 運算逐位形成差異。 如果 P 和 P ?? 是兩個明文，那么它們的差就是 P ′ = P ⊕ P ? =P\oplus P^ { \分支 }} 。 通過各個加密步驟可以觀察到這種差異。 僅包含 XOR 鏈接的步驟不會更改差異。 排列和擴展，因為它們出現在大多數 Feistel 密碼中，也可以通過交換或復制排列和擴展提供的差異位來輕松計算。 只是不可能計算非線性替換框之間的差異。

為了更詳細地檢查替換框（S-box）中差異的行為，給出不同的輸入值 S X I? 和 S X I ? 具有相同的輸入差異到 S-Box X ，即 S X I ′ = c o n s t 。 然后可以看出 S X O ′ 值 S X O 和 S X O ?在輸出端分布不均。 這意味著在輸入差異恒定的情況下，一些輸出差異會更頻繁地出現，而另一些則不會出現或根本不會出現。 S-Box 的這個屬性記錄在一個差異分布表中：

值 x i , j 表示當用S-Box X 。 輸入差異 S X I j ′ 然后導致輸出差異 S X O i ′ 概率

p D = x i , j 2 l 通過檢查的 S-Box X 與輸入 l? 位寬。

對于一輪 Feistel 密碼，可以使用此知識排除某些密鑰。 其余鍵是關鍵候選者。 右圖以DES為例，使下面使用的標識有些清晰關于。

攻擊者有兩個用自選差異加密的明文。 他了解密文或至少了解它們之間的區別。 根據明文的知識，他可以計算出加密 S X E 在與輪密鑰 K 進行異或運算之前的狀態。 從密文差異，他可以計算出 S-Box X? 的初始差異 S X O ′ 。 使用差異分布表，可見S-盒可能輸入值的個數。 輸入值對 S X I 和 S X I ?? ，差值 S X I ′ ，這是輸出差異 S X O ′ 必須由攻擊者計算或從表中讀取。 假設攻擊者知道 S-box 的計算規則（Kerckhoffs 原理）。

這可以用不同的明文對重復。 正確的輪密鑰總是在運行的關鍵候選者中。 因此，不包括在所有運行的關鍵候選者中的密鑰作為輪密鑰被消除。

每個特征 Ω 可以被分配一個概率 p Ω 具有給定差異 Ω P 的隨機明文對恰好是那些這些特征假設在各個回合中存在差異。 n 輪特征 p Ω的概率是所有 1 輪特征 p i Ω 的概率的乘積n 輪特征 Ω。

p Ω = ∞ i = 1 n p i Ω

1輪特征的概率為 p D ，即該特征的輸入差異導致該特征輸出差異的概率。

一個特例是所謂的迭代特征，其中 Ω 1 = Ω 2 ，它總是可以附加到它們自身。 因此，明文差異的交換一半等于相同特征的密文差異。 因此，這些可以很容易地與任何大小的 n 輪特征相關聯。 而在非迭代特征的情況下，概率隨著 n 的增加而越來越快地下降，由于雪崩效應，構成迭代特征的部分特征的概率保持不變。 因此，在攻擊中優選使用迭代特征。