数据加密标准DES

为了建立适用于计算机系统的商用密码，美国商业部的国家标准局NBS于1973年5月和1974年8月两次发布通告，向社会征求密码算法。在征得的算法中，由IBM公司提出的算法lucifer中选。1975年3月，NBS向社会公布了此算法，以求得公众的评论。于1976年11月被美国政府采用，DES随后被美国国家标准局和美国国家标准协会(American National Standard Institute，ANSI) 承认。1977年1月以数据加密标准DES（Data Encryption Standard）的名称正式向社会公布。

随着攻击技术的发展，DES本身又有发展，如衍生出可抗差分分析攻击的变形DES以及密钥长度为128比特的三重DES等。

DES使用56位密钥对64位的数据块进行加密，并对64位的数据块进行16轮编码。与每轮编码时，一个48位的“每轮”密钥值由56位的完整密钥得出来。DES用软件进行解码需要用很长时间，而用硬件解码速度非常快。在1977年，人们估计要耗资两千万美元才能建成一个专门计算机用于DES的解密，而且需要12个小时的破解才能得到结果。所以，当时DES被认为是一种十分强壮的加密方法。

DES受到的最大攻击是它的密钥长度仅有56比特，1990年S.Biham 和 A.Shamir提出了差分攻击的方法，采用选择明文247攻击，最终找到可能的密钥，M.Matsui 提出的线性分析方法，利用243个已知明文，成功地破译了16圈DES算法，到目前为止，这是最有效的破译方法。

从1997年开始，RSA公司发起了一个称作“向DES挑战”的竞技赛。在首届挑战赛上，罗克·维瑟用了96天时间破解了用DES加密的一段信息。

1999年12月22日，RSA公司发起“第三届DES挑战赛（DES Challenge III）”。2000年1月19日，由电子边疆基金会组织研制的25万美元的DES解密机以22.5小时的战绩，成功地破解了DES加密算法。DES已逐渐完成了它的历史使命。

很多分组密码的结构从本质上说都是基于一个称为Feistel网络的结构。Feistel提出利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果。取一个长度为n的分组（n为偶数），然后把它分为长度为n/2的两部分：L和R。定义一个迭代的分组密码算法，其第i轮的输出取决于前一轮的输出：

L⁽ⁱ⁾= R^(i-1)

R⁽ⁱ⁾= L^(i-1)⊕f(R^(i-1)，K⁽ⁱ⁾)

K⁽ⁱ⁾是i轮的子密钥，f是任意轮函数。

容易看出其逆为：

L^(i-1) = R⁽ⁱ⁾⊕f(R^(i-1)，K⁽ⁱ⁾)= R⁽ⁱ⁾⊕f(L⁽ⁱ⁾，K⁽ⁱ⁾)

DES就是基于Feistel网络的结构。假定信息空间都是由{0，1}组成的字符串，信息被分成64比特的块，密钥是56比特。经过DES加密的密文也是64比特的块。设用m表示信息块，k表示密钥，则：

m=m₁m₂…m₆₄ m_i = 0，1 i = 1，2，…64

k=k₁k₂…k₆₄ k_i = 0，1 i = 1，2，…64

其中k₈，k₁₆，k₂₄，k₃₂，k₄₀，k₄₈，k₅₆，k₆₄是奇偶校验位，真正起作用的仅为56位。

加密算法为E_k(m) = IP^-1·T₁₆·T₁₅……T₁·IP(m)。其中IP为初始置换，IP^-1是IP的逆，T_i，i = 1，2，…16是一系列的变换。解密算法为m=E_k^-1 [E_k(m)]= IP^-1·T₁·T₂……T₁₆·IP[E_k(m)]。

DES的每一密文比特是所有明文比特和所有密钥比特的复合函数。这一特性使明文与密文之间，以及密钥与密文之间不存在统计相关性，因而使得DES具有很高的抗攻击性。整个算法如下：

图4.9 DES算法

（1）初始变换

这是移位操作，用IP表示。移位时不用密钥，仅对64比特明文进行操作。输入64个二进制位明码组，m= m₁m₂…m₆₄。按初始换位表IP进行换位，得到区组B^（0）：B^（0）=b₁⁽⁰⁾b₂⁽⁰⁾…b₆₄⁽⁰⁾= m₅₈m₅₀…m₇。初始变换IP表：

58 50 42 34 26 18 10 2

（2）选择运算

选择运算E，输入32位数据，产生48位输出。

设B^（i）=b₁⁽ⁱ⁾b₂⁽ⁱ⁾…b₆₄⁽ⁱ⁾是第i+1次迭代的64个二进制位输入区组，将B^（i）分为左右两个大小相等的部分，每部分为一个32位二进制的数据块：

L^（i）= l₁⁽ⁱ⁾l₂⁽ⁱ⁾…l₃₂⁽ⁱ⁾= b₁⁽ⁱ⁾b₂⁽ⁱ⁾…b₃₂⁽ⁱ⁾

R^（i）= r₁⁽ⁱ⁾r₂⁽ⁱ⁾…r₃₂⁽ⁱ⁾= b₃₃⁽ⁱ⁾b₃₄⁽ⁱ⁾…b₆₄⁽ⁱ⁾

把R^（i）视为由8个4位二进制的块组成

r₁⁽ⁱ⁾r₂⁽ⁱ⁾r₃⁽ⁱ⁾r₄⁽ⁱ⁾

把它们再扩充为8个6位二进制的块（左右各增加一列）

r₃₂⁽ⁱ⁾r₁⁽ⁱ⁾r₂⁽ⁱ⁾r₃⁽ⁱ⁾r₄⁽ⁱ⁾ r₅⁽ⁱ⁾

用E(R^（i）)表示这个变换，称为选择函数E。

32 1 2 3 4 5

（3）使用密钥

在第i+1次迭代中，用48位二进制的密钥（由56位密钥生成）

K^（i+1）=k₁⁽ⁱ⁺¹⁾k₂⁽ⁱ⁺¹⁾…k₄₈⁽ⁱ⁺¹⁾

与E(R^（i）)按位相加（逻辑异或），输出仍是48位，共8行，每行6位。

Z ₁ ：r₃₂⁽ⁱ⁾+ k₁⁽ⁱ⁺¹⁾ r₁⁽ⁱ⁾ +k₂⁽ⁱ⁺¹⁾ … r₅⁽ⁱ⁾ +k₆⁽ⁱ⁺¹⁾

Z ₂ ：r₄⁽ⁱ⁾+ k₇⁽ⁱ⁺¹⁾ r₅⁽ⁱ⁾ +k₈⁽ⁱ⁺¹⁾ … r₉⁽ⁱ⁾ +k₁₂⁽ⁱ⁺¹⁾

…

Z ₈ ：r₂₈⁽ⁱ⁾+ k₄₃⁽ⁱ⁺¹⁾ r₂₉⁽ⁱ⁾ +k₄₄⁽ⁱ⁺¹⁾ … r₁⁽ⁱ⁾ +k₄₈⁽ⁱ⁺¹⁾

（4）选择函数（S盒）

S₁，S₂...S₈为选择函数，其功能是把6bit数据变为4bit数据。下面给出选择函数S_i(i=1，2......8)的功能表：

S₁:

将以上第j个(1≤j≤8)6位二进制的块（记为Z _j=z_j1 z_j2 z_j3 z_j4 z_j5 z_j6）输入第j个选择函数S_j。各选择函数S_j的功能是把6位数变换成4位数，做法是以z_j1z_j6为行号，z_j2 z_j3 z_j4 z_j5为列号，查找S_j，行列交叉处即是要输出的4位二进制数。

在此以S₁为例说明其功能，我们可以看到：在S₁中，共有4行数据，命名为0，1、2、3行；每行有16列，命名为0、1、2、3，......，14、15列。

现设输入为： D＝101100，令列＝0110，行＝10，坐标为（2，6），然后在S₁表中查得对应的数为2，以4位二进制表示为0010，此即选择函数S₁的输出。由此可见，选择函数实现了代换。

（5）选择函数输出的拼接与换位

八个选择函数S_j(1≤j≤8)的输出拼接为32位二进制数据区组

y₁⁽ⁱ⁾y₂⁽ⁱ⁾…y₃₂⁽ⁱ⁾

把它作为换位函数P的输入，得到输出

X⁽ⁱ⁾= x₁⁽ⁱ⁾x₂⁽ⁱ⁾…x₃₂⁽ⁱ⁾ = y₁₆⁽ⁱ⁾y₇⁽ⁱ⁾…y₂₅⁽ⁱ⁾

记X⁽ⁱ⁾=f(R⁽ⁱ⁾，K⁽ⁱ⁺¹⁾)

换位表P是：

16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10

（6）每轮输出

把L⁽ⁱ⁾与X⁽ⁱ⁾按位相加，形成R⁽ⁱ⁺¹⁾，且令R⁽ⁱ⁾为L⁽ⁱ⁺¹⁾，即得到经第i+1次迭代加密后的输出L⁽ⁱ⁺¹⁾R⁽ⁱ⁺¹⁾，其中：

L⁽ⁱ⁺¹⁾= R⁽ⁱ⁾

R⁽ⁱ⁺¹⁾= L⁽ⁱ⁾⊕f(R⁽ⁱ⁾，K⁽ⁱ⁺¹⁾) (i=0，1，2，…，15)

可以看出，DES密码体制的每一次迭代都用替代法和换位法对上一次迭代的输出进行加密变换。用硬件实现DES算法时，实际上用替代盒实现替代函数S_j(1≤j≤8)，用换位盒实现换位函数P。为了使最后输出的密码文与原始输入的明码文没有明显的函数关系，DES算法采用16次迭代。在前15次迭代中，L⁽ⁱ⁾表示左32位，R⁽ⁱ⁾表示右32位。对最后一次迭代，L⁽¹⁶⁾表示右32位，R⁽¹⁶⁾表示左32位，即在最后一次迭代时不再左右交换，以保证加密和解密的对称性。

（7）逆初始变换

用IP^-1 表示，它和IP互逆。例如，第1位经过初始置换后，处于第58位，而通过逆置换，又将第58位换回到第1位。

逆初始变换IP^-1表：

40 8 48 16 56 24 64 32

（8）子密钥K⁽ⁱ⁾(48bit)的生成算法

密钥计算的目的在于产生加密和解密时所需要的16个子密钥，记作K⁽ⁱ⁾。初始密钥Key值为64位，但DES算法规定，其中第8、16、......64位是奇偶校验位，不参与DES运算。故Key实际可用位数便只有56位。即：经过子密钥换位表PC-1的变换后，Key的位数由64位变成了56位，此56位分为C₀、D₀两部分，各28位。子密钥换位表PC-1如下

57 49 41 33 25 17 9 1 58 50 42 34 26 18

以上为C₀

63 55 47 39 31 23 15 7 62 54 46 38 30 22

以上为D₀

然后分别进行第1次循环左移，得到C₁、D₁，将C₁（28位）、D₁（28位）合并得到56位，再经过子密钥换位表PC-2，便得到了密钥K₁（48位）。子密钥换位表PC-2给出了选择及选择后的次序，可以看出去掉了第9、18、22、25、35、38、43、54位。

14 17 11 24 1 5 3 28 15 6 21 10

C_i、D_i的产生由C_i-1、D_i-1移位得到，依此类推便可得到K⁽²⁾、K⁽³⁾、......、K⁽¹⁶⁾。16次循环左移对应的左移位数要依据下述规则进行：1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

DES算法的解密过程是一样的，区别仅仅在于第一次迭代时用子密钥K^（15），第二次K^（14）、......，最后一次用K^（0），算法本身并没有任何变化。

为了增加密钥的长度，人们建议将一种分组密码进行级联，在不同的密钥作用下，连续多次对一组明文进行加密，通常把这种技术称为多重加密技术。对DES，建议使用3DES增强加密强度。3DES算法是扩展DES密钥长度的一种方法，可使加密密钥长度扩展到128比特（112比特有效）或192比特（168比特有效）。

3DES可以用两个密钥对明文进行三次加密，假设两个密钥是K1和K2：

（1）用密钥K1进行DES加密。

（2）用K2对步骤1的结果进行DES解密。

（3）对2）的结果使用密钥K1进行DES加密。

3DES的缺点是加、解密速度比DES慢。