從線性方程中恢復部分密鑰

我已經搜尋了我的問題，但沒有找到任何與我的情況相關的答案。我想也許這太容易了，但我是加密領域的新手，我無法找出答案。這是練習：

攻擊者使用 128 位密鑰對密碼進行部分密鑰恢復攻擊，並設法找到一個系統 $ k $ 涉及密鑰位的獨立線性方程 $ k < n $ .

例如：

$ k_{1} \oplus k_2 \oplus k_{63} = 1 $

$ k_{1} \oplus k_3 \oplus k_{17} = 1 $

$ k_{43} \oplus k_{56} \oplus k_{60} = 0 $

這些資訊是否有助於他攻擊密碼？如果是，那麼攻擊者對窮舉搜尋的複雜性有什麼好處？

我直覺地知道，這降低了複雜性，因為常見的 $ k_1 $ 在其中 2 個等式中，我嘗試對每個等式使用真值表，但我無法從中提取答案。誰能解釋如何降低複雜性？

首先考慮一個簡單的情況，我們知道兩個密鑰位之間只有一個簡單的 x-or 關係。 $ k_i \oplus k_j = 1 $ 和 $ i \neq j $ 並稱之為 $ R1 $ . 如果我們考慮 x-or 表，我們將看到只有一半的行 $ k_i $ 和 $ k_j $ 將滿足這個方程。

$$ \begin{array}{cc|c} k_i & k_j & k_i\oplus k_j \ \hline 0 & 0 & \color{blue}{0} \ 0 & 1 & \color{red}{1} \ 1 & 0 & \color{red}{1} \ 1 & 1 & \color{blue}{0} \ \end{array} $$

一個方程等於 $ 0 $ 具有相同的結果，即 x-or 將表格分成兩半。

現在，讓我們看一下通過蠻力進行的關鍵搜尋。

  for key in possible_keys
      if ciphertext = Enc(key,m)
           return key

顯然，這將需要 $ \mathcal{O}(2^n) $ -n 位密碼的時間。

現在使用關係更新這個鍵搜尋

  for key in possible_keys
      if the key doesn't satisfy R1
          continue
      if ciphertext = Enc(key,m)
           return key

這裡有什麼收穫？對於一半的密鑰，循環不會計算Enc這意味著密鑰空間由於 R1 而減少了一位。

有人可能會說，我們仍在循環作為所有可能鍵的數量。Enc 的成本不被考慮在內 $ \mathcal{O}(2^n) $ -時間。如果添加它，您會看到，您將獲得大約兩倍的加速。可以設計一個只循環有效鍵的迭代器，但是，這是一個軟體問題。見下文還有另一種方法。

具有兩個以上密鑰位的關係將具有相同的結果。有一半的時間我們不需要計算加密。

如果我們對加速計算有多個關係，我們將使用方程式固定位。讓我們看看你的方程式來看看這個：

$ k_{1} \oplus k_2 \oplus k_{63} = 1 $

$ k_{1} \oplus k_3 \oplus k_{17} = 1 $

$ k_{43} \oplus k_{56} \oplus k_{60} = 0 $

在迭代我們時，如果我們知道 $ k_1 $ 和 $ k_2 $ 比值 $ k_{63} $ 是固定的。即使其中之一 $ k_1 $ 和 $ k_2 $ 的被翻轉 $ k_{63} $ 也被翻轉了。所以，你整體迭代，期待 $ k_{63} $ 因為它是固定的。為了受益於此，您可以在鍵上使用排列以獲得更好的迭代。

同樣，對於您的第二個和第三個方程。因此，您已經根據關係固定了三個鍵。這可以產生 3 位密鑰搜尋優勢。粗略地說，我們可以說， $ l $ 方程給出 $ l $ 位優勢。

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