DES已经不再被推荐使用,请使用AES替代。

数据加密标准(Data Encryption Standard, DES)中的算法是第一个并且是最重要的现代对称加密算法,是美国国家安全标准局于1977年公布的由IBM公司研制的加密算法,主要用于与国家安全无关的信息加密。在数据加密标准被公布后的20多年里,其在世界范围内得到了广泛的应用,经受了各种密码分析和攻击,表现出了令人满意的安全性。

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

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

在某些文献中,作为算法的DES被称为DEA(Data Encryption Algorithm,数据加密算法),以与作为标准的DES区分开来。在发音时,DES可以作为缩写按字母拼出来(/ˌdiːˌiːˈɛs/),或作为一个词念成/ˈdɛz/。

DES采用分组加密方法,待处理的消息会被分为定长数据分组。以待加密的明文为例,将明文按8个字节为一组进行分组,而8个二进制位为一个字节,即每个明文分组为64位二进制数据,每组数据单独进行加密处理。在DES加密算法中,明文和密文均为64位,有效密钥长度为56位,即DES加密或解密算法输入64位的明文或密文消息和56位的密钥,输出64位的密文或明文消息。DES的加密和解密算法相同,只是解密子密钥与加密子密钥的使用顺序刚好相反。

DES的加密过程的整体描述如图1所示,主要可分为3步。

第一步:对输入的64位明文分组进行固定的“初始置换”(Initial Permutation,IP),即按固定的规则重新排列明文分组的64位二进制数据,将重排后的64位数据按前后各32位分为独立的左右两个部分,前32位记为L,后32位记为R。我们可以将这个初始置换写为:

(L,R)←IP(64位分组明文)

因初始置换函数是固定且公开的,故初始置换并无明显的密码意义。

第二步:进行16轮相同函数的迭代处理。将上一轮输出的Ri-1直接作为Li输入,同时将Ri-1与第i个48位的子密钥ki经“轮函数f”转换后,得到一个32位的中间结果,再将此中间结果与上一轮的Li-1做异或运算,并将得到的新的32位结果作为下一轮的Ri。如此往复,迭代处理16次,每次的子密钥均不同。我们可以将这一过程写为:

Li←Ri-1
Ri←Li-1⊕f(Ri-1, ki)

这个运算的特点是交换两个半分组,一轮运算左半分组的输入是上一轮运算右半分组的输出,交换运算是一个简单的密码换位运算,目的是获得更大程度的“信息扩散”。显而易见,DES的这一步是代换密码和换位密码的结合。

第三步:将第16轮迭代结果左右两半组L16、R16直接合并为64位(L16,R16),并输入到初始逆置换以消除初始置换的影响。这一步的输出结果即为加密过程的密文。我们可以将这一过程写为:

输出64位密文←IP-1(L16,R16)

需要注意的是,在将最后一轮输出结果的两个半分组输入初始逆置换之前,还需要进行一次交换。如图1所示,在最后的输入中,右边是L16,左边是R16,合并后左半分组在前,右半分组在后,即(L16,R16)。

(1)初始置换IP和初始逆置换IP-1

表1和表2分别定义了初始置换与初始逆置换。置换表中的数字从1到64,共64个,代表输入的64位二进制明文或密文数据中每一位数从左至右的位置序号。置换表中的数字位置即为置换后数字对应的原位置数据在输出的64位序列中新的位置序号。例如,表中第一个数字为58,其表示输入64位明文或密文二进制数据的第58位;而58位于第一位,则表示将原二进制数据的第58位换到输出的第1位。

表1 DES的初始置换表IP

表2 DES的初始逆置换表IP-1

(2)轮函数f

DES的轮函数如图2所示,其可被描述为4步。

图2 DES的轮函数

第一步:扩展E变换(expansion box,E盒),即将输入的32位数据扩展为48位。扩展E变换如表3所示,表中元素的意义与初始置换基本相同,按行顺序,从左至右共48位。例如,第一个元素为32,其表示48位输出结果的第一位数据,该数据为原输入32位数据中的第32位上的数据。

表3 E盒扩展表

E盒的真正作用是确保最终的密文与所有的明文都有关。

第二步:将第一步输出结果的48位二进制数据与48位子密钥ki按位做异或运算,结果自然为48位。然后将运算结果(48位二进制数据)从左到右每6位分为一组,共分8组。

第三步:将8组6位的二进制数据分别装入8个不同的S盒,即每个S盒输入6位数据,输出4位数据,然后再将8个S盒输出的8组4位数据依次连接,重新合并为32位数据。

第四步:将第三步合并生成的32位数据经P盒(permutation box)置换,输出新的32位数据。P盒置换如表4所示。

表4 P盒置换表

P盒置换表中的数字前面的相似。按行的顺序,从左到右,表中第i个位置对应的数据j表示输出的第i位数据为输入的第j位数据。P盒的8行4列与8个S盒在设计准则上有一定的对应关系,但从应用角度来看,依然是按行的顺序。P盒输出的32位数据即为轮函数的最终输出结果。

(3)替换盒

替换盒(substitution box,S盒)是DES的核心部分。利用通过S盒定义的非线性替换,DES实现了明文消息在密文消息空间上的随机非线性分布。S盒的非线性替换特征意味着,给定一组输入-输出值,很难预计所有S盒的输出。

共有8种不同的S盒,如图3所示,每种S盒接收的6位数据(输入)均可通过定义的非线性映射变换为4位的输出。一个S盒有一个16列4行数表,它的每个元素都是一个4位二进制数,通常表示为十进制数0~15。IBM公司已经公布了S盒与P盒的设计准则,感兴趣的朋友可以查阅相关资料进行学习。

图3 8种不同的S盒

S盒的替代运算规则:设输入的6位二进制数为“b1b2b3b4b5b6”,则以“b1b6”组成的二进制数为行号,以“b2b3b4b5”组成的二进制数为列号,取出S盒中行列交点处的数,并将其转换成二进制数输出。由于表中十进制数的范围是0~15,因此以二进制表示正好4位。以6位输入数据“011001”经S1替代运算为例,如图4所示,取出1行12列处的元素9,由于9=(1001)2,故输出4位二进制数为“1001”。

图4 S盒替代运算举例

(4)DES的子密钥

在DES加密过程中需要16个48位的子密钥。子密钥是由用户提供的64位密钥经16轮迭代运算依次生成的。DES子密钥生成过程如图5所示,主要可分为3个阶段。

图5 DES子密钥生成过程

第一阶段:用户提供由8个字符组成的密钥,将其转换成ASCII的64位,再经置换选择1(如表5所示)去除8个奇偶校验位,并重新排列各位。由表5可知,8、16、24、32、40、48、56、64位舍去了,重新组合后得到56位。由于舍去规则是固定的,因而实际使用的初始密钥只有56位。

表5 置换选择1

第二阶段:将上一步置换选择后生成的56位密钥分成左右两个部分,前28位记为C,后28位记为D。然后分别将28位的C、D循环左移位一次,移位后将分别得到的C1、D1作为下一轮子密钥生成的位输入。每轮迭代循环左移位的次数遵循固定的规则,如表6所示。

表6 循环左移位的次数

第三阶段:将C1、D1合并后得到的56位数据(C1,D1)经置换选择2(如表7所示),即经固定的规则,置换选择出重新排列的48位二进制数据,即为子密钥k1。

表7 置换选择2

将C1、D1作为下一轮的输入,迭代第二、第三两个阶段,即可得到k2。这样经过16轮迭代即可生成16个48位的子密钥。

(5)DES的解密算法

DES的解密算法与加密算法相同,只是子密钥的使用次序相反,即第一轮用第16个子密钥,第二轮用第15个子密钥,以此类推,最后一轮用第1个子密钥。

实际中使用的56位密钥,共有256≈7.2×1016种可能。一台每毫秒执行一次DES加密运算的计算机,即使仅搜索一半的密钥空间,也需要用1000年的时间才能破译出密文。所以,在20世纪70年代的计算机技术条件下,穷举攻击明显不太实际。DES是一种非常成功的密码技术。

每毫秒执行一次运算的假设过于保守,随着计算机硬件与网络技术的快速发展,56位的密钥显得太短,无法抵抗穷举搜索攻击,尤其到了20世纪90年代后期。


1997年,美国克罗拉多州程序员利用互联网上的14000多台计算机,花费96天时间,成功破解了DES密钥。

1998年,电子前哨基金会(Electronic Frontier Foundation,EFF)设计出了专用的DES密钥搜索机,昵称“深译”(英语:Deep Crack),该机器只需要56小时就能破解一个DES密钥。电子前哨基金会公布了这种机器的设计细节,如此一来,随着硬件速度的提高和造价的下降,任何人都能拥有一台高速破译机,这最终必将导致DES毫无价值。

1998年年底,DES停止使用。


克服短密钥缺陷的一个解决办法是使用不同的密钥,多次运行DES算法。这种方案被称为加密-解密-加密三重DES方案,即3DES。2组56位密钥,实现3次加密。1999年,3DES被颁布为新标准。