CBC模式下AES的Grover算法
您好，
我想知道理論上是否可以使用 Grover 算法在 CBC 模式下破壞 AES。假設我有大約 1000 個明文/密文對，密鑰長度為 128 位。我是這樣想的：
- 對於每對明文和密文，僅使用前 16 個字節的明文和前 16 個字節的密文。（它們將被標記為 P n， C n其中 n 是第 n 對）
- 用一個未知變數 - 鍵寫下一組方程。(密鑰標記為 K)
AES-128 d (C 1 , K) ⊕ AES-128 d (C 2 , K) = P1 ⊕ P2
AES-128 d (C 3 , K) ⊕ AES-128 d (C 4 , K) = P3 ⊕ P4
AES-128 d (C 5 , K) ⊕ AES-128 d (C 6 , K) = P5 ⊕ P6
…
AES-128 d是AES-128解密函式
⊕是XOR 3. 使用 Grover 算法從上面給出的方程中找到 K。如果找到密鑰，則使用以下等式很容易確定 IV：
AES-128 d (C 1 , K) = P1 ⊕ IV
可以使用 Grover 算法從步驟 2 中反轉一組方程嗎？對於 128、192 和 256 位的密鑰長度，我需要多少個明文/密文對才能唯一確定密鑰和 IV？
Grover 的算法將適用於 CBC。你的意思是你有幾千條明文/密文消息，每條都有自己的IV？
我不確定你在步驟 2 中在做什麼。我認為通常 IV 被認為是密文的一部分，所以如果你有密文，你就有 IV，然後你會得到如下等式：
AES-128 $ _d $ （C $ _1 $ , K) = IV $ \oplus $ 磷 $ _1 $
AES-128 $ _d $ （C $ _2 $ , K) = C $ _1 \oplus $ 磷 $ _2 $
等等
對於 Grover 算法，由於您知道右手邊，並且您知道 AES 解密的輸入，您可以搜尋 K 的空間，對於預言機，使用電路執行 C 的 AES 解密 $ _1 $ ， C $ _2 $ 等，並與右側的值進行比較。
為了幾乎可以肯定返回的值 K 是正確的，對於 AES-128，您只需要 2個塊（即，只需 C $ _1 $ 和 C $ _2 $ 一條消息），2 個塊用於 AES-192，3 個塊用於 AES-256。一般來說，如果你使用 $ r $ 塊，每個都有 $ n $ 位和密鑰 $ k $ 位，格羅弗的搜尋將找到正確密鑰的機率約為 $ e^{-2^{k-rn}} $ . 因此，如果 $ k < rn $ ，您基本上可以保證得到正確的結果（有關推導，請參見本文第 4 頁的“偽密鑰”部分）。