資料加密標準

数据加密标准（，縮寫為 DES）是一种對稱密鑰加密块密码演算法，1976年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），随后在国际上广泛流传开来。它基于使用56位密钥的对称算法。这个算法因为包含一些机密设计元素，相对短的密钥长度以及怀疑内含美國國家安全局（NSA）的后门而在开始时有争议，DES因此受到了强烈的学院派式的审查，并以此推动了现代的块密码及其密码分析的发展。

DES现在已经不是一种安全的加密方法，主要因为它使用的56位密钥过短。1999年1月，distributed.net与电子前哨基金会合作，在22小时15分钟内即公开破解了一个DES密钥。也有一些分析报告提出了该算法的理论上的弱点，虽然在实际中难以应用。为了提供实用所需的安全性，可以使用DES的衍生算法3DES来进行加密，虽然3DES也存在理论上的攻击方法。DES标准和3DES標準已逐漸被高级加密标准（AES）所取代。另外，DES已经不再作为国家标准科技协会（前国家标准局）的一个标准。

在某些文献中，作为算法的DES被称为DEA（Data Encryption Algorithm，数据加密算法），以与作为标准的DES区分开来。在发音时，DES可以作为缩写按字母拼出来()，或作为一个词念成。

 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举行了两个开放式研讨会以讨论该标准。不同团体提出了一些意见，其中公开密钥加密先驱馬丁·赫爾曼和惠特菲爾德·迪菲认为密钥长度过短以及神奇的“S盒”是NSA的不当干涉的结果。这项论点指出，算法被情报部门秘密的削弱了，使得他们—而不是别人—可以简单的读取加密信息。S盒的设计者之一，艾伦·康海姆指出：“我们将S盒发给了华盛顿，而他们发回来的S盒变得完全不同了。”迪菲, W与海尔曼, M, “NBS的DES密码分析完全调查” IEEE Computer 10 (6), June 1977, pp74–84因此，美国参议院情报特别委员会审查了NSA的行为以判断是否存在不当行为。在1978年出版的一份公开的总结中，该委员会写道：

然而，也有人提到了：

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

以及：

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

 作为标准的算法 
虽然仍有一些批评，DES在1976年11月被确定为联邦标准，并在1977年1月15日作为FIPS PUB 46发布NBS，数据加密标准, FIPS-Pub.46. NBS,美国商务部，华盛顿特区, 1977年1月.，被授权用于所有非机密资料。它在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年以前均可用于敏感政府信息的加密国家标准科技协会, NIST Special Publication 800-67 针对TDEA块密码的建议, Version 1.1 。

DES算法也定义在了ANSI X3.92美国国家标准协会，ANSI X3.92-1981 “美国国家标准，数据加密算法”，以及ISO/IEC 18033-3中（作为TDEA的一部分）。

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

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

 年代简表 
 日期 年份 事件 5月15日 1973 NBS第一次征集加密算法标准 8月27日 1974 NBS第二次征集加密算法标准 3月17日 1975 DES在“联邦公报”上发布并征集意见 8月 1976 DES的第一次研讨会 9月 1976 第二次研讨会，讨论DES的数学基础 11月 1976 DES被确认为标准 1月15日 1977 DES被作为FIPS标准FIPS PUB 46发布 1983 DES第一次延长标准期限 1986 HBO开始使用一个基于DES的电视卫星加密系统，Videocipher II 1月22日 1988 DES第二次延长标准期限，称为FIPS 46-1，取代FIPS PUB 46 7月 1990 毕汉姆和萨莫尔重新发现了差分密码分析，并将之应用到了一个15位的类DES密码系统 1992 毕汉姆和萨莫尔发布了第一个复杂性小于暴力破解的理论攻击方法：差分密码分析。然而，这种方法仍然需要不现实的247选择明文。 12月30日 1993 DES作为FIPS 46-2第三次延长标准期限 1994 试验了第一个实验性的DES密码分析，线性密码分析（preprint ） 6月 1997 DESCHAL计划第一次公开破解了DES加密的信息 7月 1998 EFF的DES破解机（Deep Crack）在56小时内破解了DES密钥 1月 1999 Deep Crack和distributed.net合作在22小时15分钟内破解了一个DES密钥 10月25日 1999 DES作为FIPS46-3第四次延长标准期限，其中规定优先使用3DES，而普通DES只允许在遗留的系统中应用http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf  FIPS PUB 46-3：描述DES标准的最新官方文档]（PDF） 11月26日 2001 AES作为FIPS 197发布 5月26日 2002 AES标准开始生效 7月26日 2004“联邦公报”发布了FIPS 46-3以及一系列相关标准被驳回的信息 5月19日 2005NIST拒绝了FIPS 46-3标准 4月 2006 德国鲁尔大学和基尔大学基于FPGA的价值$10,000的并行计算机COPACOBANA在9天内破解了DESS. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, A. Rupp, M. Schimmler, "如何用8,980欧元破解DES". 2nd Workshop on Special-purpose Hardware for Attacking Cryptographic Systems —SHARCS 2006, Cologne, Germany, April 3–4, 2006.在一年内，软件改进将平均时间降低到了6.4天。 11月 2008 COPACOBANA的下一代，RIVYERA将平均破解时间降低到了一天内

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

2000年代，DES逐漸被3DES替代。3DES相当于用两个（2TDES）或三个（3TDES）不同的密钥对数据进行三次DES加密。2010年代，3DES逐漸被更安全的高級加密標準（AES）替代。

2000年10月，在历时接近5年的征集和选拔之后，NIST选择了高级加密标准（AES）替代DES和3DES。2001年2月28日，联邦公报发表了AES标准，以此开始了其标准化进程http://frwebgate.access.gpo.gov/cgi-bin/getdoc.cgi?dbname=2001_register&docid=01-4886-filed.pdf  联邦公报第66卷，40号，2001年2月28日，并于2001年11月26日成为FIPS PUB 197标准。AES算法在提交的时候称为Rijndael。选拔中其它进入决赛的算法包括RC6，Serpent，MARS和Twofishhttp://csrc.nist.gov/archive/aes/round2/AESpressrelease-990809.pdf  NIST发布了加密标准的中选者。

 算法描述 

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

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

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

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

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

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

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

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

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

 暴力破解 

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


在学术上，曾有数个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的纪录在1天内破解DES  [Press release of Firm, demonstrated on 2009 Workshop]。

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

 差分密码分析在1980年代晚期由艾力·毕汉姆和阿迪·萨莫尔重新发现（preprint ）毕汉姆, E和萨莫尔, A.,针对DES的差分密码攻击, Springer Verlag, 1993. ISBN 978-0-387-97930-4, ISBN 978-3-540-97930-2.；1970年代IBM和NSA便发现了这种方法，但没有公开。为了破解全部16回次，差分密码分析需要247组选择明文。DES被设计为对DC具有抵抗性。
 线性密码分析由松井充（Mitsuru Matsui）发现，需要243组已知明文；该方法已被实现，是第一种公开的实验性的针对DES的密码分析。没有证据显示DES的设计可以抵抗这种攻击方法。一般概念上的LC—“多线性密码分析”—在1994年由Kaliski和Robshaw所建议Kaliski, Burton S., Matt Robshaw:使用多近似的线性密码攻击. CRYPTO 1994: pp26–39，并由比留科夫等人于2004年所改进（preprint ）.。线性密码分析的选择明文变种是一种类似的减少数据复杂性的方法。帕斯卡尔·朱诺德（Pascal Junod）在2001年进行了一些确定线性密码分析的实际时间复杂性的实验，结果显示它比预期的要快，需要约239–241次操作。
 改进的戴维斯攻击'''：线性和差分密码分析是针对很多算法的通用技术，而戴维斯攻击是一种针对DES的特别技术，在1980年代由唐纳德·戴维斯（Donald Davies）首先提出，并于1997年为毕汉姆和亚历克斯·比留科夫（Alex Biryukov）所改进毕汉姆, E.一种新的快速DES软件实现破解DES：加密研究，政策干涉和芯片设计的密码 ，电子前哨基金会毕汉姆, E.和比留科夫, A.:对DES的戴维斯攻击的改进. J. Cryptology 10 (3): 195–206 (1997)。其最有效的攻击形式需要250已知明文，计算复杂性亦为250，成功率为51%。

也有一些其它的针对削减了回次的密码版本，即少于16回次的DES版本。这些攻击显示了多少回次是安全所需的，以及完整版本拥有多少“安全余量”。差分线性密码分析于1994年为兰福德（Langford）和海尔曼所提出，是一种组合了差分和线性密码分析的方法兰福德, Susan K.,马丁·E·海尔曼：差分线性密码分析. CRYPTO 1994: 17–25。一种增强的差分线性密码分析版本可以利用215.8组已知明文可以以229.2的时间复杂性破解9回次的DES毕汉姆, E., Orr Dunkelman, Nathan Keller:改进的差分线性密码分析. ASIACRYPT 2002: pp254–266。

 次要的密码学特性 
DES有补码特性，即
其中是的补码，是以为密钥的加密函数，和分别表示明文和密文。这样的性质表明暴力破解的工作量在选择明文攻击下可以减少一半。

DES有四个所谓的弱密钥。若使用弱密钥，加密和解密有相同的效果（参见对合)：
或
也有6对半弱密钥。若使用某个半弱密钥进行加密，则相当于使用其对应的半弱密钥进行解密：
或，
在实现中可以轻易的避开弱密钥和半弱密钥，可以显式的测试密钥，或简单的随机选择密钥：刚好选到弱或半弱密钥的可能性几乎没有。这些密钥事实上并不比其它的密钥弱，因为他们没有给攻击以任何可利用的好处。

DES也被证明不是群，或更精确的，集合（对于所有可能的密钥）在复合函数之下不是一个群，也不“近似”于一个群坎贝尔, K.,维纳, M.: DES不是一个群. CRYPTO 1992: pp512–520。这有时是一个开放式的问题，而且若是这种情况，破解DES是可能的，且类似于3DES的加密模式不能增加其安全性。

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

 参考文献 
 引用 

 来源 

 Ehrsam 等：《用于数据安全的块密码系统产品》, , 1975年2月24日发布
 Gilmore, John. 《破解DES：加密研究的秘密，窃听政策和芯片设计》, 1998, O'Reilly, ISBN 978-1-56592-520-5

 外部链接 
 EFF的DES破解器计划
 针对DES的密码学提示
 John Savard对DES的描述DES
 可以显示中间值的基于Javascript的DES计算器 
 COPACOBANA，鲁尔大学和基尔大学的基于FPGA的价值$10,000的DES破解器
 RFC4772 :使用DES的安全隐患 
 一份简单的DES/3DES实现文档 

 参见 
 密钥密码学

 布萊恩特·塔克曼
 3DES

Category:数据加密标准