為什麼中間相遇攻擊需要排序

雙DES的弱點E (k1, E(k2, M))是Meet-in-the-middle攻擊是可能的。在進行中間相遇攻擊時，我們首先需要建構表，第一列所有可能的密鑰，第二列所有這些密鑰加密，然後第二步對第二列進行排序，為什麼我們需要對第二列進行排序？我們在進行排序時基於什麼？

這是針對攻擊的優化。沒有它也可以工作，但速度較慢。

要進行中間相遇攻擊，我們需要使用每個可能的密鑰加密已知的明文，並將結果文本（使用使用的密鑰）保存在列表中。現在我們用每個可能的密鑰解密一個已知的密文，看看我們是否在我們的列表中得到了結果文本。

我們想知道特定密文的密鑰。在無序列表中搜尋特定值非常困難：我們需要查看每個條目，看看它是否是我們搜尋的內容。這需要（平均） $ \frac{n}{2} $ 嘗試（與 $ n $ = 算法的密鑰空間，對於 DES 是 $ 2^{56} $ ).

如果我們在解密之前對結果列表進行排序，我們可以使用Binary Search。這將搜尋嘗試減少到大約。 $ \log_2(n) $ （n = 鍵空間）。這對於 DES 來說只有 56 個，比未排序的列表要少得多。

小記：我們用key對列進行排序，同時用密文對列進行排序。例如，第一個密鑰將是第一個密文的密鑰。

引用自：https://crypto.stackexchange.com/questions/20272