Feistel結構為什麼是加解密互逆？

01-02

des用的是Feistel結構不過為什麼這個結構可以加密和解密結構相同就密鑰順序不同這個能證明嗎？

當然是可以證明的。以下參考書籍及個人理解，不對的地方歡迎提出討論。

上圖為古典的feistel結構，這裡的輸入是2w長度的明文分組和密鑰K，明文分組被分為等長的兩部分：L0和R0，這兩部分數據經過n輪迭代後合併成密文組。第i輪迭代的輸入Li-1和Ri-1來自於上輪迭代的輸出；而輸入的子密鑰Ki是由整個密鑰K推導出來的。關於密鑰生成演算法這裡不詳述，一般的，Ki不同於K，也互不相同。

對於第i輪加密演算法，上圖的公式表示如下（E代表是加密過程）：

LEi = REi-1 （1）

REi=LEi-1⊕F(REi-1, Ki) （2）

其中，⊕為異或，輪函數F完成代換，數據左右兩部分交換完成置換。上面的表示，配合圖片相信不難理解。

這裡需要注意的是，最後一輪迭代後，有一個附加的左右置換過程。

以DES 16輪迭代為例。密文應為RE16||LE16（「||」代表連接）。

現在開始我們的解密過程。(密文已知為RE16||LE16)

第一輪：

輸入：LD0=RE16， RD0=LE16

將公式（1）和公式（2）改造成解密的形式，同時密鑰倒序使用，即第一輪使用K16，第二輪使用K15，第i輪使用K17-i，則應為

LDi = RDi-1 （3）

RDi=LDi-1⊕F(RDi-1, K17-i) （4）

說明—LE代表Left Encryption,同理，LD代表Left Decryption。

輸出：

LD1 = RD0=LE16=RE15

RD1=LD0⊕F(RD0, K16)=RE16⊕F(RE15, K16)= LE15⊕F(RE15, K16) ⊕F(RE15, K16)= LE15

其實到這裡結論就很明顯了，但是為了更加有說服力，再演算一輪好了。

第二輪：

輸入：LD1= RE15， RD1= LE15

根據公式（3）（4），輸出：

LD2=RD1=LE15= RE14

RD2=LD1⊕F(RD1, K15)= RE15⊕F(RE14, K15)= LE14⊕F(RE14, K15) ⊕F(RE14, K15)=LE14

以下剩下的14輪迭代依次類推。可以得出的結論是：

LDi=RE16-i

RDi=LE16-i

於是第十六輪迭代的結果是 LD16||RD16 = RE0|| LE0, 哦，別忘了最後還有一次額外的左右置換過程。所以最終解密得到的明文是LE0||RE0，剛好就是原來的明文。

可證得，feistel結構只要倒序使用密鑰Ki，則加密和解密的過程相同。

不知道這樣講解是否清晰？

參考文獻：

《密碼編碼學與網路安全—原理與實踐》第三章，William Stallings。

簡化一下Feistel結構一次取一半。

然後加密 y=左⊕右處理

解密 y=左⊕右處理⊕右處理=左

所以你可以使用任何方式進行右處理

後來Feistel結構出了很多的密碼，比如blowfish密碼。