在對具有兩個唯一密鑰的雙 DES 進行中間攻擊時，可能發生多少次沖突（相同對）？
我正在閱讀我的教授幻燈片，我了解中間的相遇是如何工作的，但我有一些困惑。所以我們需要兩個 $ {(P_1, C_1), (P_2, C_2)} $ . 讓 $ \lg{(k_1)} = \lg{(k_2)} = 56 $ ，我們生成 $ 2^{56} $ 的 $ X = {x_i = E_{k_{1,i}}(P_1)} $ 和 $ 2^{56} $ 的 $ Y = {y_i = D_{k_{2,i}}(C_1)} $ . 到目前為止，我們花了 $ 2^{56}+ 2^{56}= 2^{57} $ 計算步驟 $ X, Y $ .
我的理解是，這就是為什麼我們說雙 DES 只會增加一點安全性？
現在我們的工作是找到所有 $ x_i,y_j $ 這樣 $ x_i = y_j $ . 我想我們可以使用 $ 2^{56} $ 二進制搜尋，所以我們可以在 $ 2^{56}\lg{2^{56}}= 2^{56} \times 56 $ 腳步？
現在的總步驟是：
$$ \begin{align*} 2^{57}+(2^{56} \times 56) &= 2^{57}+(2^{56} \times (2^5+24)) \ &= 2^{57}+(2^{56+5} + (2^{56}\times24)) \ &= 2^{57}+2^{61} + (2^{56}\times24) \ &= 2^{61}+2^{57} + (2^{56}\times24) \ \end{align*} $$
現在我們擔心我們必須在第二個明文密文對上檢查多少個候選對 $ (P_2, C_2) $ . 這取決於我們在上一步中看到的碰撞次數。平均而言，機率是 $ x_i = y_j $ 是 $ 1/2^{56} $ 正確的？這是混淆之一，我正在閱讀的幻燈片說它是 $ 1/2^{64} $ . 由於我不明白為什麼，現在我將繼續 $ 1/2^{56} $ . 因此，平均碰撞次數必須是，
$$ \frac{2^{112}}{2^{56}} = 2^{56} $$
所以現在我們必須檢查 $ 2^{56} $ 候選對 $ (P_2, C_2) $ 意味著現在的平均步數是：
$$ 2^{61}+2^{57} + (2^{56}\times24) + 2^{56} $$
但是幻燈片是這樣分析的，他們說有 $ 2^{64} $ 許多 $ x_i $ 因此候選檢查是 $ 2^{112-64} = 2^{48} $ . 接下來是這張幻燈片，我完全迷失了：
有人可以提供一些澄清嗎？
**編輯：**我想我看到了我的疏忽， $ |X| = |Y| = 2^{56} $ 是窮舉的子集 $ |X’| = |Y’| = 2^{64} $ 設置因為 $ \lg{(x_i)} = \lg{(y_i)} = 64 $ . 因此 $ X, Y $ 使用加密解密進行採樣。因此，當我們計算碰撞機率時，我們使用 $ X’, Y’ $ 屈服 $ 1/2^{64} $ .
這是正確的嗎？
現在我們的工作是找到所有 $ x_i,y_j $ 這樣 $ x_i = y_j $ . 我想我們可以使用 $ 2^{56} $ 二進制搜尋，所以我們可以在 $ 2^{56}\lg{2^{56}}= 2^{56} \times 56 $ 腳步？
實際上，您更有可能使用基於散列的方法（在 O(n log n) 時無法擴展）或基於磁碟的排序方法（技術上為 O(n log n)，但是比重複二分搜尋更好的比例常數）；二進制搜尋方法會遇到很多記憶體未命中（假設您有那麼多記憶體）。另一方面，篩選這麼多數據有點不重要，我們在進行高級分析時通常會忽略這一點；我們通過假設除了 DES 評估本身之外的所有計算都是“免費的”來簡化問題。
而且，進行重複項搜尋所涉及的“步驟”與執行 DES 操作有很大不同（並且可能要快得多）；這使得對它們進行有意義的總結變得困難。
但是，要得到你真正的問題：
平均而言，機率是 $ x_i = y_j $ 是 $ 1/2^{56} $ 正確的？
沒有; 它是 $ 2^{-64} $ ; 那是因為兩者 $ x_i, y_j $ 是 64 位，可以假設（使用不正確的密鑰）完全隨機。
所以現在我們必須檢查 $ 2^{56} $ 候選對
沒有; 大約有 $ 2^{112} / 2^{64} = 2^{48} $ 預期的
這應該可以解釋幻燈片的來源。