查看“︁费斯妥密码”︁的源代码

{{NoteTA|G1=IT}}

在[[密码学]]中，'''费斯妥密码'''（{{lang-en|Feistel cipher}}）是用于构造[[分组密码]]的对称结构，以[[德国]]出生的[[物理学家]]和密码学家[[霍斯特·费斯妥]]（Horst Feistel）命名，他在美国[[IBM]]工作期间完成了此项开拓性研究。通常也称为'''费斯妥网络'''（Feistel network）。大部分分组[[密码]]使用该方案，包括[[数据加密标准]]（DES）。费斯妥结构的优点在于[[加密]]和[[解密]]操作非常相似，在某些情况下甚至是相同的，只需要逆转[[密钥编排]]。因此，实现这种密码所需的代码或电路大小能几乎减半。

费斯妥网络是一种迭代密码，其中的内部函数称为轮函数。<ref>{{cite book |title=Handbook of Applied Cryptography |first=Alfred J. |last=Menezes |first2=Paul C. van |last2=Oorschot |first3=Scott A. |last3=Vanstone |edition=Fifth |year=2001 |page=251 |isbn=0849385237 }}</ref>

== 历史 ==
Feistel网络最初在IBM的[[Lucifer (密码学)|Lucifer]]密码中商业化，这种密码由[[霍斯特·费斯妥]]和[[Don Coppersmith]]于1973年设计。美国联邦政府在设计[[数据加密标准|DES]]（基于Lucifer密码，由[[美国国家安全局|NSA]]进行修改）时采用了Feistel网络。像DES的其他组件一样，Feistel构造中的迭代特性使得在硬件中（特别是在设计DES时已有的硬件上）实现密码系统更容易。

== 理论工作 ==
许多现代及一些较旧的对称分组密码基于Feistel网络（例如[[GOST 28147-89]]分组密码），且[[密码学家]]已经深入研究了Feistel密码的结构和性质。具体而言，[[Michael Luby]]和[[Charles Rackoff]]分析了Feistel密码的构造，证明了如果轮函数是一个密码安全的[[伪随机函数]]，使用K<sub>i</sub>作为种子，那么3轮足以使这种分组密码成为[[伪随机置换]]，而4轮可使它成为“强”伪随机置换（这意味着，对可以得到其逆排列[[预言机|谕示]]的攻击者，它仍然是伪随机的）<ref name=pseudorandom>{{Citation |first1=Michael |last1=Luby |first2=Charles |last2=Rackoff |title=How to Construct Pseudorandom Permutations from Pseudorandom Functions |journal=SIAM Journal on Computing |volume=17 |issue=2 |date=April 1988 |doi=10.1137/0217022 |url=http://epubs.siam.org/doi/abs/10.1137/0217022 |pages=373–386 |issn=0097-5397 |accessdate=2017-11-21 |archive-date=2019-02-12 |archive-url=https://web.archive.org/web/20190212183024/https://epubs.siam.org/doi/abs/10.1137/0217022 |dead-url=no }}</ref>。

由于Luby和Rackoff的结果非常重要，Feistel密码有时也称为Luby-Rackoff分组密码。进一步的理论工作对其进行了推广，给出了更加精确的安全界限<ref name=7-rounds>{{Citation |first=Jacques |editor1-last=Boneh |last=Patarin |editor1-first=Dan |title=Luby–Rackoff: 7 Rounds Are Enough for 2<sup>''n''(1−ε)</sup> Security |url=https://www.iacr.org/archive/crypto2003/27290510/27290510.pdf |doi=10.1007/b11817 |journal=Advances in Cryptology—CRYPTO 2003 |series=Lecture Notes in Computer Science |volume=2729 |date=October 2003 |pages=513–529 |accessdate=2009-07-27 |archive-date=2017-02-01 |archive-url=https://web.archive.org/web/20170201182122/http://www.iacr.org/archive/crypto2003/27290510/27290510.pdf |dead-url=no }}</ref><ref>{{cite journal|last1=Zheng|first1=Yuliang|last2=Matsumoto|first2=Tsutomu|last3=Imai|first3=Hideki|title=On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses|journal=Advances in Cryptology — CRYPTO’ 89 Proceedings|date=1989-08-20|pages=461–480|doi=10.1007/0-387-34805-0_42|url=https://link.springer.com/chapter/10.1007/0-387-34805-0_42|accessdate=2017-11-21|publisher=Springer, New York, NY|language=en|archive-date=2018-06-09|archive-url=https://web.archive.org/web/20180609232211/https://link.springer.com/chapter/10.1007/0-387-34805-0_42|dead-url=no}}</ref>。

== 构造细节 ==
[[File:Feistel cipher diagram en.svg|right]]

令<math>{\rm F}</math>为轮函数，并令<math>K_0,K_1,\ldots,K_{n}</math>分别为轮<math>0,1,\ldots,n</math>的子密钥。

基本操作如下：

将明文块拆分为两个等长的块，(<math>L_0</math>, <math>R_0</math>)

对每轮<math>i =0,1,\dots,n</math>，计算

:<math>L_{i+1} = R_i\,</math>
:<math>R_{i+1}= L_i \oplus {\rm F}(R_i, K_i).</math>

则密文为<math>(R_{n+1}, L_{n+1})</math>。

解密密文<math>(R_{n+1}, L_{n+1})</math>则通过计算<math>i=n,n-1,\ldots,0</math>

:<math>R_{i} = L_{i+1}\,</math>
:<math>L_{i} = R_{i+1} \oplus \operatorname{F}(L_{i+1}, K_i).</math>

则<math>(L_0,R_0)</math>就是明文。

与[[代换-置换网络]]相比，Feistel模型的一个优点是轮函数<math>\operatorname{F}</math>不必是可逆的。

右图显示了加密和解密的过程。注意解密时子密钥顺序反转，这是加密和解密之间的唯一区别。

=== 非平衡Feistel密码 ===
非平衡Feistel密码相比其有所修改，其中<math>L_0</math>和<math>R_0</math>的长度不等<ref>{{cite journal|last1=Schneier|first1=Bruce|last2=Kelsey|first2=John|title=Unbalanced Feistel networks and block cipher design|journal=Fast Software Encryption|date=1996-02-21|pages=121–144|doi=10.1007/3-540-60865-6_49|url=https://www.schneier.com/academic/paperfiles/paper-unbalanced-feistel.ps.gz|accessdate=2017-11-21|publisher=Springer, Berlin, Heidelberg|language=en|archive-date=2017-09-22|archive-url=https://web.archive.org/web/20170922002349/https://www.schneier.com/academic/paperfiles/paper-unbalanced-feistel.ps.gz|dead-url=no}}</ref>。[[Skipjack (密码学)|Skipjack]]密码就是这种密码的一个例子。[[德州仪器]][[数字签名转发器]]使用专有的非平衡Feistel密码来执行[[挑战-响应认证]]<ref name="crypto-rfid">{{cite journal|last1=Bono|first1=Stephen|last2=Green|first2=Matthew|last3=Stubblefield|first3=Adam|last4=Juels|first4=Ari|last5=Rubin|first5=Aviel|last6=Szydlo|first6=Michael|title=Security Analysis of a Cryptographically-Enabled RFID Device|journal=Proceedings of the USENIX Security Symposium|date=2005-08-05|url=https://www.usenix.org/event/sec05/tech/bono/bono.pdf|accessdate=2017-11-21}}</ref>。

[[Thorp shuffle]]是一种非平衡Feistel密码的极端情况，其中一边只有一位。这比平衡Feistel密码具有更好的可证明安全性，但需要更多轮<ref name="thorp">{{cite journal|last1=Morris|first1=Ben|last2=Rogaway|first2=Phillip|last3=Stegers|first3=Till|title=How to Encipher Messages on a Small Domain|journal=Advances in Cryptology - CRYPTO 2009|date=2009|pages=286–302|doi=10.1007/978-3-642-03356-8_17|url=http://www.cs.ucdavis.edu/~rogaway/papers/thorp.pdf|publisher=Springer, Berlin, Heidelberg|accessdate=2017-11-21|language=en|archive-date=2020-10-23|archive-url=https://web.archive.org/web/20201023000901/https://www.cs.ucdavis.edu/~rogaway/papers/thorp.pdf|dead-url=no}}</ref>。

=== 其他用途 ===
除了分组密码外，Feistel结构也用于其他密码算法。例如，[[最优非对称加密填充]]（OAEP）在某些[[公开密钥加密|非对称密钥加密]]方案中，使用简单的Feistel网络对密文进行随机化。

一个广义的Feistel算法可以用来在大小不是2的幂的小域上创建强排列（参见[[保留格式加密]]）。<ref name=thorp />

=== Feistel网络作为设计组件===
无论整个密码是否是Feistel密码，类Feistel网络都可以在设计密码时用作其中一个组成部分。例如，[[MISTY1]]是一个使用三轮Feistel网络的Feistel密码函数，[[Skipjack (密码学)|Skipjack]]是一个修改的Feistel密码，在它的G置换中使用Feistel网络，[[Threefish]]（[[Skein (哈希函数)|Skein]]）是一个非Feistel的分组密码，其一部分使用了类Feistel的MIX函数。

== Feistel密码列表 ==
Feistel或修改过的Feistel密码：

{{col-begin}}
{{col-break}}
* [[Blowfish (密码学)|Blowfish]]
* [[Camellia (密码学)|Camellia]]
* [[CAST-128]]
* [[数据加密标准|DES]]
* [[FEAL]]
* [[GOST 28147-89]]
* [[ICE (密码学)|ICE]]
{{col-break}}
* [[KASUMI]]
* [[LOKI97]]
* [[Lucifer (密码学)|Lucifer]]
* [[MARS (密码学)|MARS]]
* [[MAGENTA (密码学)|MAGENTA]]
* [[MISTY1]]
{{col-break}}
* [[RC5]]
* [[Simon (密码学)|Simon]]
* [[微型加密算法|TEA]]
* [[三重DES]]
* [[Twofish]]
* [[XTEA]]
{{col-end}}

广义Feistel：

{{col-begin}}
{{col-break}}
* [[CAST-256]]
* [[CLEFIA]]
* [[MacGuffin (密码学)|MacGuffin]]
* [[RC2]]
{{col-break}}
* [[RC6]]
* [[Skipjack (密码学)|Skipjack]]
* [[SMS4]]
{{col-end}}

== 参见 ==
* [[密码学]]
* [[流密码]]
* [[代换-置换网络]]
* [[提升方案]]，用于离散小波变换，具有几乎相同的结构
* [[保留格式加密]]
* [[莱-马西方案]]

== 参考 ==
{{Reflist}}

{{Cryptography navbox | block}}

[[Category:密码学]]
[[Category:费斯妥密码]]