費斯妥密碼

在密碼學中，費斯妥密碼（英語：Feistel cipher）是用於構造區塊加密法的對稱結構，以德國出生的物理學家和密碼學家霍斯特·費斯妥（Horst Feistel）命名，他在美國IBM工作期間完成了此項開拓性研究。通常也稱為費斯妥網絡（Feistel network）。大部分分組密碼使用該方案，包括數據加密標準（DES）。費斯妥結構的優點在於加密和解密操作非常相似，在某些情況下甚至是相同的，只需要逆轉金鑰編排。因此，實現這種密碼所需的代碼或電路大小能幾乎減半。

費斯妥網絡是一種迭代密碼，其中的內部函數稱為輪函數。^[1]

歷史

Feistel網絡最初在IBM的Lucifer密碼中商業化，這種密碼由霍斯特·費斯妥和Don Coppersmith於1973年設計。美國聯邦政府在設計DES（基於Lucifer密碼，由NSA進行修改）時採用了Feistel網絡。像DES的其他組件一樣，Feistel構造中的迭代特性使得在硬件中（特別是在設計DES時已有的硬件上）實現密碼系統更容易。

理論工作

許多現代及一些較舊的對稱區塊加密法基於Feistel網絡（例如GOST 28147-89區塊加密法），且密碼學家已經深入研究了Feistel密碼的結構和性質。具體而言，Michael Luby和Charles Rackoff分析了Feistel密碼的構造，證明了如果輪函數是一個密碼安全的偽隨機函數，使用K_i作為種子，那麼3輪足以使這種區塊加密法成為偽隨機置換，而4輪可使它成為「強」偽隨機置換（這意味着，對可以得到其逆排列諭示的攻擊者，它仍然是偽隨機的）^[2]。

由於Luby和Rackoff的結果非常重要，Feistel密碼有時也稱為Luby-Rackoff區塊加密法。進一步的理論工作對其進行了推廣，給出了更加精確的安全界限^[3]^[4]。

構造細節

令 ${\rm {F}}$ 為輪函數，並令 $K_{0},K_{1},\ldots ,K_{n}$ 分別為輪 $0,1,\ldots ,n$ 的子金鑰。

基本操作如下：

將明文塊拆分為兩個等長的塊，( $L_{0}$ , $R_{0}$ )

對每輪 $i=0,1,\dots ,n$ ，計算

L_{i+1}=R_{i}\,

R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i}).

則密文為 $(R_{n+1},L_{n+1})$ 。

解密密文 $(R_{n+1},L_{n+1})$ 則通過計算 $i=n,n-1,\ldots ,0$

R_{i}=L_{i+1}\,

L_{i}=R_{i+1}\oplus \operatorname {F} (L_{i+1},K_{i}).

則 $(L_{0},R_{0})$ 就是明文。

與代換-置換網絡相比，Feistel模型的一個優點是輪函數 $\operatorname {F}$ 不必是可逆的。

右圖顯示了加密和解密的過程。注意解密時子金鑰順序反轉，這是加密和解密之間的唯一區別。

非平衡Feistel密碼

非平衡Feistel密碼相比其有所修改，其中 $L_{0}$ 和 $R_{0}$ 的長度不等^[5]。Skipjack密碼就是這種密碼的一個例子。德州儀器數碼簽章轉發器使用專有的非平衡Feistel密碼來執行挑戰-響應認證^[6]。

Thorp shuffle是一種非平衡Feistel密碼的極端情況，其中一邊只有一位。這比平衡Feistel密碼具有更好的可證明安全性，但需要更多輪^[7]。

其他用途

除了區塊加密法外，Feistel結構也用於其他密碼演算法。例如，最佳非對稱加密填充（OAEP）在某些非對稱金鑰加密方案中，使用簡單的Feistel網絡對密文進行隨機化。

一個廣義的Feistel演算法可以用來在大小不是2的冪的小域上建立強排列（參見保留格式加密）。^[7]

Feistel網絡作為設計組件

無論整個密碼是否是Feistel密碼，類Feistel網絡都可以在設計密碼時用作其中一個組成部分。例如，MISTY1是一個使用三輪Feistel網絡的Feistel密碼函數，Skipjack是一個修改的Feistel密碼，在它的G置換中使用Feistel網絡，Threefish（Skein）是一個非Feistel的區塊加密法，其一部分使用了類Feistel的MIX函數。

Feistel密碼列表

Feistel或修改過的Feistel密碼：

廣義Feistel：

參見

密碼學
串流加密法
代換-置換網絡
提升方案，用於離散小波變換，具有幾乎相同的結構
保留格式加密
萊-馬西方案

參考

^ Menezes, Alfred J.; Oorschot, Paul C. van; Vanstone, Scott A. Handbook of Applied Cryptography Fifth. 2001: 251. ISBN 0849385237.
^ Luby, Michael; Rackoff, Charles, How to Construct Pseudorandom Permutations from Pseudorandom Functions, SIAM Journal on Computing, April 1988, 17 (2): 373–386 [2017-11-21], ISSN 0097-5397, doi:10.1137/0217022, （原始內容存檔於2019-02-12）
^ Patarin, Jacques, Boneh, Dan , 編, Luby–Rackoff: 7 Rounds Are Enough for 2^n(1−ε) Security (PDF), Advances in Cryptology—CRYPTO 2003, Lecture Notes in Computer Science, October 2003, 2729: 513–529 [2009-07-27], doi:10.1007/b11817, （原始內容存檔 (PDF)於2017-02-01）
^ Zheng, Yuliang; Matsumoto, Tsutomu; Imai, Hideki. On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses. Advances in Cryptology — CRYPTO』 89 Proceedings (Springer, New York, NY). 1989-08-20: 461–480 [2017-11-21]. doi:10.1007/0-387-34805-0_42. （原始內容存檔於2018-06-09）（英語）.
^ Schneier, Bruce; Kelsey, John. Unbalanced Feistel networks and block cipher design. Fast Software Encryption (Springer, Berlin, Heidelberg). 1996-02-21: 121–144 [2017-11-21]. doi:10.1007/3-540-60865-6_49. （原始內容存檔於2017-09-22）（英語）.
^ Bono, Stephen; Green, Matthew; Stubblefield, Adam; Juels, Ari; Rubin, Aviel; Szydlo, Michael. Security Analysis of a Cryptographically-Enabled RFID Device (PDF). Proceedings of the USENIX Security Symposium. 2005-08-05 [2017-11-21].
^ ^7.0 ^7.1 Morris, Ben; Rogaway, Phillip; Stegers, Till. How to Encipher Messages on a Small Domain (PDF). Advances in Cryptology - CRYPTO 2009 (Springer, Berlin, Heidelberg). 2009: 286–302 [2017-11-21]. doi:10.1007/978-3-642-03356-8_17. （原始內容存檔 (PDF)於2020-10-23）（英語）.

[1] Menezes, Alfred J.; Oorschot, Paul C. van; Vanstone, Scott A. Handbook of Applied Cryptography Fifth. 2001: 251. ISBN 0849385237.

[pseudorandom-2] Luby, Michael; Rackoff, Charles, How to Construct Pseudorandom Permutations from Pseudorandom Functions, SIAM Journal on Computing, April 1988, 17 (2): 373–386 [2017-11-21], ISSN 0097-5397, doi:10.1137/0217022, （原始內容存檔於2019-02-12）

[7-rounds-3] Patarin, Jacques, Boneh, Dan , 編, Luby–Rackoff: 7 Rounds Are Enough for 2^n(1−ε) Security (PDF), Advances in Cryptology—CRYPTO 2003, Lecture Notes in Computer Science, October 2003, 2729: 513–529 [2009-07-27], doi:10.1007/b11817, （原始內容存檔 (PDF)於2017-02-01）

[4] Zheng, Yuliang; Matsumoto, Tsutomu; Imai, Hideki. On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses. Advances in Cryptology — CRYPTO』 89 Proceedings (Springer, New York, NY). 1989-08-20: 461–480 [2017-11-21]. doi:10.1007/0-387-34805-0_42. （原始內容存檔於2018-06-09）（英語）.

[5] Schneier, Bruce; Kelsey, John. Unbalanced Feistel networks and block cipher design. Fast Software Encryption (Springer, Berlin, Heidelberg). 1996-02-21: 121–144 [2017-11-21]. doi:10.1007/3-540-60865-6_49. （原始內容存檔於2017-09-22）（英語）.

[crypto-rfid-6] Bono, Stephen; Green, Matthew; Stubblefield, Adam; Juels, Ari; Rubin, Aviel; Szydlo, Michael. Security Analysis of a Cryptographically-Enabled RFID Device (PDF). Proceedings of the USENIX Security Symposium. 2005-08-05 [2017-11-21].

[thorp-7] 7.0 ^7.1 Morris, Ben; Rogaway, Phillip; Stegers, Till. How to Encipher Messages on a Small Domain (PDF). Advances in Cryptology - CRYPTO 2009 (Springer, Berlin, Heidelberg). 2009: 286–302 [2017-11-21]. doi:10.1007/978-3-642-03356-8_17. （原始內容存檔 (PDF)於2020-10-23）（英語）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]