【密码学】（一）分组密码和DES

1. 一、分组密码概述
2. 二、Feistel密码体制
3. 三、数据加密标准（DES）

本文转载自：《现代密码学》课程笔记知乎专栏
仅作个人学习记录。

上一讲主要讲了复杂度理论的知识，总结如下：

图4-1 第三讲总结

这一讲正式进入现代密码学。先引入分组密码的概念，然后讲解数据加密标准（DES）。

一、分组密码概述

首先说明分组密码和流密码的概念和区别。

1.分组密码和流密码的概念与区别：

所谓流密码，就是把明文的所有字符作为一个整体，然后一位一位地对明文字符进行加密。先前讲的一些古典密码，如维吉尼亚密码和Vernam密码，都属于流密码。先前讲一次一密时有一个典型的式子：；这个实际就是指：一位明文被一位密钥加密为一位密文。这就是流密码最显著的特点。

至于分组密码，就是指先对明文进行分组，然后对分组后的明文一组一组地进行加密。分组加密后的密文分组长度与明文分组长度相等。它与流密码的区别是，分组密码一次用一个密钥加密一组明文，而不是一位一位加密。

如下图所示：

图4-2 分组密码示意图

2.理想的分组密码：

（1）分组密码的可逆映射：

分组密码具有这样的特点：一个位长的明文分组，一定对应着唯一一个位的密文分组。同样，一个位的密文分组一定也唯一对应着一个位的明文分组（否则加解密不互逆）。这样的明文分组与密文分组之间的一一映射称为可逆映射。而所有可能的明文分组与对应的密文分组组成的表称为一个可逆映射表，如下图所示：

图4-3 一个分组密码的可逆映射表

（2）分组密码变换的总数：

在长度为的分组中，一个可能的可逆映射表中含有的映射对有个（因为长为位的明文组可以有种，如2位的明文分组有00,01,10,11四种）。

而第一种明文（如00）也可以对应其他4种密文（如00,01,10,11），第二种明文（如01）可以对应剩下的3种密文，以此类推，因此，所有可能的映射表种数为。

由此可以得出，一个长度为位的分组，其明密文可逆映射表有种。

（3）理想分组密码的密钥：

对于一个长度为位的分组，其明文组和密文组对应的映射本身就是密钥。如下图（一个分组长度为4的一种可能的映射表）：

图4-4 长度为4的一种映射表

本质上，右边一列（111001001101……）就是密钥。因此，对于一个分组长度为的明文，其密钥长度为。

（4）理想分组密码遇到的困难和改进：

因为对于一个理想的分组密码，其密钥长度为。而分组密码的分组长度还不能太小，因为分组长度太小会导致密码容易被攻破。但是当分组长度太大时，密钥会非常长：当时，。这造成了密钥共享的困难。考虑到这些困难，Feistel提出，我们只是需要使用一种不太理想的分组密码，用来逼近理想分组密码即可。

二、Feistel密码体制

1.分组密码的设计原则：

既然理想分组密码不太实用，那么我们可以从密码设计的本源进行探索，一个足够安全的密码系统具有什么特征？

香农引进了混淆和扩散两个概念。

（1）扩散：

所谓扩散，就是==使明文和密文之间的关系尽可能复杂==，使明文中原有的统计规律在密文中消失。即无法通过密文来获知有关明文的任何信息。可以通过让明文中的多个位对密文的一位造成影响，从而造成扩散（这也是命名为扩散的原因）。实际中，可以对明文进行置换，然后使用多个函数多次对其作用，就能产生这样的效果。（见下文的Feistel密码）

（2）混淆

混淆是指==使密文和密钥之间的关系尽可能复杂==，即无法通过密文来推断出密钥。

扩散和混淆简明扼要地抓住了现代分组密码设计的最核心的本质。

2.乘积密码体制：

所谓乘积密码体制，就是依次使用两个或者两个以上的密码，从而达到扩散和混淆的效果。这里Feistel建议多次使用古典密码中的两个重要方法：代替和置换。这种密码体制本质上密钥长度为位，每一种密钥可以产生一个唯一的可逆映射表（前文提到的），因此可以产生的可逆映射表数量为，小于理想分组密码的可逆映射表数。这种密码体制是向理想分组密码体制的一种逼近。

3.Feistel密码体制的描述：

一个Feistel密码体制包含16轮迭代和一次左右置换。如下图所示：

图4-5 Feistel密码体制示意图

（1）Feistel密码体制的加密过程：

在加密时，首先将明文分为左右等长的两部分，分别记为 $L{i-1} $和$ R{i-1} $。然后使用轮函数$ F $对$ R{i-1} $进行作用，其结果再与$ L{i-1} $进行异或运算，形成的结果成为下一轮的$ Ri $。同时，直接将右边的$ R{i-1} $挪到下一轮$ Li $的位置上（请结合图进行理解）。每一轮的输出都作为下一轮的输入，以此类推，一直进行轮迭代。在迭代的最后，左右交换$ L{16} $和$ R_{16}$，形成最终的密文。

注意：每一轮输入轮函数的密钥，是由整个密钥推出的，在DES中有专门的密钥扩展算法（之后会讲）。

（2）Feistel密码体制的解密过程：

解密过程与加密过程完全相同。

我们先来证明轮变换的可逆性：

对于一个轮变换：假设以 $L{\text{入}} $和$ R{\text{入}} $作为输入，$ L{\text{出}} $和$ R{\text{出}} $作为输出，轮密钥为$ k $，轮函数表示为$ F(k,R{\text{入}}) $。则有这样两个关系：$ R{\text{出}}=L{\text{入}}\oplus F(k,R{\text{入}}) $（等式），$ L{\text{出}}=R{\text{入}} $（等式）。对等式左右两边同时$ \oplus F(k,R{\text{入}}) $，有$ R{\text{出}}\oplus F(k,R{\text{入}})=L{\text{入}} $，把等式代入，有$ L{\text{入}}=R{\text{出}}\oplus F(k,L{\text{出}}) $（等式），同时由等式还有$ R{\text{入}}=L_{\text{出}}$（等式4）。

以上可以看出，等式1、等式2是正向变换，等式3和等式4是逆向变换。其变换过程是相同的，也是等价的，这也说明每次轮变换（迭代）都是可逆的。注意：这里并没有要求轮函数可逆，轮函数是否可逆不会影响整个轮变换的可逆性。由于每个轮迭代都是可逆的，所以整个16轮迭代的输入输出都是可逆的。在解密时，只需将加密得到的密文输入，然后倒着使用加密过程的16轮轮迭代即可。（密钥也要对应倒着使用，见图4-5）

由于在加密变换的16轮变换结束之后，左右两部分进行了一次置换，即解密过程的输入是最后一轮迭代的结果再左右交换。因此对每一轮解密变换都有 $LDi=RE{16-i} $，$ RDi=LE{16-i}$，即加密每一轮的输出都是解密每一轮的输入再左右交换，加密每一轮的输入都是解密每一轮的输出再左右交换。（见图4-5）

在执行16轮迭代之后，由于解密输出的左右两部分还与加密过程的输入相反，因此还需执行一次左右置换，从而得到明文。

三、数据加密标准（DES）

DES（Data Encryption Standard）是1977年美国国家标准局颁布的信息处理标准，多年来，DES是主流的对称加密算法。但现在DES已经不太安全了。DES主要采用了Feistel加密体制，是一种分组密码加密体制。

DES有两个输入，分别是分组长度为64位的明文，和长度为56位的密钥（实际为64位，剩下的8位可以作为奇偶校验码或随意设置）。

其加密过程如下，首先对64位明文进行初始置换，然后进行16轮的轮迭代（与Feistel密码体制完全相同），最后再进行一次逆初始置换，得到密文。每轮的密钥由一个专门的算法产生。

图4-6 DES加密过程

1.初始置换和逆初始置换：

初始置换（Initial Permutation, ）和逆初始置换（）是位于DES开始和结尾的两个置换。输入两个置换表的输入都是64位，输出的结果也是64位，具体置换规则是，将64位输入从1到64编号，然后按照表中的数字，将对应的编号放到相应的位置上，即完成置换。初始置换表和逆初始置换表是互逆的，即满足。两个表如下图所示：

图4-7 初始置换表

图4-8 逆初始置换

2.轮变换（轮迭代）的细节过程：

明文经过初始置换后，就进入了16轮轮迭代的过程。每轮迭代如图4-9左侧所示。（右侧为轮密钥产生方法）。

与前面所讲的Feistel密码体制一样，经过初始置换的64位明文，被分成了左右32位：和，然后经历下面的变换：

其中为32位，参与轮函数的密钥为48位（之后会讲密钥产生方法）。

图4-9 轮迭代的详细过程

其中轮函数包含这么几个过程：进入轮函数中的32位的首先要经过一个扩展置换，被扩展为48位，置换规则与初始置换相同，如图4-10所示。

图4-10 拓展置换(E)表

其后，被扩展出的48位与密钥进行按位异或，得出48位的结果。

之后，这48位将进入一个代替函数，产生出32位的输出。

这个代替函数由8个S盒组成。首先将48位的输入分成8部分，每部分6位，分别把分出的8个部分输入到8个S盒中。在每个S盒中，这6位输入的第1位和第6位组成的2位二进制数用来选择S盒的某一行，中间4位组成的二进制数用来选择S盒的某一列。行列确定后，会选出S盒中的一个十进制数字，然后把这个十进制数转换为4位二进制数，作为这个S盒输出的结果。这样，每个S盒都可以把6位输入转换为4位二进制输出。8个S盒同时作用，就完成了48位到32位的转换。

8个S盒如下图所示：