DES的历史

DES最初出现在1970年代早期。1972年，在一个对美国政府的计算机安全需求的研究得出结果后，NBS（国家标准局，现在的NIST）开始征集用于加密政府内非机密敏感信息的加密标准 。因此1973年5月15日，在咨询了美国国家安全局（NSA）之后，NBS向公众征集可以满足严格设计标准的加密算法。然而，没有一个提案可以满足这些要求。因此在，1974年8月27日，NBS开始了第二次征集。这一次，IBM提交了一种在1973-1974年间发展的算法，这份提案被有限度的接受了。这种算法是基于早先霍斯特·费斯妥（Horst Fiestel）提出的Lucifer算法的。费斯妥，沃尔特·塔克曼（Walter Tuchman），道·科柏密斯（Don Coppersmith），艾伦·康海姆（Alan Konheim），卡尔·梅尔（Carl Meyer），迈克·马加什（Mike Matyas），罗伊·阿德勒（Roy Adler），埃德娜·格罗斯曼（Edna Grossman），比尔·诺兹（Bill Notz），林恩·史密斯（Lynn Smith）以及布莱恩特·塔克曼等人参与了IBM在算法设计和分析方面的工作。

美国国家安全局在设计中的作用

1975年3月17日，被选中的DES在“联邦公报”上公布并征集公众意见。次年，NBS举行了两个开放式研讨会以讨论该标准。不同团体提出了一些意见，其中公开密钥加密先驱马丁·海尔曼（Martin Hellman）和威特菲尔德·迪菲（Whitfield Diffie）认为密钥长度过短以及神奇的“S盒”是NSA的不当干涉的结果。这项论点指出，算法被情报部门秘密的削弱了，使得他们—而不是别人—可以简单的读取加密信息 。S盒的设计者之一，艾伦·康海姆指出：“我们将S盒发给了华盛顿，而他们发回来的S盒变得完全不同了。” 因此，美国参议院情报常设特别委员会审查了NSA的行为以判断是否存在不当行为。在1978年出版的一份公开的总结中，该委员会写道：

然而，也有人提到了：

DES小组的另一个成员，沃尔特·塔克曼说：“完全在IBM内，由我们IBM人，发展了DES算法。NSA没有干涉任何设计问题！ ”相反，一本解密了的NSA关于加密历史的书则写道：

以及：

由于艾力·毕汉姆（Eli Biham）和阿迪·萨莫尔（Adi Shamir）独立发现和公开了微分密码分析，一种破解块密码的通用方法，针对S盒中隐藏的弱点的怀疑在1990年平静了下来。DES的S盒的设计使得该算法对这种攻击方法的抵抗能力大大强于随机的S盒，该事实强烈的支持了IBM在1970年代就已经知道了其中的技术背景的说法。这的确是事实—1994年，科柏密斯公开了一些原创的S盒的设计准则 。据史蒂文·列维（Steven Levy）说，IBM的沃森研究院（Watson）在1974年发现了微分密码攻击，而NSA要求保持技术秘密 。科柏密斯解释IBM的保密决定说：“那是因为微分密码攻击是一种强有力的针对许多算法的工具，因此有人认为公开这样的信息可能对国家安全产生不利影响。”列维引用沃尔特·塔克曼的话说：“他们让我们将我们所有的文件可靠的封存起来...我们的确对每一份文件进行编号，并将它们放在保险箱里，因为这些文件被认为是美国政府机密。他们说这样做，所以我照做了。 ”

作为标准的算法

虽然仍有一些批评，DES在1976年11月被确定为联邦标准，并在1977年1月15日作为 FIPSPUB 46 发布 ，被授权用于所有非机密资料。它在1988年（修订为 FIPS-46-1 ），1993年（ FIPS-46-2 ）和1999年（ FIPS-46-3 ），后者被规定为 3DES （见下文）。2002年5月26日，DES终于在公开竞争中被高级加密标准（AES）所取代。2005年5月26日，FIPS 46-3被官方的拒绝了，但NIST确认3DES在2030年以前均可用于敏感政府信息的加密 。

DES算法也定义在了ANSIX3.92 ，以及ISO/IEC 18033-3中 （作为TDEA的一部分）。

1994年发表了另一种理论攻击方法，线性密码分析，但1998年的一次暴力攻击显示DES可以被实用的破解，显示了替代算法的迫切需求。晚些时候的文章更详细的探讨了这些密码分析的方法。

DES的导入被认为是密码学的学术研究的催化剂，尤其是对块密码的密码分析。NIST对DES的回顾中提到：

年代简表

替代算法

安全方面和对DES软件相对慢的速度的考虑使得研究者在1980年代晚期和1990年代早期提出了一系列替代的块密码设计，包括RC5，Blowfish，IDEA，NewDES，SAFER，CAST5和FEAL。这些设计的大多数保持了DES的64位的块大小，可以作为DES的直接替代方案，虽然这些方案通常使用64位或128位的密钥。苏联导入了GOST 28147-89算法，该算法的块大小为64位，而密钥长度为256位，并在晚些时候的俄罗斯得到了应用 。

DES本身可以应用和重用到更安全的环境中。许多前DES用户现在使用3DES，这是一个由DES的专利持有人描述和分析的标准 ；它相当于用两个（2TDES）或三个（3TDES）不同的密钥对数据进行三次DES加密。3DES被认为是十分安全的，虽然它的速度较慢。另一个计算花费较小的替代算法是DES-X，它通过将数据在DES加密前后分别与额外的密钥信息进行异或来增加密钥长度。GDES则是一种速度较快的DES变体，但它对微分密码分析较敏感。

2000年10月，在历时接近5年的征集和选拔之后，NIST选择了一种新的密码，高级加密标准（AES）替代DES 。2001年2月28日，联邦公报发表了AES标准，以此开始了其标准化进程 ，并于2001年11月26日成为FIPS PUB 197标准。AES算法在提交的时候称为Rijndael。选拔中其它进入决赛的算法包括RC6，Serpent，MARS和Twofish 。

算法描述

  图1—DES中的总体費斯妥结构

DES是一种典型的块密码—一种将固定长度的平文通过一系列复杂的操作变成同样长度的密文的算法。对DES而言，块长度为64位。同时，DES使用密钥来自定义变换过程，因此算法认为只有持有加密所用的密钥的用户才能解密密文。密钥表面上是64位的，然而只有其中的56位被实际用于算法，其余8位可以被用于奇偶校验，并在算法中被丢弃。因此，DES的有效密钥长度仅为56位。

与其它块密码相似，DES自身并不是加密的实用手段，而必须以某种工作模式进行实际操作。FIPS-81确定了DES使用的几种模式 。FIPS-74包括了更多关于DES使用的讨论 。

整体结构

算法的整体结构如图1所示：有16个相同的处理过程，称为“回次”（ round ），并在首尾各有一次置换，称为 IP 与 FP （或称 IP ，FP为IP的反函数（即IP“撤销”FP的操作，反之亦然）。IP和FP几乎没有密码学上的重要性，为了在1970年代中期的硬件上简化输入输出数据库的过程而被显式的包括在标准中。

在主处理回次前，数据块被分成两个32位的半块，并被分别处理；这种交叉的方式被称为费斯妥结构。费斯妥结构保证了加密和解密过程足够相似—唯一的区别在于子密钥在解密时是以反向的顺序应用的，而剩余部分均相同。这样的设计大大简化了算法的实现，尤其是硬件实现，因为没有区分加密和解密算法的需要。

图中的⊕符号代表异或（XOR）操作。“F函数”将数据半块与某个子密钥进行处理。然后，一个F函数的输出与另一个半块异或之后，再与原本的半块组合并交换顺序，进入下一个回次的处理。在最后一个回次完成时，两个半块需要交换顺序，这是费斯妥结构的一个特点，以保证加解密的过程相似。

费斯妥函数（F函数）

图2中显示了费斯妥函数（F函数）的过程。其每次对半块（32位）进行操作，并包括四个步骤：

  图2—DES的費斯妥函数（F函数）

扩张 —用扩张置换（图中的 E ）将32位的半块扩展到48位，其输出包括8个6位的块，每块包含4位对应的输入位，加上两个邻接的块中紧邻的位。

与密钥混合 —用异或操作将扩张的结果和一个 子密钥 进行混合。16个48位的子密钥—每个用于一个回次的F变换—是利用密钥调度从主密钥生成的（见下文）。

S盒 —在与子密钥混合之后，块被分成8个6位的块，然后使用“S盒”，或称“置换盒”进行处理。8个S盒的每一个都使用以查找表方式提供的非线性的变换将它的6个输入位变成4个输出位。S盒提供了DES的核心安全性—如果没有S盒，密码会是线性的，很容易破解。

置换 —最后，S盒的32个输出位利用固定的置换，“P置换”进行重组。这个设计是为了将每个S盒的4位输出在下一回次的扩张后，使用4个不同的S盒进行处理。

S盒，P置换和E扩张各自满足了克劳德·香农在1940年代提出的实用密码所需的必要条件，“混淆与扩散”。

密钥调度

  图3—DES的密钥调度

图3显示了加密过程中的 密钥调度 —产生子密钥的算法。首先，使用 选择置换1 （PC-1）从64位输入密钥中选出56位的密钥—剩下的8位要么直接丢弃，要么作为奇偶校验位。然后，56位分成两个28位的半密钥；每个半密钥接下来都被分别处理。在接下来的回次中，两个半密钥都被左移1或2位（由回次数决定），然后通过 选择置换2 （PC-2）产生48位的子密钥—每个半密钥24位。移位（图中由 << 标示）表明每个子密钥中使用了不同的位，每个位大致在16个子密钥中的14个出现。

解密过程中，除了子密钥输出的顺序相反外，密钥调度的过程与加密完全相同。

安全与密码分析

虽然已发表的针对DES的密码分析的研究文章多于所有其它的块密码，到目前为止，最实用的攻击方法仍然是暴力攻击。已知DES有一些次要的可能导致加密强度降低的密码学特性，同时有3种理论攻击的理论复杂性小于暴力破解，但需要不现实的已知明文或选择明文数量，并无实用价值。

暴力破解

对于一切密码而言，最基本的攻击方法是暴力破解法—依次尝试所有可能的密钥。密钥长度决定了可能的密钥数量，因此也决定了这种方法的可行性。对于DES，即使在它成为标准之前就有一些关于其密钥长度的适当性的问题，而且也正是它的密钥长度，而不是理论密码分析迫使它被后续算法所替代。在设计时，在与包括NSA在内的外部顾问讨论后，密钥长度被从128位减少到了56位以适应在单芯片上实现算法 。

 EFF的价值250,000美元的DES破解机包括1,856个自定义的芯片，可以在数天内破解一个DES密钥—本图显示了使用数个Deep Crack芯片搭成的DES破解机

在学术上，曾有数个DES破解机被提出。1977年，迪菲和海尔曼提出了一部造价约2千万美元的破解机，可以在一天内找到一个DES密钥。1993年，迈克尔·维纳设计了一部造价约1百万美元的破解机，大约可以在7小时内找到一个密钥。然而，这些早期的设计并没有被实现，至少没有公开的实现。在1990年代晚期，DES开始受到实用的攻击。1997年，RSA安全赞助了一系列的竞赛，奖励第一个成功破解以DES加密的信息的队伍1万美元，洛克·韦尔谢什（Rocke Verser），马特·柯廷（Matt Curtin）和贾斯廷·多尔斯基（Justin Dolske）领导的DESCHALL计划获胜，该计划使用了数千台连接到互联网的计算机的闲置计算能力。1998年，电子前哨基金会（EFF，一个信息 组织 ）制造了一台DES破解机，造价约$250,000。该破解机可以用稍多于2天的时间暴力破解一个密钥，它显示了迅速破解DES的可能性。EFF的动力来自于向大众显示DES不仅在理论上，也在实用上是可破解的：

下一个确认的DES破解机是2006年由德国的鲁尔大学与基尔大学的工作组建造的COPACOBANA。与EFF的不同，COPACOBANA由商业上可获得的，可重配置的FPGA组成。120片并行的XILINX Spartan3-1000型FPGA分为20个DIMM模块，每个模块包括6个FPGA。使用可重配置的FPGA使得这种设备也可以用于其它密码的破解。另外一个关于COPACOBANA的有趣事实是它的成本。一台COPACOBANA的造价大约是$10,000，是EFF设备的25分之一，这充分说明了数字电路的持续进步。考虑到通货膨胀因素，同样价格的设备的性能在8年间大约提到了30倍。2007年，COPACOBANA的两个项目参与者组建的SciEngines公司改进了COPACOBANA，并发展了它的下一代。2008年，他们的COPACOBANA RIVYERA将破解DES的时间减少到了1天以内，使用128片Spartan-3 5000型FPGA。目前SciEngines的RIVYEAR保持着使用暴力破解法破解DES的纪录 。

快于暴力攻击的攻击方法

有三种已知方法可以以小于暴力破解的复杂性破解DES的全部16回次：微分密码分析（DC），线性密码分析（LC），以及戴维斯攻击。然而，这些攻击都是理论性的，难以用于实践；它们有时被归结于认证的弱点。

微分密码分析 在1980年代晚期由艾力·毕汉姆和阿迪·萨莫尔重新发现 ；1970年代IBM和NSA便发现了这种方法，但没有公开。为了破解全部16回次，微分密码分析需要2 组选择明文。DES被设计为对DC具有抵抗性。

线性密码分析 由松井充（Mitsuru Matsui）发现，需要2 组已知明文 ；该方法已被实现 ，是第一种公开的实验性的针对DES的密码分析。没有证据显示DES的设计可以抵抗这种攻击方法。一般概念上的LC—“多线性密码分析”—在1994年由Kaliski和Robshaw所建议 ，并由比留科夫等人于2004年所改进 。线性密码分析的选择明文变种是一种类似的减少数据复杂性的方法 。帕斯卡尔·朱诺德（Pascal Junod）在2001年进行了一些确定线性密码分析的实际时间复杂性的实验，结果显示它比预期的要快，需要约2 –2 次操作 。

改进的戴维斯攻击 ：线性和微分密码分析是针对很多算法的通用技术，而戴维斯攻击是一种针对DES的特别技术，在1980年代由唐纳德·戴维斯（Donald Davies）首先提出，并于1997年为毕汉姆和亚历克斯·比留科夫（Alex Biryukov）所改进 。其最有效的攻击形式需要2 已知明文，计算复杂性亦为2 ，成功率为51%。

也有一些其它的针对削减了回次的密码版本，即少于16回次的DES版本。这些攻击显示了多少回次是安全所需的，以及完整版本拥有多少“安全余量”。微分线性密码分析于1994年为兰福德（Langford）和海尔曼所提出，是一种组合了微分和线性密码分析的方法 。一种增强的微分线性密码分析版本可以利用2 组已知明文可以以2 的时间复杂性破解9回次的DES 。

次要的密码学特性

DES有补码特性，即

DES有四个所谓的弱密钥。若使用弱密钥，加密和解密有相同的效果（参见对合)：

也有6对半弱密钥。若使用某个半弱密钥 K 1 {\displaystyle K_{1}} 进行加密，则相当于使用其对应的半弱密钥 K 2 {\displaystyle K_{2}} 进行解密：

在实现中可以轻易的避开弱密钥和半弱密钥，可以显式的测试密钥，或简单的随机选择密钥：刚好选到弱或半弱密钥的可能性几乎没有。这些密钥事实上并不比其它的密钥弱，因为他们没有给攻击以任何可利用的好处。

DES也被证明不是群，或更精确的，集合 { E K } {\displaystyle \{E_{K}\}} （对于所有可能的密钥 K {\displaystyle K} ）在复合函数之下不是一个群，也不“近似”于一个群 。这有时是一个开放式的问题，而且若是这种情况，破解DES是可能的，且类似于3DES的加密模式不能增加其安全性。

DES的最大密码学安全性被限制在了约64位，除非独立选择每个回次的子密钥而不是从密钥中生成，这样做可以将允许768位的安全性。

参考文献

来源

Ehrsam 等：《用于数据安全的块密码系统产品》, 美国专利 3,962,539 , 1975年2月24日发布

Gilmore, John,《破解DES：加密研究的秘密，窃听政策和芯片设计》, 1998, O"Reilly, ISBN 978-1-56592-520-5

参见

密钥密码学

Skipjack加密

布莱恩特·塔克曼

3DES

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。