3.3 数据加密标准DES

1973年，美国国家标准局（NBS），即现在的国家标准与技术研究所（NIST），公开征集标准密码算法。IBM公司在20世纪70年代初开发出的Lucifer算法的基础上，改进并提交了建议的DES算法。1977年1月15日，美国国家标准局将其批准为联邦标准，并设计推出DES芯片。DES开始在商业领域广泛应用。1981年美国ANSI批准DES作为私营部门的标准，称为DEA。1983年，国际标准化组织ISO也将DES作为数据加密标准，称为DEA-1。原先规定使用期为10年，由于新的加密标准没有及时出台，DES实际上活跃了20多年，在保密通信中扮演着十分重要的角色。

3.3.1 DES的产生与应用

3.3.1.1 DES的产生

1973年5月15日，NBS开始公开征集标准加密算法，并公布了它的设计要求：

（1）算法必须提供高度的安全性。

（2）算法必须有详细的说明，并易于理解。

（3）算法的安全性取决于密钥，不依赖于算法。

（4）算法适用于所有用户。

（5）算法适用于不同应用场合。

（6）算法必须高效、经济。

（7）算法必须能被证实有效。

（8）算法必须是可出口的。

DES产生过程中的一些标志性事件有：

● 1974年8月27日，NBS开始第二次征集，IBM提交了算法LUCIFER，该算法由IBM的工程师在1971年至1972年研制。

● 1975年3月17日，NBS公开了IBM提交的算法的全部细节。

● 1976年，NBS指派了两个小组对算法进行评价。

● 1976年11月23日，DES被采纳为联邦标准，批准用于非军事场合的各种政府机构。

● 1977年1月15日，“数据加密标准”FIPS PUB 46发布，同年7月15日开始生效。

● 该标准规定每5年审查一次，计划5年后采用新标准。

● 最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。

3.3.1.2 DES的应用

DES应用过程中的一些标志性事件有：

● FIPS PUB 81（DES的工作方式）在1980年公布。

● FIPS PUB 74（实现和使用DES的指南）于1981年公布。

● FIPS PUB 112规定了DES用做口令加密的标准。

● FIPS PUB 113规定了DES如何用做计算机数据鉴别。

● 1979年，美国银行协会批准使用DES。

● 1980年，美国国家标准学会（ANSI）赞同DES作为私人使用的标准，称为DEA（ANSI X.392）。

● 1983年，国际化标准组织ISO赞同DES作为国际标准，称为DEA-1。

3.3.2 Feistel密码结构

前面提到分组加密算法实现了n位明密文分组的一一映射，当n较小时，等价于代替变换，当n较大时，比如n = 64，无法表达这样的任意变换。Feistel结构很好地解决了二者之间的矛盾，其基本思想是用简单算法的乘积来近似表达大尺寸的代替变换。

Feistel网络是由Horst Feistel在设计Lucifer分组密码时发明的，并因DES的使用而流行。许多分组密码采用了Feistel网络，如Blowfish、RC5等。

对一个分组长度为n（偶数）比特的l轮Feistel网络，它的加密过程如下。给定明文P，将P分成长度相等的左右两半，并分别记为L0和R0，从而P=L0R0。进行l轮完全类似的迭代运算后，再将左边和右边长度相等的两半合并产生密文分组。图3.2给出了Feistel结构的一轮，其加解密过程如下：

● 加密：Li = Ri-1，Ri = Li-1 ⊕ F（Ri-1,Ki）

● 解密：Ri-1 = Li，Li-1 = Ri ⊕ F（Ri-1,Ki）= Ri ⊕

F（Li,Ki）

其中⊕表示两个比特串的“异或”（XOR），F是轮函数，Ki是由种子密钥K生成的子密钥。

Feistel分组加密算法具有以下特点：

● 分组长度：分组长度越大安全性越高，但加解密速度会下降，64 bit是当时计算条件下较合理的长度。

● 密钥位数：密钥位数越大安全性越高，但加解密速度下降，现在通常使用的密钥长度是128 bit。

● 循环次数：多轮加密可以提高安全性，DES轮函数的迭代次数是16次。

● 子密钥产生算法：算法越复杂，就越增加密码分析的难度。

● 轮函数：轮函数越复杂，就越增加密码分析的难度。

此外，分组加密算法还有两个设计上的考虑：

● 能够快速软件实现，包括加密和解密算法。

● 易于分析，便于掌握算法的保密强度以及扩展办法。

对于DES，还有一些软/硬件实现上的原则。软件实现的要求是使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如8，16，32 bit等。应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算。最好是用标准处理器所具有的一些基本指令，如加法、乘法、移位等。硬件实现的要求是加密和解密的相似性，即加密和解密过程的不同应仅仅在密钥的使用方式上，以便采用同样的器件来实现加密和解密，节省费用和体积。尽量采用标准的组件结构，适于在超大规模集成电路中实现。

3.3.3 对DES的描述

DES是一种对二元数据进行加密的算法，数据分组长度为64位，密文分组长度也是64位。使用的密钥长度为64位，其中有效密钥长度为56位，有8位用于奇偶校验。DES的解密过程和加密相似，但子密钥的使用顺序正好相反。DES的整个体制是公开的，系统的安全性完全取决于密钥的保密。

DES算法的过程示于图3.3中。在一个初始置换IP后，明文组被分成右半部分和左半部分，每部分32位，以L0和R0表示。然后是16轮迭代的乘积变换，称为函数 f，将数据和密钥结合起来。16轮之后，左右两部分再连接起来，经过一个初始逆置换IP-1，算法结束。

初始置换与初始逆置换在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分关系，并将原来明文的校验位x8，x16，…，x64变成置换输出的一个字节。初始置换IP和初始逆置换IP-1如表3.2。

迭代变换是DES算法的核心部分，如图3.4所示。在每轮的开始将输入的64 bit数据分成左、右长度相等的两半，将右半部分原封不动地作为本轮输出的64 bit数据的左半部分，对右半部分进行一系列的变换，即用轮函数作用于右半部分，然后将所得结果（32 bit数据）与输入数据的左半部分进行逐位模2加，将所得数据作为本轮输出的64 bit数据的右半部分。令i表示迭代次数，⊕表示逐位模2求和，f为加密轮函数。DES的加密和解密过程表示如下。加密过程为：

解密过程为：

从图3.4可以看出，轮函数由选择扩展运算E、与子密钥的异或运算、选择压缩变换S和置换运算P组成。

扩展置换运算E将输入32 bit数据扩展为48 bit的输出数据，变换表如表3.3所示，它的作用有三个：

（1）产生了与密钥同长度的数据进行异或运算。

（2）它产生了更长的结果，使得在代替运算时能进行压缩。

（3）输入的一位将影响两个替换，所以输出对输入的依赖性将传播得更快。使得明文或密钥的一点小的变动应该使密文发生一个大的变化，这叫雪崩效应（Avalanche effect）。

选择压缩变换将输入的48 bit数据自左至右分成8组，每组为6 bit。然后输入8个S盒，每个S盒为一非线性代换，有4 bit输出，如图3.5所示。

8个S盒的选择函数关系分别如表3.4所示。对每个S盒，6 bit输入中的第1和第6比特组成的二进制数用于确定S盒的行，中间4位二进制数用来确定S盒的列，对应位置十进制数的4位二进制表示作为输出。假定输入是110011，经过S6盒的输出为1110。具体变换过程如下：

S盒是许多密码算法的唯一非线性部件，因此，它的密码强度决定了整个算法的安全强度，提供了密码算法所必须的混淆作用。

置换P如表3.5所示，P置换的目的是提供雪崩效应，即明文或密钥的一点小的变动都引起密文的较大变化。

子密钥的产生过程如图3.6所示，给定64 bit的密钥K，用置换选择1（PC-1）作用，去掉了输入的第8，16，24，31，40，48，56，64位，这8 bit是奇偶校验位，并重排实际56 bit的密钥。将得到的56 bit数据分成左、右等长的28 bit，分别记为C0和D0。对1≤ i≤ 16，计算和。LS表示循环左移。每轮循环左移的位数为：

然后，将每轮56 bit数据Ci Di用置换选择2（PC-2）作用，去掉了第9，18，22，25，35，38，43，54位，同时重排了剩下的48 bit，输出作为Ki。

置换选择1（PC-1）和置换选择2（PC-2）如表3.6所示。PC-1把64位DES密钥的第8的倍数位去掉，缩减为56位。PC-2再从56位中选出48位。

DES的解密算法和加密算法完全相同，只是各子密钥的使用顺序相反，即为k16，k15，k14，…，k2，k1。算法也是循环右移产生每一圈的子密钥，每次右移的位数为：

3.3.4 对DES的讨论

3.3.4.1 弱密钥与半弱密钥

初始密钥被分成两部分，每部分都单独做移位。如果每一部分的每一位都是0或都是1，则每一圈的子密钥都相同。这样的密钥被称为弱密钥。基于弱密钥的加解密过程是相同的，加密两次就恢复成明文。DES存在4个弱密钥，以十六进制形式表示，参见表3.7。

有些成对的密钥会将明文加密成相同的密文，即一对密钥中的一个能用来解密由另一个密钥加密的消息，这种密钥称作半弱密钥。这些密钥不是产生16个不同的子密钥，而是产生两种不同的子密钥，每一种出现8次。至少有12个半弱密钥。其十六进制形式参见表3.8。

还有些密钥只产生四种子密钥，每种出现四次。这种密钥称为半半弱密钥，共48个。弱密钥、半弱密钥、半半弱密钥加起来有4 + 12 + 48 = 64个，而可能的密钥数是256个。随机选择密钥，落在这64个中的概率很小，而且可以在产生时进行检查，以避免这些密钥。

3.3.4.2 互补密钥

将密钥的0换成1，1换成0，就得到该密钥的补密钥。

通过对一位的二进制变量 A 和 B 运算规律的观察，对于任何等长的 A 和 B，我们有：(A⊕B ′= ⊕) A′ BA， ⊕ = ′⊕。B A B′

对于DES的一轮来说，如果明文和密钥取补，第一个XOR的输入也取补，输出和没有取补时一样，进一步看到对于第二个XOR的输入只有一个取补了，该轮输出是没有取补的输入产生的输出的补。

总体来说，如果用原密钥加密一组明文，则用补密钥可以将明文的补码加密成密文的补码。

设X′表示X的补码，则

这一结论可以用于对DES的选择明文攻击，在一个选择明文攻击中，如果选择明文X，攻击者可以得到Y1 = Ek[X] and Y2 = Ek[X′]，那么穷举式攻击只需要进行255次加密，而不是256次，使测试的密钥减少一半。

注意到，现在选取一个测试密钥T，计算ET [X]，那么有三种可能：

（1）如果结果是Y1，T是正确的密钥。

（2）如果结果是(Y2)′，T′是正确的密钥。

（3）如果都不是，就通过一次加密否定了两个基本密钥。

3.3.4.3 DES的破译

根据攻击者所掌握的信息，可将对对称分组密码的攻击分为以下几类：唯密文攻击、已知明文攻击、选择明文攻击。

攻击的复杂度可以从两个方面衡量，一个是数据复杂度，即实施该攻击所需输入的数据量，一个是处理复杂度，即处理这些数据所需要的计算量。对DES最可靠的攻击办法是强力攻击，此外还有一些比强力攻击更有效的攻击方法：差分密码分析、线性密码分析、插值攻击方法、密钥相关攻击方法等。

强力攻击可以用于任何分组密码，攻击复杂度严格依赖于分组长度和密钥长度。具体而言，强力攻击又可以分为以下几种做法：强力密钥搜索攻击、字典攻击、查表攻击和时间-存储攻击。设k是密钥的长度，在唯密文攻击下，攻击者依次试用密钥空间中所有的2k个密钥解密密文，直到得到一个有意义的明文。其复杂度平均为2k-1。字典攻击是攻击者搜集明密文对，把它们编成字典，当截获密文时，查找密文是否在字典中存在，如果 n 是分组长度，攻击者需要2n个明密文对才能在不知道密钥的情况下解密任何消息。查表法是一种选择明文攻击，对给定明文用所有2k个密钥预先算出密文，这样，对于给定的密文就可以从存储表中找出相应的密钥。时间-存储权衡攻击是一种选择明文攻击，由穷尽密钥搜索和查表攻击两种方法混合而成，比穷尽密钥搜索的时间复杂度小，比查表攻击的空间复杂度小。

1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法，可对DES进行选择明文攻击，通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。线性密码分析本质上是一种已知明文攻击方法，通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统。差分密码分析法需要使用247对明密文进行选择明文攻击，线性密码分析法需要使用247对明密文进行已知明文攻击。由于差分密码分析和线性密码分析所需要的选择（已知）明文数量太大，强力攻击依然是目前实用的攻击，如何改进差分密码分析和线性密码分析的复杂度仍是理论研究的热点。

3.3.4.4 密钥长度的争论

关于DES算法的另一个最有争议的问题就是担心实际56 bit的密钥长度不足以抵御穷举式攻击，因为密钥量只有256个。

早在1977年，Diffie和Hellman已建议制造一个每微秒能测试100万个密钥的VLSI芯片。每微秒测试100 万个密钥的机器大约需要一天就可以搜索整个密钥空间。当时，他们估计制造这样的机器大约需要2000万美元。

Hellman提出通过空间和时间的折中，可以加速密钥的寻找过程。他建议计算并存储256个用每种可能密钥加密一段固定明文的结果。估计机器造价500万美元。

在CRYPTO'93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。此芯片每秒能测试5000万个密钥，用5760个芯片组成的系统需要花费10万美元，它平均用1.5天左右就可找到DES密钥。

1997年1月28日，美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1万美元破译密钥长度为56 bit的DES。美国科罗拉多州的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元。

1998年7月电子前沿基金会（Electronic Frontier Foundation）使用一台25万美元的计算机在56小时内破译了56 bit密钥的DES。

1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。

3.3.4.5 DES的轮数

对于DES，56 bit密钥决定了密钥空间是固定的，为什么说轮函数的循环次数越多则安全性越高？为什么DES是16轮，而不是32轮？

一般来说，循环次数越多进行密码分析的难度就越大，循环次数的选择准则是要使已知密码分析的工作量大于简单的穷举式密钥搜索的工作量。对于16轮循环的DES来说，差分密码分析的运算次数为255.1，而穷举式搜索要求255，前者比后者效率稍低，如果DES有15次循环，那么差分密码分析比穷举式搜索的工作量要小。对DES进行差分密码分析，需要247个选择明文，如果仅有已知明文，就需要多一些的明密文对，使运算量增大到255.1。

3.3.4.6 S盒的设计原理未知

S盒（S-Box）是许多密码算法的唯一非线性部件，因此，它的密码强度决定了整个算法的安全强度，提供了密码算法所必须的混乱作用，如何全面准确地度量S盒的密码强度和设计有效的S盒是分组密码设计和分析中的难题。S盒的设计细节，NSA和IBM都未公开过。Hellman在1976年指出，在DES中仔细选择一些S盒，可以使安全性降低。他们以自己设计的S盒代替DES原来的S盒，证明可以做到这一点，且在一定程度上可以隐蔽S盒构造上的弱点。在差分分析公开后，1992年IBM公布了S盒和P盒设计准则。从本质上说，希望S盒输入向量的任何变动在输出方都产生看似随机的变动。这两种变动之间的关系是非线性的，并难以用线性函数近似。