如何找到 DES 弱密鑰的不動點
有人可以解釋一下嗎？我有點困惑？它來自我正在閱讀的一本教科書（分組密碼伴侶）它說：
每個弱鍵都有 $ 2^{32} $ 固定點 $ m $ 在哪裡 $ \operatorname{DES}_w(m) = m $ ( $ w $ 是 DES 弱密鑰）。換句話說，加密一個固定點給出完全相同的點。要看到這一點，請考慮 $ 2^{32} $ 經過 8 輪加密後的密文，兩個 32 位一半相等。對於弱DES密鑰，第八輪和第九輪的輪密鑰相等。因此經過七輪加密和九輪加密後的中間文本將是相等的。由於第 7 輪和第 10 輪的輪密鑰相等，因此經過 6 輪和 10 輪加密後的中間文本將相等。像這樣繼續下去，明文將等於密文。
現在不太明白：
- 為什麼會有 $ 2^{32} $ 固定點？為什麼在第八輪加密之後兩半必須相等？
- 作者所說的中間文本到底是什麼意思？他們是如何平等的？
PS：這個問題不是問弱鍵是什麼。我要求的是“固定點”而不是弱鍵。出於這個原因，我認為這不是任何其他問題的重複。有一個與我所要求的問題類似的問題，我已經檢查過，發現那裡也沒有給出令人滿意的答案。這是沒有正確答案的類似問題：
我希望按照教學順序回答。
作者所說的中間文本到底是什麼意思？
之後的中間文本 $ n $ 輪數是 64 位數量 $ L_n\mathbin|R_n $ ，根據 DES的規範對這些進行編號。 $ L_n $ 和 $ R_n $ 是一半。
為什麼第八輪加密後兩半必須相等？
我不知道兩半是否必須相等。但是我們可以證明兩半相等就足夠了，這就是引用的文本所做的。
忽略 $ \mathsf{IP} $ 和 $ \mathsf{IP}^{-1} $ , DES 加密的正規方程為 $ 1\le n<16 $ : $$ \begin{align} L_n&=R_{n-1}&&&R_n&=L_{n-1}\oplus f(R_{n-1},K_n)\ L_{16}&=L_{15}\oplus f(R_{15},K_{16})&&&R_{16}&=R_{15} \end{align} $$ 由於四個弱鍵的值 $ z $ , 寄存器中的所有位 $ C $ 是相同的。所以 $ C $ 在加密過程中旋轉時保持不變。這同樣適用於 $ D $ . 因此 $ K_1=K_2=\ldots=K_{15}=K_{16} $ . 因此對於 $ 1\le i\le16 $ 我們可以替換 $ f(R_i,K_i) $ 通過函式 $ f_z(R_i) $ 在所有回合中都相同，對於固定 $ w $ . 上述 DES 方程變為 $$ \begin{align} L_n&=R_{n-1}&&&R_n&=L_{n-1}\oplus f_z(R_{n-1})\ L_{16}&=L_{15}\oplus f_z(R_{15})&&&R_{16}&=R_{15} \end{align} $$ 如果 $ L_8=R_8 $ （即在第 8 輪之後等於一半）然後，通過將其代入方程 $ n=8 $ 和 $ n=9 $ ，我們得到 $$ \begin{align} L_8&=R_7&&&L_8&=L_7\oplus f_z(R_7)\ L_9&=L_8&&&R_9&=L_8\oplus f_z(L_8) \end{align} $$ 我們將上面的兩個方程代入下面的方程，得到 $$ \begin{align} L_9&=R_7&&&R_9&=\bigl(L_7\oplus f_z(L_8)\bigr)\oplus f_z(L_8)\ &&&&&=L_7\oplus\bigl(f_z(L_8)\oplus f_z(L_8)\bigr)\ &&&&&=L_7\oplus0^{32}\ &&&&&=L_7 \end{align} $$ 我們使用了關聯性 $ \oplus $ ， 那 $ f_z $ 是一個函式（並且在所有回合中都相同），對於所有 32 位 $ X $ 它擁有 $ X\oplus X=0^{32} $ （32 個零位的位串），它是中性的 $ \oplus $ .
結束，我們得到 $ L_7=R_9 $ 和 $ R_7=L_9 $ . 因此，引文錯誤地迴避了左右反轉中的*“七輪加密和九輪加密後的中間文本將相等” 。*
我們將這些結果代入方程 $ n=7 $ 和 $ n=10 $ ，並得到 $$ \begin{align} R_9&=R_6&&&L_9&=L_6\oplus f_z(R_6)\ L_{10}&=R_9&&&R_{10}&=L_9\oplus f_z(R_9)\ \end{align} $$ 如前所述簡化後，我們得到 $ L_6=R_{10} $ 和 $ R_6=L_{10} $ . 以此類推，直到 $ L_1=R_{15} $ 和 $ R_1=L_{15} $ . 對於下一步，我們必須注意最後一輪的方程反轉 $ L_{16} $ 和 $ R_{16} $ 與其他人相比。我們獲得 $ L_0=L_{16} $ 和 $ R_0=R_{16} $ .
64 位明文 $ P $ 是這樣的 $ \operatorname{IP}(P)=L_0\mathbin|R_0 $ 和 64 位密文塊 $ C $ 是這樣的 $ \operatorname{IP}^{-1}(L_{16}\mathbin|R_{16})=C $ . 它遵循 $ P=C $ . 呼叫那個數量 $ m $ 我們有 $ \operatorname{DES}_w(m)=m $ , QED
為什麼會有 $ 2^{32} $ 固定點？
有 $ 2^{32} $ 可能的值 $ L_8 $ ，因此對於中間文本 $ L_8\mathbin|R_8 $ 和 $ L_8=R_8 $ . 通過上述推理，每個都給出了一個值 $ m $ 和 $ \operatorname{DES}_w(m)=m $ 對於給定的弱鍵 $ w $ . 並且由此獲得的值必須是不同的：DES 加密對於給定密鑰是確定性的 $ w $ ，因此相同的輸入值在 8 輪後不能給出不同的中間文本。
因此至少有 $ 2^{32} $ 固定點 $ m $ 對於給定的弱鍵 $ w $ . 我不知道可能還有多少，對於四個中的每一個 $ w $ . 但是，我們可以看出，全零和全一的計數是相同的 $ w $ （忽略奇偶校驗位）；其他兩個弱鍵也一樣。這源於DES 的互補性。
如何找到 DES 弱密鑰的不動點
一種選擇是修改一些 DES 加密程式碼以從第 8 輪開始 $ L_8=R_8 $ . 密文將是所使用的弱密鑰的固定點。我們可以找 $ 2^{32} $ 這些對於給定的弱鍵 $ w $ , 通過使用計數器 $ L_8 $ . 當為弱鍵完成此操作時 $ w $ ，我們可以推導出固定點 $ w $ 通過使用 DES 的互補屬性。