了解 DES 的線性逼近
我將介紹 DES 的線性逼近（Matsui 的論文 1993 Linear Cryptanalysis Method for DES Cipher），但我不明白其中的某些部分。
這是我的問題：
- 線上性近似中 $ S $ 我們有引理 1 的盒子，上面寫著 $ NS(a,b) $ 甚至
我看到了關於引理 1 的話題，但我也不明白解釋:( 2. 在與引理 1 相同的頁面上，我們有表 1。我理解表和偏差等的概念，但在表中，如果我們在每一行中添加值，我們得到 0。我不明白它的原因。
（我有一個想法：例如，當我們為 α=16 添加所有行時，我們有$$ \mathtt{X4=8Y3\oplus8Y2\oplus8Y1\oplus8Y0} $$ 由於我們將右側的每個位乘以 8，我們在右側有 0，所以 x4 為 0 的機率是 1/2，因此我們有 0 偏差）
- 為了打破 16 輪 DES，我們使用算法 2，但我不明白我們如何獲得 14 個密鑰位？
- 我們說 DES 的唯一非線性部分是 S 個盒子。通過說線性或非線性，我們的意思是像數學函式中的線性？
- 在算法 2 中，我們為每個關鍵候選應用算法。我理解算法，但我不明白我們如何找到這些候選鍵。如果我們嘗試所有可能的候選鍵，那麼這將使過程變得很長。
這種非線性給我們帶來了哪些優勢或劣勢？
- 定義：$$ NS_a(\alpha,\beta) = # {x| 0 \leq x < 64, (\oplus_{s=0}^{5}(x[s] \bullet \alpha[s])) = (\oplus_{t=0}^{3}(S_{a}(x)[t] \bullet \beta[t]))} $$
這裡， $ x $ 是您對 S-box 的輸入，並且 $ S_a(x) $ 是對應的 S-box 的輸出。 $ \alpha $ 和 $ \beta $ 是面具。然後， $ NS_a(\alpha,\beta) $ 是被屏蔽的輸入位 exor 的重合數 $ \alpha $ 和 exor 掩蔽的輸出位 $ \beta $ . 看看下面的例子，其中 $ \alpha = 16 $ 和 $ \beta = 15 $ ，即， $ \alpha = 010000 $ 和 $ \beta = 1111 $ , 輸入為 $ x=011100 $ 我們考慮第五個 S-box：$$ 011100 \xrightarrow{\text{5’th S-box}} 1110 $$ $$ \oplus_{s=0}^{5}(x[s] \bullet \alpha[s]) = x[4] \bullet \alpha[4] = 1 $$ 自從 $ \bullet $ 是按位“與”運算， $ x \bullet 0 = 0 $ 和 $ 0 \oplus x = x $ . $$ \oplus_{t=0}^{3}(S_{a}(x)[t] \bullet \beta[t]) = (S_{a}(x)[1] \bullet \beta[1])\oplus(S_{a}(x)[2] \bullet \beta[2])\oplus(S_{a}(x)[3] \bullet \beta[3]) = 1 $$ 然後，我們遞增 $ NS_a(16,15) $ 1。如果你對所有可能的輸入重複這個（即 $ 0 \leq x < 64 $ ), $ NS_a(16,15) $ 結果確實是12。
所以，我們保持 $ \alpha $ 在我們遍歷每 64 個可能的輸入時保持不變。由於每個輸入位將是 32 次“1”和 32 次“0”，因此這個想法總結了這樣一個事實，即等式左側總是有 32 個 1 和 32 個 0。另一種說服的方法，只是按格雷碼順序對輸入進行排序，並省略每個非屏蔽位，並且由於格雷碼一次切換 1 位，我們的 exor 會隨著每個輸入而改變，因此我們將有 32-32 分佈在等式的左邊。對於等式的右側，同樣成立，我們將有 32 個 0 和 32 個 1。在這裡，將 S-box 視為將左側的 32 個零和 32 個 1 分配給右側的 32 個零和 32 個 1 的框，並進一步假設所有零都分配給 1，所有 1 都分配給零。然後，我們稍微改變我們的 Sbox，將一個零分配給另一個零，這基本上是交換 Sbox 的 2 個輸出，以對齊兩個零；這意味著兩個也被分配給彼此。雖然這樣解釋有點麻煩，但當我研究松井的攻擊時，我就這樣說服了自己。
換句話說，我們有 32 個奇數個 1 的輸入和 32 個偶數個 1 的二進製表示。, 那麼等式左邊有 32 個零和 32 個 1。因為對於每個 S-box，有
- 我想我有一種直覺的方式可以看到這一點，但我應該看看我的筆記，我會盡快編輯這個部分。
- 實際上，我們得到了 7 個密鑰位，然後逆向處理，即開始以相反的順序解密密文，重新排序輪密鑰並使用相同的結構獲得更多的 7 個位。在這裡，當我們將整個方案反轉時，我們得到另一個最佳表達式對於某些特定的表達式，在明文和密文上使用不同的遮罩，-據我所知，並非全部-，我們可以通過在給定的 DES 線性近似中將明文更改為密文和將密文更改為明文來表達它們的特徵。那麼，如何獲得 7 個密鑰位呢？從算法 1 或鬆井為 n 輪 DES 給出的任何 n 輪表達式，我們可以直接獲得 1 位資訊。如果我們在 n 輪 DES 中引入 (n-1) 輪最佳表達式，正如您可能注意到的，我們將得到一個明文、密文和 $ F(X,K) $ . 使用這個詞 $ F(X,K) $ ，-注意每個輪密鑰是48位，即6個密鑰位影響一個S盒-，我們可以恢復這6個密鑰位。算法 2 是搜尋這 6 個關鍵位的算法。當您使用算法 1 和 2 恢復 7 位時，只需顛倒順序，從密文開始，開始解密，然後再次應用分析算法恢復另外的 7 位。
- 我不是數學家，所以我寧願不談論數學函式意義上的“線性/非線性”，但請記住，S-box 的線性增加了混亂，從而增強了它的安全性，而 P-盒子增加了擴散，這使得密鑰位和明文位盡可能快地相互融合。
注意：我不是經驗豐富的密碼學家，但我現在正在閱讀和研究這些基本攻擊，如果我弄錯了，我很抱歉。