滿足中間時間複雜度
您好，
我想知道為什麼說帶有 2 個 DES 密鑰的雙重加密消息在最壞的情況下可能會被破壞 $ 2\times2^{56} $ 在中間攻擊中使用相遇的時間。
這是我的推理：
- 明文和密文對範例：AAAAAAAAAAAAAAAA 和 35E16A5E44161DB8（要破解的密鑰：BABABABABABABABA 和 CDCDCCDCDCDCDCDCD），額外的明文和密文對要在步驟 4 中檢查，因為密鑰空間足夠大，很可能有很多密鑰對只需一個就可以成功對： 00000000000000000 & 84EC2BA1A2748F7B ; 1111111111111111 & 549A6B5696E02B5E ; 2222222222222222 & 7BB2C14B23A807C3 ; 3333333333333333 & 3BD27AAF1E0EB4F7
- 我生成包含 2^56 個條目的數組，第 n 個條目是對（第 n 個密鑰；DES 加密明文 AAAAAAAAAAAAAAAA 和第 n 個密鑰）。It will look like this (keys are in ascending order with correct parity bits):
0101010101010101 3AE716954DC04E25
0101010101010102 2B74C1D96CDE840B
0101010101010104 3367B1FBB4D2FFA7
0101010101010107 8880DA13709C9198
0101010101010108 80181B831CDC8D61
010101010101010B 0F6CD43C15297456
….. 3. 現在我必須按第 2 列中的密文對數組進行排序 4. 現在我嘗試使用連續密鑰解密密文 35E16A5E44161DB8 並通過二進制搜尋在第 2 列中搜尋此值：
嘗試 #1：密鑰 0101010101010101 在排序數組中給出 477B6FD8296E1956 搜尋密鑰，如果找到密鑰，請檢查其他明文和密文對，應失敗
嘗試#2：密鑰 0101010101010102 在排序數組中給出 107272EB5D1BFF28 搜尋密鑰，如果找到密鑰，請檢查其他明文和密文對，應該失敗
嘗試＃3：密鑰 0101010101010104 給出 23153894F3FF825E 在排序數組中搜尋密鑰，如果找到密鑰，請檢查其他明文和密文對，應該失敗
嘗試＃4：密鑰0101010101010107在排序數組中給出D0D497791C20B166搜尋密鑰，如果找到密鑰檢查其他明文和密文對，應該失敗
嘗試 #5：密鑰 0101010101010108 在排序數組中給出 8A830E5E7927C541 搜尋密鑰，如果找到密鑰，請檢查其他明文和密文對，應該失敗
嘗試 #6：密鑰 010101010101010B 在排序數組中給出 BA7A15AA12A62C02 搜尋密鑰，如果找到密鑰，請檢查其他明文和密文對，應該失敗
…..
嘗試#57873028282430310：密鑰 CDCDCDCDCDCDCCDD 在排序數組中給出 AC972FC04E884797 搜尋密鑰，如果找到密鑰檢查其他明文和密文對，應該成功
對我來說，似乎需要第 3 步才能執行第 4 步
如果我是對的，那麼時間複雜度就在附近 $ 2^{56}\times\log(2^{56}) = 56\times2^{56} $ 使用最優排序算法。我的推理中缺少什麼？
我的推理中缺少什麼？
兩件事情：
- 除了排序之外，還有其他策略來查找衝突；一個明顯的方法是建立一個巨大的雜湊表。現在，在實踐中，排序可能會更快（因為一個巨大的雜湊表是不切實際的），但理論上，一個雜湊表將允許 $ O(1) $ 此復雜性分析隱含假設的訪問。
- $ O(n \log n) $ 實際上並不是最佳的排序時間。如果您可以對數據執行的唯一操作是比較和數據移動；但是我們實際上並沒有受到這種限制。一種明顯的方法是使用基數排序方法，它可以具有更好的時間複雜度。
現在，老實說，我們通常會忽略這些非密碼操作（例如搜尋和排序）所花費的時間，除非它們佔用了總時間的很大一部分。坦率地說，當你下降到那個級別時，可能會有很多細節（比如處理的複雜性） $ O(2^{56}) $ 數據），而我們只計算 DES 評估。
我們實際上並沒有試圖破壞 2DES；相反，我們展示了打破 2DES 實際上可以在實際時間內實現。如果我們真的試圖打破它，我們最終可能會改用 lambda 搜尋，它會不斷增加複雜性並且不能保證，會更容易實現（因為 lambda 搜尋會使用更少的記憶體，並且仍然很容易並行化）。