使用 Grover 算法攻擊 AES-128
當 Grover 算法用於嘗試發現秘密 AES 密鑰時，需要多少個純文字/密文對？
我正在嘗試確定是否擁有限制從純文字生成密文的速度的設備將有助於防止這種攻擊。
Grover 算法是一種具有復雜性的蠻力量子算法 $ \mathcal{O}(\sqrt{N}) $ 在非結構化數據上漸近最優。裡面還有“量子計算和隱藏變數” $ \mathcal{O}(\sqrt[3]{N}) $ 通過亞倫森。
確保解決方案的唯一性
需要ECB模式；
讓 $ n $ 表示塊大小。
讓 $ r $ 是不同的明文-密文對的數量。
讓 $ r $ 表示在兩個密鑰下同時加密的明文-密文對的數量 $ k_1 \neq k_2 $ .
那麼如果 $ r $ 明文不同；
$$ 1- \frac{1}{2^{rn}} $$
一個很好的估計 $ r $ 給出為；
$$ r > \lceil 2^k/n \rceil $$
對於 AES-128
$ n=128, k=128 \Rightarrow r=3 $
對於 AES-192
$ n=128, k=192 \Rightarrow r=4 $
對於 AES-256
$ n=128, k=256 \Rightarrow r=5 $
有關更多詳細資訊，請參閱#3.1 中的“將 Grover 算法應用於 AES：量子資源估計”
Grover 算法具有搜尋複雜性 $ \sqrt{2^{128}} $ 對於 AES 128。在純 ECB 模式下，一對明文/密文就足夠了，因為密碼映射是一種排列。
有趣的是，最近 Grover 算法和 Simon 算法的組合已被用於：
將經典的高級滑動攻擊（由 Biryukov 和 Wagner 引入）轉換為量子攻擊，從而獲得時間複雜度的指數級加速。
引用論文的作者包括對 MD5 和更早版本的 SHA 提出最佳攻擊的 Xiaoyun Wang。
具體來說，他們將量子滑動攻擊擴展到 Feistel 密碼。
編輯：
為 $ n $ 位塊密碼 $ n $ 原始滑動攻擊的位鍵 $ O(2^{n/2}) $ 複雜性並且需要盡可能多的明文/密文對。
Kaplan 等人的攻擊。上述論文中引用的要求 $ O(n) $ 複雜性，但需要根據上面引用的論文針對 Feistel 密碼進行修改。