DES 加密/解密
数据加密标准
DES 数据加密标准（英语：Data Encryption Standard，缩写为 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 可以作为缩写按字母拼出来(/ˌdiːˌiːˈɛs/)，或作为一个词念成/ˈdɛz/。
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 盒变得完全不同了。”因此，美国参议院情报特别委员会审查了 NSA 的行为以判断是否存在不当行为。在 1978 年出版的一份公开的总结中，该委员会写道：
- 在 DES 的开发中，NSA 使 IBM 确信缩短后的密钥长度也可以满足需求，间接的帮助了 S 盒结构的开发，并确认最终的 DES 算法可以在他们所知范围内没有任何统计学的或数学的弱点。
然而，也有人提到了：
- NSA 没有以任何方式干涉算法的设计。IBM 发明和设计了该算法，做出了一切相关决定，并一致同意密钥长度超出了所有 DES 涉及的商业应用的需要。
DES 小组的另一个成员，沃尔特·塔克曼说：“完全在 IBM 内，由我们 IBM 人，发展了 DES 算法。NSA 没有干涉任何设计问题！”相反，一本解密了的 NSA 关于加密历史的书则写道：
- 1973 年 NBS 向私人工业征集数据加密标准。第一份投标方案令人失望，因此 NSA 开始研究它自己的算法。此后，负责研究和工程的主任霍华德·罗森布拉姆（Howard Rosenblum）发现 IBM 的沃尔特·塔克曼正在研究修改 Lucifer 以适应一般应用。NSA 为塔克曼发放了一份许可，让他与情报部门一起研究 Lucifer 的改进方案。
以及：
- NSA 与 IBM 紧密合作以增强算法针对除了暴力破解以外的攻击方式，并增强被称为 S 盒的置换表的强度。同时，很矛盾的，NSA 试图说服 IBM 将密钥长度从 64 位削减到 48 位，而最终他们达成了妥协，使用 56 位的密钥长度。
由于艾力·毕汉姆（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 日作为 FIPS PUB 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 算法也定义在了 ANSI X3.92，以及 ISO/IEC 18033-3 中（作为 TDEA 的一部分）。
1994 年发表了另一种理论攻击方法，线性密码分析，但 1998 年的一次蛮力攻击显示 DES 可以被实用的破解，显示了替代算法的迫切需求。晚些时候的文章更详细的探讨了这些密码分析的方法。
DES 的导入被认为是密码学的学术研究的催化剂，尤其是对块密码的密码分析。NIST 对 DES 的回顾中提到：
- DES 可以被称为对加密算法的非军用研究和发展的开始。1970 年代除了为军队或情报组织工作的以外，只有很少的密码学者，对密码学的学术研究也很少。现在则有许多活跃的学术性的密码学者，善于密码学方面编程的数学部分，以及商业信息安全公司和顾问。一整代的密码学者都拼命分析（或者说，破解）DES 算法。用密码学家布鲁斯·施奈尔的话说：“DES 在促进密码学界的发展上做的比其它的一切都多。现在有一种算法供学者们分析了。”在 1970 和 1980 年代，密码学中关于 DES 的公开文献所占的比例令人大吃一惊，而且 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 的电视卫星加密系统，VideocipherII | |
| 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 密码分析，线性密码分析 | |
| 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 只允许在遗留的系统中应用 |
| 11 月 26 日 | 2001 | AES 作为 FIPS 197 发布 |
| 5 月 26 日 | 2002 | AES 标准开始生效 |
| 7 月 26 日 | 2004 | “联邦公报”发布了 FIPS 46-3 以及一系列相关标准被驳回的信息 |
| 5 月 19 日 | 2005 | NIST 拒绝了 FIPS 46-3 标准 |
| 4 月 | 2006 | 德国鲁尔大学和基尔大学基于 FPGA 的价值$10,000 的并行计算机 COPACOBANA 在 9 天内破解了 DES在一年内，软件改进将平均时间降低到了 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 标准，以此开始了其标准化进程，并于 2001 年 11 月 26 日成为 FIPS PUB 197 标准。AES 算法在提交的时候称为 Rijndael。选拔中其它进入决赛的算法包括 RC6，Serpent，MARS 和 Twofish。
算法描述
图1 — DES 中的总体费斯妥结构
图2 — DES 的费斯妥函数（F 函数）
图3 — DES 的密钥调度
- 为简明起见，下文中的叙述省略的各变换和置换的细节，可以在 DES 补充材料中找到对应的查找表。
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 位以适应在单芯片上实现算法。
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 是让某些人相信他们不能依赖 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 回次，差分密码分析需要 247 组选择明文。DES 被设计为对 DC 具有抵抗性。
- 线性密码分析由松井充（Mitsuru Matsui）发现，需要 243 组已知明文；该方法已被实现，是第一种公开的实验性的针对 DES 的密码分析。没有证据显示 DES 的设计可以抵抗这种攻击方法。一般概念上的 LC—“多线性密码分析”—在 1994 年由 Kaliski 和 Robshaw 所建议，并由比留科夫等人于 2004 年所改进。线性密码分析的选择明文变种是一种类似的减少数据复杂性的方法。帕斯卡尔·朱诺德（Pascal Junod）在 2001 年进行了一些确定线性密码分析的实际时间复杂性的实验，结果显示它比预期的要快，需要约 239–241 次操作。
- 改进的戴维斯攻击：线性和差分密码分析是针对很多算法的通用技术，而戴维斯攻击是一种针对 DES 的特别技术，在 1980 年代由唐纳德·戴维斯（Donald Davies）首先提出，并于 1997 年为毕汉姆和亚历克斯·比留科夫（Alex Biryukov）所改进。其最有效的攻击形式需要 250 已知明文，计算复杂性亦为 250，成功率为 51%。
也有一些其它的针对削减了回次的密码版本，即少于 16 回次的 DES 版本。这些攻击显示了多少回次是安全所需的，以及完整版本拥有多少“安全余量”。差分线性密码分析于 1994 年为兰福德（Langford）和海尔曼所提出，是一种组合了差分和线性密码分析的方法。一种增强的差分线性密码分析版本可以利用 215.8 组已知明文可以以 229.2 的时间复杂性破解 9 回次的 DES。
次要的密码学特性
DES 有补码特性，即
EK(P) = C <=> EK(P) = C 其中x是 x 的补码，EK是以 K 为密钥的加密函数， P 和 C 分别表示明文和密文。这样的性质表明暴力破解的工作量在选择明文攻击下可以减少一半。
DES 有四个所谓的弱密钥。若使用弱密钥，加密和解密有相同的效果（参见对合）：
EK（EKP）= P 或 EK = DK
也有 6 对半弱密钥。若使用某个半弱密钥K1进行加密，则相当于使用其对应的半弱密钥K2进行解密：
EK1（EK2P）= P 或 EK2 = DK1
在实现中可以轻易的避开弱密钥和半弱密钥，可以显式的测试密钥，或简单的随机选择密钥：刚好选到弱或半弱密钥的可能性几乎没有。这些密钥事实上并不比其它的密钥弱，因为他们没有给攻击以任何可利用的好处。
DES 也被证明不是群，或更精确的，集合{EK}（对于所有可能的密钥K）在复合函数之下不是一个群，也不“近似”于一个群。这有时是一个开放式的问题，而且若是这种情况，破解 DES 是可能的，且类似于 3DES 的加密模式不能增加其安全性。
DES 的最大密码学安全性被限制在了约 64 位，除非独立选择每个回次的子密钥而不是从密钥中生成，这样做可以将允许 768 位的安全性。
