[科普中国]-分组密码

研究历史

现代分组密码的研究始于20世纪70年代中期，至今已有40余年历史，这期间人们在这一研究领域已经取得了丰硕的研究成果。

对于分组密码，在早期的研究，基本上是围绕DES进行的，推出了一些类似的算法，例如：LOKI，FEAL，GOST等。进入20世纪90年代，人们对DES算法研究更加深入，特别是差分密码分析（differential cryptanalysis）和线性密码分析（linear cryptanalysis）的提出，迫使人们不得不研究新的密码结构。IDEA密码打破了DES类密码的垄断局面，随后出现了SQUARE、SHARK、SAFER-64等采用了结构非常清晰的代替—置换（SP）网络，从理论上给出了最大差分特征概率和最佳线性逼近优势的界，证明了密码对差分密码分析和线性密码分析的安全性。

AES的征集掀起了分组密码研究的新高潮，15个AES候选算法反映了当前分组密码设计的水平，也可以说是近几年研究成果的一个汇总。

目前分组密码所采用的整体结构可分为Feistel结构（例如CAST—256、DEAL、DFC、E2等）、SP网络（例如Safer+、Serpent等）及其他密码结构（例如Frog和HPC）。加解密相似是Feistel型密码的一个实现优点，但它在密码的扩散似乎有些慢，例如需要两轮才能改变输入的每一个比特。SP的网络结构非常清晰，S一般被称为混淆层，主要起混淆作用。P一般被称为扩散层，主要起扩散作用。在明确S和P的某些密码指标后，设计者能估计SP型密码抵抗差分密码分析和线性密码分析的能力。SP网络和Feistel网络相比，可以得到更快速的扩散，但是SP密码的加/解密通常不相似。

分组密码是现代密码学中的一个重要研究分支，其诞生和发展有着广泛的实用背景和重要的理论价值。目前这一领域还有许多理论和实际问题有待继续研究和完善。这些问题包括：如何设计可证明安全的密码算法；如何加强现有算法及其工作模式的安全性；如何测试密码算法的安全性；如何设计安全的密码组件，例如S—盒、扩散层及密钥扩散算法等。1

研究内容大体上，分组密码的研究包括三方面：分组密码的设计原理，分组密码的安全性分析和分组密码的统计性能测试。1

设计分析分组密码的设计与分析是两个既相互对立又相互依存的研究方向，正是由于这种对立促进了分组密码的飞速发展。早期的研究基本上是围绕DES进行，推出了许多类似于DES的密码，例如，LOKI、FEAL、GOST等。进入90年代，人们对DES类密码的研究更加深入，特别是差分密码分析（differential cryptanalysis）和线性密码分析（linear cryptanalysis）的提出，迫使人们不得不研究新的密码结构。IDEA密码的出现打破了DES类密码的垄断局面，IDEA密码的设计思想是混合使用来自不同代数群中的运算。随后出现的Square、Shark和Safer-64都采用了结构非常清晰的代替-置换（SP）网络，每一轮由混淆层和扩散层组成。这种结构的最大优点是能够从理论上给出最大差分特征概率和最佳线性逼近优势的界，也就是密码对差分密码分析和线性密码分析是可证明安全的。1

设计原则扩散（diffusion）和扰乱（confusion）是影响密码安全的主要因素。扩散的目的是让明文中的单个数字影响密文中的多个数字，从而使明文的统计特征在密文中消失，相当于明文的统计结构被扩散。例如，最简单的方法让明文中的一个数字影响密文中的k个数字，可以用：

扰乱是指让密钥与密文的统计信息之间的关系变得复杂，从而增加通过统计方法进行攻击的难度。扰乱可以通过各种代换算法实现。

设计安全的分组加密算法，需要考虑对现有密码分析方法的抵抗，如差分分析、线性分析等，还需要考虑密码安全强度的稳定性。此外，用软件实现的分组加密要保证每个组的长度适合软件编程（如8、16、32……），尽量避免位置换操作，以及使用加法、乘法、移位等处理器提供的标准指令；从硬件实现的角度，加密和解密要在同一个器件上都可以实现，即加密解密硬件实现的相似性。2

AES征集AES的征集掀起了分组密码研究的新高潮，15个AES候选算法反映了当前分组密码设计的水平，可以说是近几年研究成果的一个总汇。分组密码所采用的整体结构可分为Feistel结构（如CAST-256、DEAL、DFC/E2等）、SP网络（如Safer+、Serpent等）及其他密码结构（如Frog和HPC）。Feistel结构由于DES的公布而广为人知，已被许多分组密码所采用。Feistel结构的最大优点是容易保证加解密相似，这一点在实现中尤其重要。而SP网络比较难做到这一点，但是SP网络的扩散特性比较好。在现有的分组密码中，所有的基本运算有异或、加、减、查表、乘及数据依赖循环等。查表运算提供了DES的安全基础，仔细地选择S-盒能较好地抗击线性和差分密码分析，提供好的数据及密钥比特的雪崩特性。不过，S-盒需要一些存储器，所以S-盒的规模不能太大。15个AES候选算法所采用的S-盒规模有6种，分别是4×4、8×8、8×32、11×8、13×8、及8×32。S-盒的另一中称呼是黑盒子，它常给人造成故意设置陷阱的嫌疑，因此，Safer+等选取公开的数学函数，避免嫌疑。S-盒的设计与分析是分组密码设计中的重要环节，它的好坏直接影响密码体制的安全性，对S-盒的设计并没有一个完备的要求，但总的希望是增强S-盒的非线性度、差分均匀性及分量函数的代数次数和项数。

对分组密码安全性的讨论主要包括差分密码分析、线性密码分析和强力攻击等。从理论上讲，差分密码分析和线性密码分析是目前攻击分组密码的最有效的方法，而从实际上说，强力攻击是攻击分组密码最可靠的方法。到目前为止，已有大量文献讨论各种分组密码的安全性。自AES候选算法公布以后，国内外许多专家都致力于候选算法的安全性分析，预计将会推出一些新的攻击方法，这无疑将进一步推动分组密码的发展。

与序列密码每次加密处理数据流的一位或一个字节不同，分组密码处理的单位是一组明文，即将明文消息编码后的数字序列m0，m1，m2，…，mi划分成长为L位的组m=(m0，m1，m2，…，mL-1)，各个长为L的分组分别在密钥k=(k0，k1，k2，…，kt-1)（密钥长为t）的控制下变换成与明文组等长的一组密文输出数字序列c=(c0，c1，c2，…，cL-1)。L通常为64或128。分组密码的模型如图2.3所示。

设明文m与密文c均为二进制0、1数字序列，它们的每一个分量mi，DF(2)(i=0，1，2，…，n-1)，则明文空间为{0，1，…，2n-1}，密文空间也为0，1，…，2n-1}，分组密码是由密钥k=(k0，k1，k2，…，kt-1)确定的一个一一映射，也就是空间{0，1，…，2n-1}，到自身的一个置换F，由于置换F是由密钥k所确定，一般地，我们把这个置换表示为C=Fk(m)。2

算法要求分组密码算法实际上就是密钥控制下，通过某个置换来实现对明文分组的加密变换。为了保证密码算法的安全强度，对密码算法的要求如下。

分组长度足够大当分组长度较小时，分组密码类似于古典的代替密码，它仍然保留了明文的统计信息，这种统计信息将给攻击者留下可乘之机，攻击者可以有效地穷举明文空间，得到密码变换本身。

密钥量足够大分组密码的密钥所确定密码变换只是所有置换中极小一部分。如果这一部分足够小，攻击者可以有效地穷举明文空间所确定所有的置换。这时，攻击者就可以对密文进行解密，以得到有意义的明文。

密码变换足够复杂使攻击者除了穷举法以外，找不到其他快捷的破译方法。3

技术总结优点明文信息良好的扩展性，对插入的敏感性，不需要密钥同步，较强的适用性，适合作为加密标准。

缺点加密速度慢，错误扩散和传播。

分组密码将定长的明文块转换成等长的密文，这一过程在秘钥的控制之下。使用逆向变换和同一密钥来实现解密。对于当前的许多分组密码，分组大小是 64 位，但这很可能会增加。

明文消息通常要比特定的分组大小长得多，而且使用不同的技术或操作方式。这样的方式示例有：电子编码本（ECB）、密码分组链接（CBC）或密码反馈（CFB）。ECB 使用同一个密钥简单地将每个明文块一个接一个地进行加密；在 CBC 方式中，每个明文块在加密前先与前一密文块进行“异或”运算，从而增加了复杂程度，可以使某些攻击更难以实施。 “输出反馈”方式（OFB）类似 CBC 方式，但是进行“异或”的量是独立生成的。 CBC 受到广泛使用，例如在 DES（qv）实现中，而且在有关密码术的技术性方面的相应书籍中深入讨论了各种方式。请注意：您自己建立的 密码系统的普遍弱点就是以简单的形式来使用某些公开的算法，而不是以提供了额外保护的特定方式使用。

迭代的分组密码是那些其加密过程有多次循环的密码，因此提高了安全性。在每个循环中，可以通过使用特殊的函数从初始秘钥派生出的子密钥来应用适当的变换。该附加的计算需求必然会影响可以管理加密的速度，因此在安全性需要和执行速度之间存在着一种平衡。天下没有免费的午餐，密码术也是如此；与其它地方一样，应用适当方法的技巧中有一部分是源于对需要进行的权衡以及它们与需求平衡的关系如何的理解。

分组密码包括DES、IDEA、SAFER、Blowfish和 Skipjack — 最后一个是“美国国家安全局（US National Security Agency，NSA）”限制器芯片中使用的算法。3