数据加密标准

数据加密标准

DES的Feistel函数（F函数）
一般的
设计师	IBM
首次出版	1975年（联邦公报）（1977年1月标准化）
来自	路西法
继任者	Triple des ， g-des ， des-x ， loki89 ，冰
密码细节
钥匙尺寸	56位
块尺寸	64位
结构	平衡的Feistel网络
回合	16
最好的公共隐态分析
由于蛮力攻击的可行性，从一开始就被认为是不安全的。在实践中已证明了此类攻击（请参阅Eff Des Cracker ），现在可以在市场上作为服务。截至2008年，最好的分析攻击是线性密码分析，它需要2 43个已知的明文，并且时间复杂性为2 39-43 （Junod，2001）。

数据加密标准（ des ）是用于加密数字数据的对称键算法。尽管它的短长长度为56位，因此对于现代应用来说太不安全了，但它在加密技术的发展方面具有很大影响。

该算法于1970年代初在IBM开发，并根据Horst Feistel的较早设计，根据该机构邀请提出保护敏感，未分类的电子政府数据的候选人，将算法提交给国家标准局（NBS）。 1976年，在与国家安全局（NSA）协商后，NBS选择了一个稍微修改的版本（反对差分密码分析的加强，但针对蛮力攻击却削弱了），该版本是作为官方的联邦信息处理标准（FIPS）出版的1977年美国。

NSA批准的加密标准的发布导致了其迅速的国际收养和广泛的学术审查。争议源于机密设计元素，对称键块密码设计的相对较短的密钥长度以及NSA的参与，引起了对后门的怀疑。促使这些怀疑的S盒是由NSA设计的，以删除他们暗中认识的后门（差分密码分析）。但是，NSA还确保了密钥大小大大降低，以便它们可以通过蛮力攻击破坏密码。随着时间的推移，算法对算法进行了严格的学术审查，导致对块密码及其密码分析的现代理解。

由于相对较短的56位钥匙尺寸， DES是不安全的。 1999年1月， Distributed.net和电子边界基金会合作，在22小时15分钟内公开打破了DES KEY（请参阅§§年代）。也有一些分析结果证明了密码中理论弱点，尽管它们在实践中是不可行的。尽管存在理论攻击，但该算法被认为实际上以三重DES的形式安全。该密码已被高级加密标准（AES）取代。美国国家标准技术学院已撤回了DES的标准。

一些文档将DES标准及其算法区分开，将算法称为DEA （数据加密算法）。

历史

DES日期至1972年的起源，当时美国政府计算机安全局的一项国家标准局研究确定了对政府范围内的标准进行加密，以加密未分类，敏感的信息。

大约在同一时间，工程师Mohamed Atalla于1972年创立了Atalla Corporation ，并开发了第一个硬件安全模块（HSM），该模块是1973年商业化的所谓“ Atalla Box”。它使用安全的销钉生成密钥和安全的离线设备，且是商业上的成功。银行和信用卡公司担心Atalla会主导市场，这促使市场发展了国际加密标准。阿塔拉（Atalla）是银行市场IBM的早期竞争对手，并被IBM员工的影响力所列为DES Standard的IBM员工。 IBM 3624随后采用了与早期Atalla系统相似的PIN验证系统。

1973年5月15日，在与NSA咨询后，NBS征求了符合严格设计标准的密码的建议。这些意见都不合适。 1974年8月27日发出了第二份请求。这次， IBM提交了一名被认为可以接受的候选人 - 根据早期算法， Horst Feistel的Lucifer Cipher，在1973 - 1974年期间开发了一个密码。 IBM参与密码设计和分析的团队包括Feistel， Walter Tuchman ， Don Coppersmith ，Alan Konheim，Carl Meyer，Mike Matyas， Roy Adler ， Edna Grossman ，Edna Grossman，Bill Notz，Lynn Smith和Bryant Tuckerman 。

NSA参与设计

1975年3月17日，提议的DES发表在联邦公报上。要求公开评论，并在接下来的一年举行了两个公开研讨会，讨论了拟议的标准。公开密码学的先驱者马丁·海尔曼（Martin Hellman）和惠特菲尔德（Whitfield）的批评受到了缩短的关键长度和神秘的“ S盒”的批评，这是NSA受到不当干扰的证据。人们的怀疑是，该算法已被情报机构秘密削弱，以便它们（但没有其他人）可以轻松阅读加密信息。 Alan Konheim（DES的设计师之一）评论说：“我们将S-Boxes送往华盛顿。他们回来了，都不同。”美国参议院情报选择委员会审查了NSA的行动，以确定是否有不当参与。委员会写道，在其发现的未分类摘要中，该委员会写道：

在DES的发展中，NSA确信IBM的密钥尺寸减小就足够了。间接协助S-box结构的开发；并证明，据他们所知，最终的DES算法是没有任何统计或数学弱点的。

但是，它也发现

NSA并未以任何方式篡改该算法的设计。 IBM发明并设计了算法，就其做出了所有相关的决定，并同意商定的关键规模足以满足DES预期的所有商业应用。

DES团队的另一位成员Walter Tuchman表示：“我们完全使用IBMERS在IBM中完全开发了DES算法。NSA并没有指示单线！”相比之下，一本关于密码史的NSA编译的书：

1973年，NBS征求了私营企业的数据加密标准（DES）。第一批产品令人失望，因此NSA开始使用自己的算法。然后，研究与工程副总监霍华德·罗森布鲁姆（Howard Rosenblum）发现，IBM的Walter Tuchman正在为路西法（Lucifer）进行修改，以供一般使用。美国国家安全局（NSA）给了塔赫曼（Tuchman）的许可，并将他与代理商进行了与他的路西法修改共同合作。”

和

NSA与IBM紧密合作，以增强除蛮力攻击外的所有算法，并加强称为S-boxes的替代表。相反，NSA试图说服IBM将密钥的长度从64位减少到48位。最终，他们在56位钥匙上妥协。

1990年，人们对S-box中隐藏弱点的一些怀疑进行了消除， Eli Biham和Adi Shamir的独立发现和开放式出版物是差分密码分析，这是打破块密码的一般方法。与随机选择相比，DES的S-box对攻击具有更大的抵抗力，强烈暗示IBM知道1970年代的技术。确实就是这样。 1994年，Don Coppersmith发表了一些S-Boxes的原始设计标准。根据史蒂文·利维（Steven Levy）的说法，IBM Watson研究人员在1974年发现了差异性隐态攻击，并被NSA要求保持这种技术秘密。 Coppersmith解释了IBM的保密决定，他说：“那是因为[差异性密码分析]可以是一种非常强大的工具，用于用于许多方案，并且担心公共领域中的此类信息可能会对国家安全产生不利影响。”利维引用沃尔特·塔克曼（Walter Tuchman）的话：“ [hear hear hear hear hear要求我们将所有文件盖章……我们实际上在每个文件上放了一个数字，并将它们锁定在保险箱中，因为他们被认为是美国政府分类的。他们说这样做。所以。我做到了”。布鲁斯·施尼尔（Bruce Schneier）观察到：“学术界花了二十年的时间才发现NSA“调整”实际上改善了DES的安全性。”

算法标准

尽管受到了批评，但DES于1976年11月被批准为联邦标准，并于1977年1月15日以FIPS Pub 46出版，被授权用于所有未分类数据。随后，它在1983年，1988年重申为标准（以FIPS-46-1的修订），1993年（FIPS-46-2），并在1999年再次确认（FIPS-46-3），后者处方“ Triple des ”（见下文）。 2002年5月26日，在公共竞争之后，DES最终被先进的加密标准（AES）取代。 2005年5月19日，FIPS 46-3正式撤回，但NIST在2030年批准了Triple Des ，以获取敏感的政府信息。

该算法也在ANSI X3.92中指定（今天X3被称为incits ，ANSI X3.92为ANSI incits 92），NIST SP 800-67和ISO/IEC 18033-3（作为TDEA的组成部分）。

1994年发表了另一种理论攻击，即线性密码分析，但1998年电子边界基金会的DES Cracker证明了DES可以非常实际的攻击，并强调了对替代算法的需求。本文稍后将更详细地讨论这些密码分析的方法和其他方法。

DES的引入被认为是密码学学术研究的催化剂，尤其是破解密码的方法。根据关于DES的NIST回顾

可以说，DES已“启动”加密算法的非军事研究和开发。在1970年代，除军事或情报组织的密码学家外，密码学家很少，而对密码学的学术研究很少。现在有许多活跃的学术密码学家，数学部门，具有强大的加密计划以及商业信息安全公司和顾问。一系列的隐性药物已经切断了牙齿分析（即试图“破裂”）DES算法。用密码学家布鲁斯·施尼耶（Bruce Schneier）的话说：“ des所做的更多是为了使密码分析领域比其他任何事物所做的更多。现在有一种算法可以研究。” 1970年代和1980年代的加密文学中，令人惊讶的开放文献涉及DES，而DES是比较了每种对称密钥算法的标准。

年表

描述

DES是原型块密码- 一种算法，该算法采用了固定长度的明文位串，并通过一系列复杂的操作将其转换为相同长度的另一个密文伯特特林。如果是DES，则块大小为64位。 DES还使用钥匙来自定义转换，因此据说只能由那些知道用于加密的特定密钥的人执行解密。表面上的关键由64位组成；但是，算法实际上只有56个。八个位仅用于检查奇偶校验，此后被丢弃。因此，有效的密钥长度为56位。

钥匙名义上存储或传输为8个字节，每个字节都有奇怪的奇偶校验。根据ANSI X3.92-1981（现在称为ANSI Incits 92-1981），第3.5节：

密钥的每个8位字节中的一个位可以用于密钥生成，分布和存储中的错误检测。位8、16，...，64用于确保每个字节都是奇怪的。

像其他块密码一样，DES本身并不是加密的安全手段，而是必须以操作方式使用。 FIPS-81指定多种模式可与DES一起使用。 FIPS-74中包含有关DES使用的进一步评论。

解密使用与加密相同的结构，但使用相反顺序使用的键。 （这具有一个优点，即可以在两个方向上使用相同的硬件或软件。）

整体结构

该算法的整体结构如图1所示：处理的16个相同的处理阶段，称为回合。还有一个初始和最终的排列，称为IP和FP ，它们是倒置（IP“撤消” FP的动作，反之亦然）。 IP和FP没有加密意义，但被包括在内，以促进1970年代中期的8位硬件中进出的装载块。

在主回合之前，将块分为两个32位的半部分，并交替处理。这种纵横交错被称为Feistel方案。 Feistel结构确保解密和加密是非常相似的过程 - 唯一的区别是，解密时以相反顺序应用了子钥匙。其余算法是相同的。这大大简化了实现，尤其是在硬件中，因为不需要单独的加密和解密算法。

⊕符号表示独家或（XOR）操作。 F功能将半个块与一些钥匙拼凑在一起。然后将来自F功能的输出与块的另一半结合，将半部分交换在下一轮之前。最后一轮后，两半被换成；这是Feistel结构的一个特征，它使加密和解密相似。

Feistel（F）功能

图2中描绘的F功能一次在半个块（32位）上运行，包括四个阶段：

1. 扩展：使用膨胀置换量，将32位半块扩展到48位，通过复制一半的位来表示图中表示E。输出由八个6位（8×6 = 48位）件组成，每个零件包含4个相应输入位的副本，以及从每个输入件到任何一侧的紧密相邻位的副本。
2. 密钥混合：结果与XOR操作结合使用。使用密钥附表（如下所述），有16个48位子钥匙（每轮一轮）源自主键。
3. 替换：在子钥匙中混合后，将块分为八个6位零件，然后由S盒或替换盒进行处理。八个S框中的每个S-box中的每个输入位替代了四个输出位，根据非线性转换，以查找表的形式提供。 S-box提供了DES安全性的核心 - 无需它们，密码将是线性的，并且在琐碎的上是可损坏的。
4. 置换：最后，S-BoxES的32次输出根据固定置换式P-Box重新排列。这是设计的，以便在排列后，本轮中每个S-box的输出的位分布在下一轮的四个不同的S-box上。

从S-boxes替换的交替，P-Box和E-Expansion的位置换分别提供了所谓的“混乱和扩散”，这是Claude Shannon在1940年代确定的概念，这是安全的必要条件。但是实用的密码。

关键时间表

图3说明了加密的关键时间表- 生成子键的算法。最初，从最初的64位选择了56位键的选择1 （ PC-1 ） - 其余的八个位被丢弃或用作奇偶校验检查位。然后将56位分为两半；此后每半进行单独处理。在连续的回合中，这两半均由一两个位旋转（每轮指定），然后由置换的选择2 （PC-2）（ PC-2 ） - 24位从左半部分和24位选择48位，从右侧选择24位。旋转（图中用“ <<<”表示）意味着每个子键中使用了不同的位。每个位在16个子钥匙中大约14个中使用。

解密的关键时间表是相似的 - 与加密相比，子键相反。除了这种变化外，该过程与加密相同。相同的28位传递给所有旋转箱。

虚拟程式码

DES算法的伪代码如下。

// All variables are unsigned 64 bits
// Pre-processing: padding with the size difference in bytes
pad message to reach multiple of 64 bits in length
var key // The keys given by the user
var keys[16]
var left, right
// Generate Keys
// PC1 (64 bits to 56 bits) 
key := permutation(key, PC1)
left := (key rightshift 28) and 0xFFFFFFF
right := key and 0xFFFFFFF
for i from 0 to 16 do
	right := right leftrotate KEY_shift[i]
	left := left leftrotate  KEY_shift[i]
	var concat := (left leftshift 28) or right
	// PC2 (56bits to 48bits)
	keys[i] := permutation(concat, PC2)
end for
// To decrypt a message reverse the order of the keys
if decrypt do
	reverse keys
end if
// Encrypt or Decrypt
for each 64-bit chunk of padded message do
	var tmp
	// IP
	chunk := permutation(chunk, IP)
	left := chunk rightshift 32
	right := chunk and 0xFFFFFFFF
	for i from 0 to 16 do
		tmp := right
		// E (32bits to 48bits)
		right := expansion(right, E)
		right := right xor keys[i]
		// Substitution (48bits to 32bits)
		right := substitution(right)
		// P
		right := permutation(right, P)
		right := right xor left
		left := tmp
	end for
	// Concat right and left
	var cipher_chunk := (right leftshift 32) or left
	// FP
	cipher_chunk := permutation(cipher_chunk, FP)
end for

安全性和隐性分析

尽管已经发表了有关DES的隐性分析的更多信息，而不是任何其他块密码，但迄今为止，最实际的攻击仍然是一种蛮力的方法。已知各种较小的隐式分析特性，并且可以进行三种理论攻击，尽管理论复杂性小于蛮力攻击，但需要不切实际的已知或选择的纯文本来进行，并且在实践中并不关心。

蛮力攻击

对于任何密码，最基本的攻击方法是蛮力- 依次尝试到所有可能的钥匙。密钥的长度决定了可能的密钥数，因此该方法的可行性。对于DES而言，甚至在将其关键规模的足够早期（甚至在将其作为标准用作）采用之前提出了问题，而这是小关键大小，而不是理论上的密码分析，这决定了需要替换算法的问题。由于涉及包括NSA在内的外部顾问的讨论，关键大小从256位减少到56位，以适合单个芯片。

在学术界，提出了针对Des-Des-rack机器的各种建议。 1977年，Diffie和Hellman提出了一台耗资2000万美元的机器，这可能会在一天内找到DES KEY。到1993年，维纳（Wiener）提出了一台钥匙搜索机器，耗资100万美元，这将在7小时内找到一个钥匙。但是，从未实施过这些早期建议，或者至少没有公开承认实施。 DES的脆弱性在1990年代后期实际上得到了证明。 1997年， RSA Security赞助了一系列比赛，向第一支球队提供了10,000美元的奖金，该团队打破了与DES一起加密比赛的消息。该竞赛由Deschall Project赢得，由Rocke Verser， Matt Curtin和Justin Dolske领导，在整个Internet上使用了数千台计算机的闲置周期。 1998年，当网络空间民权集团电子边境基金会（EFF）建造了一个自定义的Des-cracker，以大约25万美元的成本（请参阅Eff Des Cracker ）。他们的动机是表明DES在实践中以及理论上都是可损坏的：“有很多人不会相信真理，直到他们用自己的眼睛看到它。向他们展示一种物理机器，可以在一些中破解DES日子是说服某些人确实无法相信自己的安全性的唯一方法。

下一个确认的Des Cracker是Bochum和Kiel大学在德国建造的Copacobana机器。与EFF机器不同，Copacobana由市售，可重新配置的集成电路组成。 Xilinx Spartan-3 1000类型的这些现场可编程的门阵列（FPGA）中的120个并行运行。它们分组为20个DIMM模块，每个模块包含6个FPGA。可重新配置硬件的使用也使机器也适用于其他代码破坏任务。 Copacobana更有趣的方面之一是其成本因素。一台机器的建造量约为10,000美元。 EFF机器的成本降低大约25倍是数字硬件不断改进的一个例子，请参阅Moore的定律。调整8年的通货膨胀率会产生约30倍的更高改善。自2007年以来，Copacobana的两个项目合作伙伴的衍生公司Sciengines GmbH增强了Copacobana的继任者。 2008年，他们使用128 spartan-3 5000的Copacobana Rivyera减少了不到一天的时间。 Sciengines Rivyera在使用128 spartan-3 5000 fpgas的情况下以野蛮的折断DES保留了记录。他们的256个Spartan-6 LX150型号这次进一步降低了。

2012年，David Hulton和Moxie Marlinspike宣布了一个系统，该系统具有48 Xilinx virtex-6 LX240T FPGA，每个FPGA均包含40个以400 MHz运行的完全管道的DES核心，总容量为768 GOVAKEYS/SEC。该系统可以在大约26小时内详尽地搜索整个56位键空间，并在线提供此服务。

攻击比蛮力快

已知的三种攻击可以使整个16轮DES的复杂性比蛮力搜索：差分密码分析（DC），线性密码分析（LC）和Davies的攻击。但是，这些攻击是理论上的，通常认为在实践中不可行。这些类型的攻击有时被称为认证弱点。

• Eli Biham和Adi Shamir在1980年代后期重新发现了差分密码分析； IBM和NSA之前都知道它，并保密。为了打破整个16轮，差分密码分析需要2 ^47个选择的明文。 DES被设计为对DC具有抗性。
• 线性密码分析是由Mitsuru Matsui发现的，需要2 ^43个已知的明文（Matsui，1993）。该方法实施（Matsui，1994），是DES的第一次实验性隐式分析。没有证据表明DES是针对这种攻击具有抵抗力的。 LC的概括（多次线性隐式分析）在1994年提出（Kaliski和Robshaw），并由Biryukov等人进一步完善。 （2004）;他们的分析表明，多个线性近似可用于将攻击的数据要求减少至少4倍（即2 ⁴¹而不是2 ⁴³ ）。在线性密码分析的选定plaintext变体中，可以获得类似的数据复杂性（Knudsen和Mathiassen，2000）。 Junod（2001）进行了多个实验，以确定线性隐式分析的实际时间复杂性，并报告说它比预测的速度要快，需要等于2 ³⁹ - 2 ⁴¹ DES评估的时间。
• 改进的戴维斯的攻击：虽然线性和差分密码分析是一般技术，并且可以应用于许多方案，但戴维斯的攻击是DES的一种专业技术，首先是唐纳德·戴维斯（Donald Davies）在八十年代提出的，并得到了Biham and Biryukov （1997年）的改进）。最强大的攻击形式需要2 ^50个已知的明文，其计算复杂性为2 ⁵⁰ ，成功率为51％。

还提出了针对密码减少版本的攻击，即DES的版本不到16发。这种分析可以洞悉安全需要多少个回合，以及完整版本保留的“安全保证金”。

兰福德（Langford）和海尔曼（Hellman）在1994年提出了差异线性密码分析，并将差异和线性隐式分析结合在一起。攻击的增强版本可以通过2 ^15.8选定的明文打破9轮DES，并且具有2 ^29.2的时间复杂性（Biham等人，2002年）。

较小的隐窝特性

des展示了互补特性，即

在其中分别用密钥加密的表格补充分别为纯文本和密文块。互补属性意味着，在所选的plaintext假设下，可以将蛮力攻击的工作减少2（或一个位）。根据定义，此属性也适用于TDE Cipher。

DES也有四个所谓的弱键。弱钥匙下的加密（ E ）和解密（ d ）具有相同的效果（请参阅相关性）：

或等同于

还有六对半湿钥匙。用一对半导性键进行加密，与另一个相同的解密相同。

或等同于

可以通过明确测试它们，或者仅通过随机选择键来避免实现中的弱和半导体密钥很容易；偶然地挑选薄弱或半维克钥匙的机率可以忽略不计。无论如何，这些钥匙并不比任何其他键都弱，因为它们不会给攻击带来任何优势。

DES也被证明不是一个组，或更确切地说，功能组成下的集合（对于所有可能的密钥）不是一个组，也不是“接近”的组。这是一个悬而未决的问题，如果是这样，则可能会破坏DES，并且多种加密模式（例如Triple des）不会增加安全性，因为在不同键下重复加密（和解密）等效于在另一个单键下加密。

简化的DES

简化的DES（SDE）仅用于教育目的，以帮助学生了解现代的隐性技术。 SDE具有与DES相似的结构和特性，但已被简化，以使用铅笔和纸手动执行加密和解密变得更加容易。有些人认为，学习SDE可以洞悉DES和其他块密码，并深入了解对它们的各种隐式分析攻击。

替代算法

对安全性和DES在软件中的相对缓慢操作的担忧使动机研究人员提出了各种替代块密码设计，这些设计在1980年代末和1990年代初开始出现：示例包括RC5 ， Blowfish ， Idea ，Newdes， Newdes， Safer ， Safer ， Cast5和菲尔。这些设计中的大多数都保持了DES的64位块大小，并且可以用作“倒入”替代品，尽管它们通常使用了64位或128位键。在苏联，引入了GOST 28147-89算法，具有64位的大小和256位钥匙，后来在俄罗斯也使用。

DES本身可以在更安全的方案中进行调整和重复使用。现在，许多前DES使用者使用Triple Des （TDE），该DES（TDE）由DES的一位专利权人描述和分析（请参阅FIPS Pub 46-3）；它涉及使用两个（2TD）或三个（3TD）不同的键应用DES。 TDE被认为是足够的安全性，尽管它很慢。 DES-X是一个较不昂贵的计算昂贵的替代方案，它通过在DES之前和之后通过X置额外的关键材料来增加关键大小。 GDES是提出的DES变体，是加快加密加速的一种方式，但事实证明它容易受到差异隐rysiss的影响。

1997年1月2日，NIST宣布希望选择一个继任者。在2001年，在国际比赛之后，NIST选择了一个新的密码，即先进的加密标准（AES）作为替代品。被选为AES的算法是由其设计师提交的，名称为Rijndael 。 NIST AES比赛中的其他决赛入围者包括RC6 ，蛇，火星和Twofish 。

也可以看看

• 蛮力：破解数据加密标准
• DES补充材料
• 跳过（密码）
• 三重