我如何證明 Feistel 輪次是 DES 的逆循環？
我很難證明每一輪 DES 算法都是它自己的逆算法。有人可以給它一個簡明的解釋嗎？
如果一個函式，說 $ f $ , 是它自己的逆比 $ f(f(x))= x $ 正確的？我試圖證明，給定一個圓形函式 $ Rd $ ， 那： $ Rd(Rd(L_1|R_1))= L_1|R_1 $ . 這裡 $ L_1 $ 和 $ R_1 $ 是輸入的左右部分。
然後我得到： $$ Rd(R_1|L_1 \oplus F(R_1,K_1))=L_1 \oplus F(R_1,K_1)|R_1 \oplus F(L_1+F(R_1,K_1), K_2) $$ …這必須等於 $ L_1|R_1 $ .
但我看不出這將如何等於 $ L_1|R_1 $ ? 我在哪裡犯錯？
有一種簡單的方法可以*“每一輪 DES 算法都是它自己的逆”。考慮圓 $ n $ DES 涉及（幾乎只）一個函式 $ g_n $ 和 $$ g_n(L\mathbin|R)=\bigl(L\oplus f(R,K_n)\bigr)\mathbin|R $$ 在哪裡 $ K_n $ 是輪的 48 位子密鑰 $ n $ ， 功能 $ f $ 是“密碼函式”*（在DES 的定義中給出），並且 $ L $ 和 $ R $ 是形成 64 位塊的 32 位比特環。
那個功能 $ g_n(L\mathbin|R) $ 驗證 $ g_n(g_n(L\mathbin|R))=L\mathbin|R $ ，正如問題中所想的那樣；或者換句話說 $ g_n $ 是對合；或者換句話說 $ g_n\circ g_n $ 是恆等函式。證明： $$ \begin{align} g_n(g_n(L\mathbin|R))&=g_n\Bigl(\bigl(L\oplus f(R,K_n)\bigr)\mathbin|R\Bigr)\ &=\Bigl(\bigl(L\oplus f(R,K_n)\bigr)\oplus f(R,K_n)\Bigr)\mathbin|R\ &=\Bigl(L\oplus\bigl(f(R,K_n)\oplus f(R,K_n)\bigr)\Bigr)\mathbin|R\ &=\left(L\oplus0^{32}\right)\mathbin|R\ &=L\mathbin|R \end{align} $$ 該證明呼叫了 $ g_n $ （兩次），關聯性 $ \oplus $ ， 那 $ f $ 是一個函式，它適用於所有 32 位 $ X $ 它擁有 $ X\oplus X=0^{32} $ （32 個零位的位串），它是中性的 $ \oplus $ .
DES 加密在 64 位數量上鍊接這 33 個操作： $$ \mathsf{IP},,,g_1,,,\mathsf S,,,g_2,,,\mathsf S,,,\ldots,,,\mathsf S,,,g_{15},,,\mathsf S,,,g_{16},,,\mathsf{IP}^{-1} $$ 在哪裡 $ \mathsf S $ 是由定義的“交換”對合 $ \mathsf S(L\mathbin|R)=R\mathbin|L $ ， 功能 $ \mathsf{IP} $ 是位的一些排列，並且 $ \mathsf{IP}^{-1} $ 是逆排列。
DES 解密在 64 位數量上鍊接這 33 個操作： $$ \mathsf{IP},,,g_{16},,,\mathsf S,,,g_{15},,,\mathsf S,,,\ldots,,,\mathsf S,,,g_2,,,\mathsf S,,,g_1,,,\mathsf{IP}^{-1} $$
我們看到DES加密然後解密是恆等函式： $ (34-j)^\text{th} $ 解密操作取消 $ j^\text{th} $ 加密操作：
- 為了 $ j=33 $ ， 因為 $ \mathsf{IP} $ 取消 $ \mathsf{IP}^{-1} $ .
- 為了 $ j=1 $ ， 因為 $ \mathsf{IP}^{-1} $ 取消 $ \mathsf{IP} $ .
- 對於其他甚至 $ j $ ， 因為 $ g_{j/2} $ 是對合。
- 對於其他（奇數） $ j $ ， 因為 $ \mathsf S $ 是對合。
重要的是，加密和解密使用完全相同的結構，只有索引（即子密鑰的順序） $ K_n $ ) 不同。這允許使用相同的硬體或程式碼進行加密和解密。
一輪 Feistel 密碼的通常定義包括交換 $ \mathsf S $ : $$ \begin{align} g’_n(L\mathbin|R)&=\mathsf S\bigl(g_n(L\mathbin|R)\bigr)\ &=R\mathbin|\bigl(L\oplus f(R,K_n)\bigr) \end{align} $$ 根據問題的意義，這個函式不是它自己的反函式。
使用該符號，DES 加密和解密是 18 次操作 $$ \mathsf{IP},,,g’1,,,g’2,,,\ldots,,,g’{15},,,g{16},,,\mathsf{IP}^{-1}\ \mathsf{IP},,,g’{16},,,g’{15},,,\ldots,,,g’_2,,,g_1,,,\mathsf{IP}^{-1} $$ 在該展示文稿中，解密撤消加密的情況不太明顯。但這仍然成立，如果我們擴展 $ g’_n $ 進入 $ g_n $ 其次是 $ \mathsf S $ .
當說DES有16輪時，它被忽略了 $ \mathsf{IP} $ 和 $ \mathsf{IP}^{-1} $ . 而且，對於嚴格的Vulcan，只有第 16輪（沒有交換的那輪）是它自己的逆。
DES 規範和許多關於 Feistel 密碼的教科書都給出了索引 $ L $ 和 $ R $ 回合前後 $ n $ 加密，與 $ L_0\mathbin|R_0 $ 之後的明文 $ \mathsf{IP} $ . 上式為 $ g’n $ 那麼可以寫成： $$ \begin{align} L_n&\gets R{n-1}\ R_n&\gets L_{n-1}\oplus f(R_{n-1},K_n) \end{align} $$
DES（作為 $ m=16 $ 輪）和一些教科書考慮密文（之前 $ \mathsf{IP}^{-1} $ ） 成為 $ L_m\mathbin|R_m $ ，並專門化最後一輪加密的方程： $$ \begin{align} L_m&\gets L_{m-1}\oplus f(R_{m-1},K_m)\ R_m&\gets R_{m-1} \end{align} $$
周圍還有其他約定：一些文本在所有回合中都使用相同的方程式。然後一些添加最終交換，或者認為密文是 $ R_m\mathbin|L_m $ ; 其他人認為 $ L_m\mathbin|R_m $ 作為密文（後一種不會獲得與 DES 相同的密文）。
對於解密，DES 使用相同的輪方程進行加密和解密，除了子密鑰的編號，即 $ 1\le n<m $ : $$ \begin{align} L_n&\gets R_{n-1}&&&L_m&\gets L_{m-1}\oplus f(R_{m-1},K_1)\ R_n&\gets L_{n-1}\oplus f(R_{n-1},K_{16-n})&&&R_m&\gets R_{m-1} \end{align} $$ 與解密的 $ L_0\mathbin|R_0 $ 定義為加密的 $ L_n\mathbin|R_n $ ，由此得出對於 $ 1\le n<m $ , 解密的 $ L_n\mathbin|R_n $ 是加密的 $ R_{m-n}\mathbin|L_{m-n} $ （注意反轉）和解密的 $ L_m\mathbin|R_m $ 是加密的 $ L_0\mathbin|R_0 $ .
其他文本在解密和加密中對相等的變數使用相同的命名，並為解密定義了不同的圓形方程。對於正常圓形結構，它給出： $$ \begin{align} R_{n-1}&\gets L_n\ L_{n-1}&\gets R_n\oplus f(L_n,K_n) \end{align} $$
每條評論的腳註：Feistel 密碼的幾輪之間總是存在某種形式的交換，因此在一輪中沒有改變的狀態部分在下一輪改變。這對於安全性至關重要（而不是解密工作）。只有當我們將交換排除在其定義中時，一輪才是它自己的逆。