在介绍完Feistel结构之后，接下来进入到著名的DES算法。

6.1 DES算法的意义

在正式介绍DES之前，首先介绍几个重要的历史时间节点。

① 1973年，美国国家标准局(NBS)向社会公开征集加密算法，一直盯加密算法标准。

② 1974年，第二次征集。

③ 1975年，选中IBM的算法，公布征求意见。

④ 1977年1月15日正式颁布。

⑤ 1998年底以后停用。

⑥ 1999年颁布3DES为新标准。

标准加密算法的目标：

① 用于保护政府机构和商业部门的非机密的敏感数据。

② 用于加密保护静态存储和传输信道中的数据。

③ 安全使用10~15年。

DES算法是单射的分组密码算法，是密码学发展的一个重要的阶段（现代密码学诞生的标志之一），对算法的标准化研究和分组密码的发展有重大意义。

目前攻击DES的最有效的办法是密钥穷举攻击。

6.2 DES算法概述

密码的整体特点：

① 分组密码：明文、密文和密钥的分组长度都是64位。

② 面向二进制数据的密码算法：因而能够加解密任何形式的计算机数据。

③ 对合运算：加解密使用同一个算法，使工程量减半。

④ 综合运用了置换、代替、代数等基本密码技术。

⑤ 基本结构属于Feistel结构。

首先，简单看一下DES算法的整体结构，其主要由初始置换IP、轮函数、逆初始置换IP-1以及密钥扩展算法组成。这里直接放上书上的图。

DES算法时迭代型分组密码算法，16轮的Feistel型密码基本参数：

·分组长度：64比特

·密钥长度：64比特

·有效密钥长度：56比特（8比特校验位）

·迭代圈数：16圈

·圈密钥长度：48比特

DES加密标准的核心是采用Fesitel结构。明文分组长度是64比特，初始密钥长度也是64比特（实际上采用的是56比特，8比特校验位），循环轮数为16轮。

6.3 Fesitel型密码

Fesitel模型的优缺点：

优点：设计容易，f函数不要求可逆。

缺点：轮变换有一半的输入没有改变，左右块的处理不能并行实施。

6.4 DES中的轮函数 f(A,J)

A为32比特串，J为48比特串，输出为f(A,J)为32比特串。

① A根据一个固定扩展函数E扩展成一个长为48比特串E(A).

② 计算E(A)⊕J,并将所得结果分成8个长为6的比特串，记为B=B1B2B3B4B5B6B7B8.

③ 使用8个S盒S1,S2,...,S8,每个S盒为6进4出。用4×16矩阵描述。

对 Bj = b1b2b3b4b5b6 计算 Sj(Bj)

b1b6对应Sj的行

b2b3b4b5对应Sj的列

对应二进制表示 Cj=Sj(Bj)

例：有 B1 = 100110

此时有 b1b6=10，b2b3b4b5=0011.则对应第2行第3列（序号从0开始）。

查找S盒找到对应的数字——8.故S1(B1)=1000.

④ 将长为32比特的 C=C1C2...C8通过固定置换P（P盒）：

P(C) = f(A,J)

扩展变换 —— E和扩展

作用： 将输入的32比特扩展为48比特。

扩展方式： 分别将第i-1块最右比特 和 第i+1块最左比特 添加到 第i块的左边 和 右边。形成输出的第i个6比特块。

S盒

S盒代替是DES算法中唯一的非线性变换。在DES算法中起核心作用。

S盒的设计标准对于实现DES算法的安全性，对于实现混乱和扩散原则，对于保障DES算法的密码强度，具有十分重要的作用。

S盒只要稍微改变，其密码强度就会大大改变。

P盒

P盒的设计特点：

① P盒的各输入块的4比特都分配到不同的输出块中。

② P盒的各输出块的4比特都来自不同的输入块。

6.5 轮密钥产生

轮密钥的产生主要包含三个部分：

① 置换选择1 （64比特 -> 56比特，去掉8比特奇偶校验位）

② 循环移位 （分左28比特，右28比特）

③ 置换选择2 （56比特 -> 48比特）

最终得到 16 个 48比特 的 轮密钥。

① 置换选择1

作用：去掉密钥中8比特奇偶校验位；打乱重排，形成C0（左28比特）、D0（右28比特）。

② 循环移位

作用：对Ci、Di分别循环左移位。

③ 置换选择2

作用：从Ci和Di（56比特）中选择出一个48比特的子密钥Ki.

说明：从Ci中取24比特，Di中取24比特。

6.6 加密过程

加密过程可以简单分为三个部分：①初始置换IP ②16轮Feistel结构 ③逆初始置换IP-1

① 初始置换 IP

作用：把64位明文打乱重排。

注意：IP中的置换是有规律的，则对保密是不利的。

② 逆初始置换 IP-1

作用：把64位中间密文打乱重排，形成最终64位密文。

相逆性：IP 与 IP-1 互逆

如：在IP中把输入的第1位置换到第40位，而在IP-1中把输入的第40位置换到第1位。

但保密作用不大。由于没有密钥参与，在IP与IP-1公开的条件下，其保密意义不大。

③ 16轮Feistel结构

（a）扩展置换E

作用：把32位输入扩充为48位中间数据，通过重复使用数据，实现数据扩充。

（b）代替函数组S（S盒）

S盒的一般性质：

S盒是DES中唯一的非线性变换，是DES安全的关键。

在保密性方面，起混淆作用。

共有8个S盒，并行作用。

每个S盒有6个输入，4个输出，是非线性压缩变换。

改变S和任一输入比特，其输出至少2比特发生改变。

其他准则：

非线性准则：S盒必须有足够的非线性度，否则不能抵抗线性攻击。

差分均匀性准则：S盒的差分性应均匀，否则不能抵抗差分攻击。

代数次数及项数分布准则：S盒必须有足够的代数次数和项数，否则不能抵抗插值攻击和高阶差分攻击。

S盒的密码学特性保证了DES的安全。

（c）置换运算P

把数据打乱重排。

在保密性方面，其扩散作用。因为S盒是6位输入，4位输出，其非线性作用是局部的，因此需要把S盒的混淆作用扩散开来。

S盒和P盒相互配合，共同确保DES安全。

6.7 解密过程

DES的加密算法是对合运算，因此解密和加密可以共用同一个算法。

不同点：子密钥的使用顺序不同

第一次解密迭代使用子密钥K16，第二次解密迭代使用子密钥K15，...，第十六次解密迭代使用子密钥K1。

数学描述：

Ri-1=Li i=16,15,...,1.

Li-1=Ri-1⊕f(Li,Ki) i=16,15,...,1.

6.8 DES的对合性和可逆性

① 可逆性证明

（1）定义：变换T是把64位数据的左右两半交换位置。

T(L,R)=(R,L)

因为TT(L,R)=T(R,L)=(L,R)=I，其中I为恒等变换。

又显然TT-1=I，于是TT-1=TT，所以有

T=T-1

所以T变换是对合运算。

（2）记DES第i轮中的主要运算为Fi，即

Fi(Li-1,Ri-1)=(Li-1⊕f(Ri-1,Ki),Ri-1)

Fi2(Li-1,Ri-1)=Fi(Li-1⊕f(Ri-1,Ki),Ri-1)=(Li-1⊕f(Ri-1,Ki)⊕f(Ri-1,Ki),Ri-1)=(Li-1,Ri-1)=I

所以，Fi=Fi-1.

所以，Fi变换是对合运算。

（3）结合（1）（2），便构成了DES的轮运算：

Hi=FiT

因为(FiT)(TFi)=(Fi(TT)Fi)=FiFi=I,所以(FiT)-1=(TFi),(TFi)-1=(FiT)

（4）初始置换IP和逆初始置换IP-1是互逆的。

（5）加解密表示

① DES(M) = (M)IP(F1T)(F2T)...(F15T)(F16)IP-1 = C

② DES-1(C) = (C)IP(F16T)(F15T)...(F2T)(F1)IP-1 = M

故有DES-1DES(M) = (M)IP(F1T)(F2T)...(F15T)(F16)IP-1IP(F16T)(F15T)...(F2T)(F1)IP-1

= (M)IP(F1T)(F2T)...(F15T)(F16)(F16T)(F15T)...(F2T)(F1)IP-1

= (M)IP(F1T)(F2T)...(F14T)(F15)(F15T)(F14T)...(F2T)(F1)IP-1

= (M)IP(F1T)(F2T)...(F13T)(F14)(F14T)(F13T)...(F2T)(F1)IP-1

= ......

= (M)IP(F1T)(F2)(F2T)(F1)IP-1

= (M)IP(F1)(F1)IP-1

= (M)IP IP-1

= M

所以DES是可逆的。

② 对合性证明

DES = IP(F1T)(F2T)...(F15T)(F16)IP-1

DES-1 = IP(F16T)(F15T)...(F2T)(F1)IP-1

DES和DES-1除了子密钥的使用顺序相反之外是相同的。

不考虑子密钥的使用顺序，则有：

DES = IP(FT)(FT)...(FT)(F)IP-1

DES-1 = IP(FT)(FT)...(FT)(F)IP-1

显然 DES = DES-1

所以DES的运算是对合运算。

6.9 DES的破译

1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法。可对DES进行选择明文攻击。

线性密码分析（1993）比差分密码攻击更有效。

强力攻击：平均255次尝试（56位有效密钥位，256平均÷2=255）

差分密码分析法：使用247对明密文的选择明文攻击

线性密码分析法：使用247对明密文的已知明文攻击

6.10 DES的安全性

① 攻击：穷举攻击（目前最有效的方法）、差分攻击、线性攻击。

② 安全弱点：

密钥太短

存在弱密钥

存在互补对称性（设C=DES(M,K),则有~C=DES(~M,~K)）

- DES的弱密钥：

通过密钥扩展算法产生的16个子密钥出现重复：k1=k2=k3=...=k15=k16.

由密钥扩展算法，易知C、D两个寄存器如果取值“全0”或“全1”，则通过循环移位和置换选择2得到的子密钥总是重复的。

6.11 三重DES

在讲三重DES之前首先考虑一下双重DES。

用DES加密两次，每次使用不同的密钥。

但双重DES并不安全，双重DES存在中间相遇攻击。使它的强度跟一个56位DES的强度差不多。

若已知明文密文对(M,C)，攻击方法如下：

① 先用256个可能的K1加密M,得到256个可能的值，将这些值从小到大存入一个表中。

② 再对256个可能的K2解密C，每次做完解密，将所得到的值与表中的值比较，如果产生匹配，则它们对应的密钥可能是K1和K2。

③ 用一个新的明文密文对检测两个密钥，如果产生正确的密文，则它们是正确的密钥。

为了防止中间相遇攻击，采用三次加密方案。

（1）下面是使用两个密钥的三重DES（加密-解密-加密 E-D-E）方案

注意：加密与解密在安全性上来说是等价的。这种加密方案穷举攻击代价是2112.

（2）三把密钥的三重DES的（有效）密钥长度是168位，采用加密-解密-加密（E-D-E）方案

3DES的优点和缺点：

优点：

① 密钥长度是168位，足以抵抗穷举攻击；

② 3DES的底层加密算法与DES加密算法相同，该加密算法比任何其它加密算法收到分析的时间要长得多，也没有发现有比穷举攻击更有效的密码分析攻击方法。

缺点：

加解密速度慢，分组长度只有64位。

优势：

3密钥的3DES：密钥长度是168位。

2密钥的3DES：密钥长度是112位。

安全：密钥足够长，经过最充分的分析和实践检验。

兼容性好。

弱势：

速度慢。

6.12 DES的历史回顾

DES的贡献：

DES很好地体现了香农的密码设计理论；

DES体现了密码公开设计原则，开创了公开密码算法的先例；

DES代表当时商业密码的最高水平，是商用密码的典范；

DES对确保国际信息安全和提高国际密码设计水平都发挥了重要作用。

DES给我们的启示：

商用密码应当坚持公开设计原则；

商业密码标准应当公布算法。