计算机科学

首页 > 计算机科学

费斯妥密码

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

费斯妥网络是一种迭代密码,其中的内部函数称为轮函数。[1]

目录

  • 1 历史
  • 2 理论工作
  • 3 构造细节
    • 3.1 非平衡Feistel密码
    • 3.2 其他用途
    • 3.3 Feistel网络作为设计组件
  • 4 Feistel密码列表
  • 5 参见
  • 6 参考

历史

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]

构造细节

Feistel cipher diagram en.svg

为轮函数,并令分别为轮的子密钥。

基本操作如下:

将明文块拆分为两个等长的块,(, )

对每轮,计算

则密文为

解密密文则通过计算

就是明文。

与代换-置换网络相比,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密码:

  • Blowfish
  • Camellia
  • CAST-128
  • DES
  • FEAL
  • GOST 28147-89
  • ICE

  • KASUMI
  • LOKI97
  • Lucifer
  • MARS
  • MAGENTA
  • MISTY1

  • RC5
  • Simon
  • TEA
  • 三重DES
  • Twofish
  • XTEA

广义Feistel:

  • CAST-256
  • CLEFIA
  • MacGuffin
  • RC2

  • RC6
  • Skipjack
  • SMS4

参见

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

参考

  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, ISSN 0097-5397, doi:10.1137/0217022 
  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 
  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 (英语). 
  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 (英语). 
  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 (英语). 

上一篇:Zcash
下一篇:随机性
相关推荐