費斯妥密碼
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在密碼學中,費斯妥密碼(英語: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密碼的構造,證明了如果輪函數是一個密碼安全的偽隨機函數,使用Ki作為種子,那麼3輪足以使這種分組密碼成為偽隨機置換,而4輪可使它成為「強」偽隨機置換(這意味着,對可以得到其逆排列諭示的攻擊者,它仍然是偽隨機的)[2]。
由於Luby和Rackoff的結果非常重要,Feistel密碼有時也稱為Luby-Rackoff分組密碼。進一步的理論工作對其進行了推廣,給出了更加精確的安全界限[3][4]。
構造細節
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Feistel_cipher_diagram_en.svg/511px-Feistel_cipher_diagram_en.svg.png)
令為輪函數,並令分別為輪的子密鑰。
基本操作如下:
將明文塊拆分為兩個等長的塊,(, )
對每輪,計算
則密文為。
解密密文則通過計算
則就是明文。
與代換-置換網絡相比,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網絡,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 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)
- ^ 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) (英語).