数据加密标准DES是迄今为止世界上使用最广泛的分组加密算法
直到2001年高级加密标准AES的提出，DES才逐渐被取代

DES原理

总体结构

如图所示，DES基于Feistel结构
其中分组大小为64位，密钥大小为56位，子密钥$K_i$为48位，迭代轮数为16次
在Feistel结构之前和之后分别经过一次置换和逆置换

与Feistel一样，DES解密过程与加密过程完全相同，只是密钥和初始置换逆序使用

des_structure

密钥产生算法

56位密钥K首先经过置换1，之后分为等分为左右两份$C,D$，分别为28位
每轮子密钥产生中，先将$C,D$分别循环左移1位，将$C,D$拼接起来经过置换2并从中选择48位即为子密钥
注意传入下一轮的$C,D$是没有经过置换2的

des_K

迭代结构

如图所示，DES的迭代结构与Feistel一致，均表示为

其中轮函数F首先根据扩展表E扩展为48bit，然后与子密钥异或
之后经过S盒和P盒分别完成混淆和扩散

des_f

扩展表E

如图所示，扩展表E实质上是将32bit中的某16bit各复制一次，再进行一个简单置换

des_expand

S盒

S盒由8个4×16的子表组成，如图所示为一个示例

S盒的输入为48bit，输出为32bit，其中输入每6bit分为一组，共8组，分别对应了S盒8个子表

对于第$i$个组，取其中第1和第6个bit位组成一个2bit二进制数，作为查找的行号，取中间4bit作为查找的列号，在子表$S_i$中按上述行列号查找到对应的十进制数，转换为4bit二进制数后输出

des_s

P盒

如图所示，P盒是一个精心构造的置换函数
P盒使得该轮同一个S盒子表输出的4bit，在下一轮迭代由四个不同的S盒子表处理

des_p

对DES的穷举攻击

虽然DES密钥空间大小为$2^{56}$，但实际上对DES的穷举攻击搜索空间大小为$2^{56}/2=2^{55}$

这个结论基于DES的一个性值：若$Y=DES(K,X)$，则$\overline{Y}=DES(\overline{K},\overline{X})$

这一点用数学归纳很容易证明
令$S(x),P(x)$分别表示S盒与P盒，则轮函数$F(R,K)=P(S(R\oplus K))=P(S(\overline{R}\oplus \overline{K}))=F(\overline{R},\overline{K})$

对于第一轮加密有

$Y_1=(R_0,R_0\oplus F(R_0, K_1))\\overline{Y_1}=(\overline{R_0},\overline{R_0\oplus F(R_0, K_1)})=(\overline{R_0},\overline{R_0}\oplus F(\overline{R_0}, \overline{K_1}))$

假设命题对第n轮加密成立，则对于第n+1轮加密有

$Y{n+1}=(R_n,R_n\oplus F(R_n, K{n+1}))\\overline{Y{n+1}}=(\overline{R_n},\overline{R_n\oplus F(R_n, K{n+1})})=(\overline{Rn},\overline{R_n}\oplus F(\overline{R_n}, \overline{K{n+1}}))$

综上由数学归纳法可知命题对任意$n>0$加密轮数的DES均成立

基于这个结论，假设攻击者有明密文对$(X,Y)$，若$DES(K,X)\neq Y$且$DES(K,\overline{X})\neq \overline{Y}$，则$K,\overline{K}$均不是密钥，即搜索空间减半

双重DES

在现代计算机硬件的支持下，DES面对穷举攻击相对比较脆弱，因为DES的密钥空间大小只有$2^{56}$，使用超级计算机进行穷举破解只需约一小时

抵御穷举攻击可以通过增大密钥或多重加密来实现

多重加密的最简单形式就是双重加密
给定明文$P$和密钥$K_1,K_2$，则密文$C=E(K_2,E(K_1,P))$，相应的解密为$P=D(K_1,D(K_2,C))$

多重加密必须仔细分析是否能约化为单次加密
也即分析是否存在密钥$K_3$使得$E(K_2,E(K_1,P))=E(K_3,P)$，若存在则多重加密显然是无用的

对于DES来说，双重加密是不能被约化为单次加密的

中途相遇攻击

中途相遇攻击是一种攻击任意双重加密的分组密码的方法

对于双重加密的分组密码，显然有$X=E(K_1,P)=D(K_2,C)$
给定明密文对$(P,C)$，首先使用所有可能的密钥$K_1$对$P$加密，存下得到的$2^{56}$个$X$及其对应的$K_1$
然后枚举所有可能的密钥$K_2$对$C$解密，如果解密结果与存下来的$X$有相同的，就用相应的$K_1,K_2$测试另一对明密文对$(P’,C’)$，若测试通过则表明找到了正确密钥

以双重DES为例，因为其密文空间为$2^{64}$，密钥空间为$2^{112}$，因此有约$2^{112-64}=2^{48}$对$K_1,K_2$能通过第一个明密文对的测试，而第二对明密文出错的概率就降为$2^{48-64}=2^{-16}$

中途相遇攻击对双重DES的计算量为$2^{56}$数量级，与单重DES加密相当

两个密钥的三重DES

应对中途相遇攻击最简单方法就是三个密钥三重加密
因为需要为2个密钥的组合构建表格，所以中途相遇攻击的计算量变成了$2^{112}$

然而三个密钥总大小增大到了168位，实际上使用两个密钥的三重DES就足够了，其公式如下

当$K_1=K_2$时，该公式其实就是单重DES加密

目前为止还没有对3DES的可行攻击方法