密碼學中,費斯妥密碼(英語: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 LubyCharles Rackoff分析了Feistel密碼的構造,證明了如果輪函數是一個密碼安全的偽隨機函數,使用Ki作為種子,那麼3輪足以使這種分組密碼成為偽隨機置換,而4輪可使它成為「強」偽隨機置換(這意味着,對可以得到其逆排列諭示的攻擊者,它仍然是偽隨機的)[2]

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

構造細節

編輯
 

 為輪函數,並令 分別為輪 的子密鑰。

基本操作如下:

將明文塊拆分為兩個等長的塊,( ,  )

對每輪 ,計算

 
 

則密文為 

解密密文 則通過計算 

 
 

 就是明文。

代換-置換網絡相比,Feistel模型的一個優點是輪函數 不必是可逆的。

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

非平衡Feistel密碼

編輯

非平衡Feistel密碼相比其有所修改,其中  的長度不等[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網絡,ThreefishSkein)是一個非Feistel的分組密碼,其一部分使用了類Feistel的MIX函數。

Feistel密碼列表

編輯

Feistel或修改過的Feistel密碼:

廣義Feistel:

參見

編輯

參考

編輯
  1. ^ Menezes, Alfred J.; Oorschot, Paul C. van; Vanstone, Scott A. Handbook of Applied Cryptography Fifth. 2001: 251. ISBN 0849385237. 
  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) 
  3. ^ Patarin, Jacques, Boneh, Dan , 編, Luby–Rackoff: 7 Rounds Are Enough for 2n(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) (英語). 
  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]. 
  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) (英語).