Des
有效攻擊 2DES
在 2DES 使用中相遇 $ 2^{56} $ 記憶。鑑於攻擊者只有 $ 2^{45} $ 記憶。攻擊者如何調整攻擊，即使有這個記憶體限制，它仍然比查看所有現有密鑰更有效？
我想你可以把它分成幾個查找——幾個表——每次都包含一個不同的子集，同時確保每一行都得到比較。這仍然應該比 $ O(n^2) $ . 這是答案嗎？
攻擊者分割範圍 $ 2^{56} $ 第一個 DES 的密鑰 $ 2^{17} $ 尺寸範圍 $ 2^{39} $ . 然後他會跑 $ 2^{17} $ 以下中間相遇攻擊的次數，每個範圍一次：
- 對於範圍內的所有密鑰，攻擊者計算已知明文上的第一個 DES，產生 $ 2^{39} $ 64 位字，總大小為 $ 2^{45} $ 位。
- 攻擊者按升序對它們進行排序。
- 對全部 $ 2^{56} $ 對於第二個 DES 的可能密鑰，攻擊者解密已知密文，並在排序列表中查找該塊。
最壞的情況是攻擊者需要為所有人這樣做 $ 2^{17} $ 範圍，對於大約 DES 加密的總數 $ 2^{56+17} = 2^{73} $ , 這仍然比 $ 2^{112} $ . 攻擊者在任何時候都不需要記住超過 $ 2^{45} $ 位。排序步驟可以忽略不計（ $ 2^{17}·39·2^{39} \approx 2^{50} $ 比較和交換），並且可以使用間接索引（ $ 2^{39} $ 單詞會或多或少有規律地傳播，所以我們可以做得比簡單的二分法更好）。