破解雙重加密

讓 $ E_k $ : {0,1} $ ^l $ 是具有塊大小的塊密碼加密函式 $ l $ 和密鑰長度 $ n $ .

在課堂上，我們看到了具有兩個獨立密鑰的雙重加密 $ E{}’{k_1k_2}(x) $ = $ E{k_1}(E_{k_2}(x)) $ ,

可以暴力破解 $ O(2^n) $ 時間和 $ O((l + n)2^n) $ 使用中間相遇攻擊的空間：

創建一個表 $ 2^n $ 條目映射鍵的長度 $ l $ 通過加密已知的純文字到長度為 n 的條目 $ x $ 使用所有可能的鍵 $ k_2 $ ，然後通過解密對應的密文來查表 $ c $ 使用所有可能的鍵 $ k_1 $ .

假設你只有 $ O((l + m)2^m) $ 空間（其中 $ m < n $ ), 給出一個及時破解雙重加密的算法 $ O(2^{2n-m}) $ .

我被困了好幾天，無法弄清楚允許這種有效算法的技巧。

有任何想法嗎？尖端？提示？

這當然是功課。

添加：

是否足以證明如果我們選擇更小的 $ n $ 加密會以不可忽略的機率被破壞嗎？或者我必須展示一個總是阻止加密的算法？

提示：假設有人告訴你 $ n-m $ 位 $ k_2 $ ; 那麼中間相遇攻擊需要多少時間/空間？

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