DES-X , 計算負載和儲存
文章說攻擊 DES-X 的計算量可以減少到大約 $ 2^{(56+64)}=2^{120} $ 步驟，並且數據集的儲存應該是 $ 2^{64} $ .
但我不明白為什麼它是時間複雜度 $ 2^{120} $ 並且數據集的（空間複雜度）應該是 $ 2^{64} $ .
有人可以幫忙嗎？
實際上，由於 DESX 的工作原理，中間相遇攻擊可以優化為 $ 2^{119} $ $ DES $ （和不 $ DES^{-1} $ 操作），並且沒有額外的儲存空間。
它是這樣工作的：讓我們假設我們有三個已知的明文/密文對 $ (P_1, C_1) $ , $ (P_2, C_2) $ 和 $ (P_3, C_3) $ . 我們知道：
$$ C_1 = K_2 \oplus DES( K, K_1 \oplus P_1 ) $$ $$ C_2 = K_2 \oplus DES( K, K_1 \oplus P_2 ) $$ 在標準的中間相遇攻擊中，我們將第一個等式重寫為：
$$ C_1 \oplus K_2 = DES( K, K_1 \oplus P_1 ) $$ 並創建兩側的列表（使用可能的值 $ K, K_1, K_2 $ )，並尋找共同的價值觀；列表（實際上，我們只為左側創建一個列表，因為它更小）將佔額外的儲存空間。
但是，在 DESX 的情況下，我們可以通過將兩個等式組合為：
$$ C_1 \oplus C_2 = DES( K, K_1 \oplus P_1 ) \oplus DES( K, K_1 \oplus P_2 ) $$ 我們知道左邊的值；和 $ 2^{119} $ DES 操作，我們可以遍歷所有可能的組合 $ K, K_1 $ 使這個等式起作用（注意：為什麼 $ 2^{119} $ 並不是 $ 2^{121} $ ? 因為有兩個獨立的工件允許我們將搜尋空間分別減少兩倍：第一個是觀察值 $ K_1 $ 讓它工作，所以價值 $ K’_1 = K_1 \oplus P_1 \oplus P_2 $ ; 因此，如果我們測試一個 $ K_1 $ 值，它不起作用，我們可以跳過相應的 $ K’_1 $ 價值; 二是DES的關鍵互補性；也就是說，如果 $ K, K_1 $ 滿足上式，所以 $ \bar{K}, \bar{K_1} $ ; 因此，如果我們測試一個 $ K $ 它不起作用，我們知道 $ \bar{K} $ 也不會。所以我們用 $ 2^{55} $ $ K $ 價值觀和 $ 2^{63} $ $ K_1 $ 值，每個測試涉及 2 次 DES 操作，總共 $ 2 \times 2^{55} \times 2^{63} = 2^{119} $ DES 評估）。而且，因為我們沒有明確地創建任何列表，所以我們不使用任何額外的記憶體。
當我們找到一個 $ K, K_1 $ 使這項工作的對，我們可以計算對應的 $ K_2 $ 值，並用我們已知的第三對明文/密文對進行測試；這種額外的檢查很少見（一旦出 $ 2^{64} $ 對測試），因此在進行複雜度計算時可以忽略。
而且，這個觀察可以擴展到表明如果我們有更多的明文/密文對，對 DESX 的攻擊可以更快地執行。