密码学系列文(3)--分组密码-EW帮帮网

一、分组密码概述

分组密码是许多系统安全的一个重要组成部分，可用于构造：

拟随机数生成器
流密码
消息认证码(MAC)和杂凑函数
消息认证技术、数据完整性机构、实体认证协议以及单钥数字签字体制的核心组成部分

应用中对于分组密码的要求：

安全性
运行速度
存储量（程序的长度、数据分组长度、高速缓存大小）
实现平台（硬、软件、芯片）
运行模式

明文序列 $x_1,x_2,...,x_i,...$

加密函数 $E:V_n\times K\rightarrow V_n$

这种密码实质上是字长为 $m$ 的数字序列的代换密码;如图所示：

通常取 $n=m$ ；

若 $n>m$ ，则为有数据扩展的分组密码；

若 $n<m$ ，则为有数据压缩的分组密码；

分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密变换。

分组密码算法应满足的要求：

分组长度n要足够大：防止明文穷举攻击法奏效；
密钥量要足够大：尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效；
由密钥确定置换的算法要足够复杂：充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击；
加密和解密运算简单：易于软件和硬件高速实现；
数据扩展：一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展；
差错传播尽可能地小

1.1 代换网络

代换是输入集 $A$ 到输出 $A'$ 上的双射变换: $f_k:A\rightarrow A'$ 。式中， $k$ 是密钥。
实现代换 $f_k$ 的网络称作代换网络。双射条件保证在给定 $k$ 下可从密文唯一地恢复出原明文。
代换 $f_k$ 的集合： $S=\left \{ f_k|k\in K \right \}$ , $K$ 是密钥空间。如果网络可以实现所有可能的 $2^n!$ 个代换，则称其为全代换网络。全代换网络密钥个数必须满足条件： $\left \{ k \right \}\geq 2^n!$ .
密码设计中需要先定义代换集 $S$ ，而后还需定义解密变换集，即逆代换网络 $S^{-1}$ ，它以密文 $y$ 作为输入矢量，其输出为恢复的明文矢量 $x$
要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。实现密码体制的集合 $S$ 中的元素个数都远小于 $2^n!$

1.2 代换盒(S盒)

在密码设计中，可选 $n=r\cdot n_0$ ，其中 $r$ 和 $n_0$ 都为正整数，将设计 $n$ 个变量的代换网络化为设计 $r$ 个较小的子代换网络，而每个子代换网络只有 $n_0$ 个输入变量。称每个子代换网络为代换盒(Substitution Box)

$DES$ 的 $S_1$ 盒的输入和输出关系:

1.3 扩散和混淆

扩散将明文的统计特征散步到密文中。实现的方式是使明文的每一位影响密文中多位的值。
混淆是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。因此即使敌手能得到密文的一些统计关系，由于密钥和密文之间统计关系复杂化，敌手无法得到密钥。

扩散和混淆成功地实现了分组密码的本质属性，因而成为设计现代分组密码的基础。

S盒的设计准则实现较好的混淆：

S盒的输出都不是其输入的线性或仿射函数；
改变S盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化；
当S盒的任一输入位保持不变，其它5位输入变化时(共有 $2^5=32$ 种情况),输出数字中的0和1的总数近于相等；

S盒的组合（将几个S盒组合起来构成一个n值较大的组）：

将几个S盒的输入端并行，并通过坐标置换(P盒)将各S盒输出比特次序打乱，再送到下一级各S盒的输入端，起到了Shannon所谓的“扩散”作用。
S盒提供非线性变换，将来自上一级不同的S盒的输出进行混淆。经过P盒的扩散作用使1均匀分散到整个输出矢量中，从而保证了输出密文统计上的均匀性，这就是Shannon的乘积密码的作用。

1.4 Feistel网络

将n比特明文分成为左右各半，长为 $\frac{n}{2}$ 比特的段，以 $L$ 和 $R$ 表示。然后进行多轮迭代，其第 $i$ 轮迭代的输出为前轮输出的函数：

$L_i=R_{i-1}$
$R_i=L_{i-1}\bigoplus f(R_{i-1},K_i)$

式中， $K_i$ 是第 $i$ 轮用的子密钥， $f$ 是任意密码轮函数。称这种分组密码算法为Feistel网络，它保证加密和解密可采用同一算法实施。

1.5 迭代分组密码

若以一个简单函数 $f$ ，进行多次迭代，就称其为迭代密码

每次迭代称作一轮(Round)，相应函数 $f$ 称作轮函数

每一轮输出都是前一轮输出的函数，即 $y^{(i)}=f(y^{(i-1)},k^{(i)})$ ，其中 $k^{(i)}$ 是第 $i$ 轮迭代用的子密钥，由秘密密钥 $k$ 通过密钥生成算法产生；

二、分组密码运行模式

即使有了安全的分组密码算法，也需要采用适当的工作模式来隐蔽明文的统计特性、数据的格式等，以提高整体的安全性，降低删除、重放、插入和伪造成功的机会。

2.1 电码本模式(ECB)

直接利用加密算法分别对分组数据组加密
在给定的密钥下同一明文组总产生同样的密文组。这会暴露明文数据的格式和统计特征。明文数据都有固定的格式，需要以协议的形式定义，重要的数据常常在同一位置上出现，使密码分析者可以对其进行统计分析、重传和代换攻击。

2.2 密码分组链接模式(CBC)

每个明文组 $P_i$ 加密之前，先与反馈至输入端的前一组密文 $C_{i-1}$ 按位模2求和后，再送至加密算法加密
各密文组 $C_{i}$ 不仅与当前明文组 $P_i$ 有关，而且通过反馈作用还与以前的明文组 $P_1,P_2,...,P_{i-1}$ 有关。

初始矢量IV：第一组明文加密时尚无反馈密文，为此需要在寄存器中预置一个，收发双方必须选用同一个IV；
实际上，IV的完整性要比其保密性更为重要。在CBC模式下，最好是每发一个消息，都改变IV，比如将其值加1.

CBC的错误传播：

明文有一组中有错，会使以后的密文组都受影响，但经解密后的恢复结果，除原有误的一组外，其后各组明文都正确地恢复；
若在传送过程中，某组密文组 $C_i$ 出错时，则该组恢复的明文 $P_i'$ 和下一组恢复数据 $P_{i+1}'$ 出错。再后面的组将不会受 $C_i$ 中错误比特的影响

2.3 密码反馈模式(CFB)

对于k比特密码反馈模式

若待加密消息必须按字符或按比特处理时，可采用CFB模式
CFB实际上是将加密算法DES作为一个密钥流产生器，当k=1时就退化为流密码了

CFB的优点：

特别适合用户数据格式的需要
能隐蔽明文数据图样，也能检测出对手对于密文的篡改

CFB的缺点：

对信道错误较敏感，且会造成错误传播
CFB也需要一个初始矢量，并要和密钥同时进行更换

2.4 输出反馈模式(OFB)

将分组密码算法作为一个密钥流产生器，其输出的k比特密钥直接反馈至分组密码的输入端，同时这k比特密钥和输入的k比特明文段进行对应位模2相加；
克服了CBC和CFB的错误传播所带来的问题
对于密文被篡改难以进行检测

2.5 填充（Padding）

给定加密消息的长度是随机的，如果按64bit分组时，最后一组消息长度可能不足64bit。此时可以填充一些数字，通常用最后1字节作为填充指示符(PI)。它所表示的十进制数字就是填充占有的字节数。数据尾部、填充字符和填充指示符一起作为一组进行加密。

三、DES算法

虽然DES已有替代的数据加密标准算法，但是它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制；

分组长度为64 bits;
密文分组长度也是64 bits；
密钥长度为64 bits，有8 bits奇偶校验，有效密钥长度为56 bits；
算法主要包括：初始置换IP、16轮迭代的乘积变换、逆初始置换以及16个子密钥产生器；

DES算法框图如下所示：

3.1 初始置换IP

将64 bit明文的位置进行置换，得到一个乱序的64 bit明文组，而后分成左右两段，每段为32 bit

初始置换和逆初始置换在密码意义上作用不大，它们的作用在于打乱原来输入 $x$ 的ASCII码字划分的关系，并将原来明文的校验位 $x_8,x_{16},x_{32},x_{64}$ 变成为IP输出的一个字节

3.2 轮结构

DES算法的核心部分，将经过IP置换后的数据分成32 bit的左右两组，在迭代过程中彼此左右交换位置
每次迭代时只对右边的32 bit进行一系列的加密变换，在此轮迭代即将结束时，把左边的32 bit与右边得到的32 bit逐位模2相加，作为下一轮迭代时右边的段，并将原来右边未经过变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段
在每一轮迭代时，右边的段要经过选择拓展运算E、密钥加密运算、选择压缩运算S、置换运算P和左右混合运算

DES加密算法的轮结构：

3.3 DES的安全性

互补性：若明文组 $x$ 逐位取补，密钥 $k$ 逐位取补，即 $y=DES_k(x)$ ，则有 $\bar{y}=DES_k(\bar{x}))$ 。这种互补性会使DES在选择明文破译下所需的工作量减半;
弱密钥和半弱密钥：DES算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥 $k$ ，各轮的子密钥都相同，即有 $k_1=k_2=...=k_{16}$ 就称给定密钥为弱密钥;

若 $k$ 为弱密钥，则有 $DES_k(DES_k(x))=x$ ， $DES_k^{-1}(DES_k^{-1}(x))=x$

即以 $k$ 对 $x$ 加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。弱密钥下使DES在选择明文攻击下的搜索量减半。

如果随机地选择密钥，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及DES的安全性。

DES密钥太短：穷搜索对DES构成威胁

3.4 两重DES

用DES进行两次加密，不能意味着两重DES加密强度等价于112 bit密钥的密码的强度

中途相遇攻击法

由Diffie和Hellman最早提出，可以降低搜索量。其基本思想如下：

若有明文密文对 $(x_i,y_i)$ 满足 $y_i=E_{k_2}[E_{k_1}(x_i)]$ 则可得 $z=E_{k_1}(x_i)=D_{k_2}(y_i)$

给定一已知明密文对 $(x_1,y_1)$ ，可按下述方法攻击:

以密钥 $k_1$ 的所有 $2^{56}$ 个可能的取值对此明文 $x_1$ 加密，并将密文 $z$ 存储在一个表中;
从所有可能的 $2^{56}$ 个密钥 $k_2$ 中依任意次序选出一个对给定的密文 $y_1$ 解密，并将每次解密结果 $z$ 在上述表中查找相匹配的值。一旦找到，则可确定出两个密钥 $k_1$ 和 $k_2$ ；
以此对密钥 $k_1$ 和 $k_2$ 对另一已知明密文对 $(x_2,y_2)$ 中的明文 $x_2$ 进行加密，如果能得出相应的密文 $y_2$ 就可确定 $k_1$ 和 $k_2$ 是所要找的密钥

分析知道：

对于给定明文 $x$ ，以两重DES加密将有 $2^{64}$ 个可能的密文
可能的密钥数为 $2^{112}$ 。所以，在给定明文下，将有 $2^{112}/2^{64}=2^{48}$ 个密钥能产生给定的密文
用另一对64 bits明文密文对进行检验，就使虚报率降为 $2^{48-64}=2^{-16}$
这一攻击法所需要的存储量为 $2^{56}\times 8$ 字节，最大试验的加密次数 $2\times2^{56}$ 。这说明破译双重DES的难度为 $2^{57}$ 量级；

3.5 三重DES加密

加密： $y=E_{k_1}[D_{k_2}[E_{k_1}(x)]]$
解密： $x=D_{k_1}[E_{k_2}[D_{k_1}(y)]]$

破译它的穷举密钥搜索量为 $2^{112}\approx 5\times 10^{35}$ 量级，而用差分分析破译也要超过 $10^{52}$ 量级。此方案仍有足够的安全性；

四、分组密码的分析

4.1 差分密码分析

差分密码分析是一种攻击迭代分组密码的选择明文统计分析破译法；
它不是直接分析密文或密钥的统计相关性，而是分析明文差分和密文差分之间的统计相关性;
给定一个 $r$ 轮迭代密码，对已知 $n$ 长明文对 $X$ 和 $X'$ ，定义其差分为： $\Delta X=X\bigotimes (X')^{-1}$ 。其中， $\bigotimes$ 表示n bits组 $X$ 的集合中定义的群运算， $(X')^{-1}$ 为 $X'$ 在群中的逆元。
在密钥作用下，各轮迭代所产生的中间密文差分为 $\Delta Y(i)=Y(i)\bigotimes Y'(i)^{-1},0\leq i\leq r$
$i=0$ 时， $Y(0)=X,Y'(0)=X',\Delta Y(0)=\Delta X$
$i=r$ 时， $\Delta Y=\Delta Y(r)$ , $k^{(i)}$ 是第 $i$ 轮加密的子密钥， $Y(i)=f(Y(i-1),k^{(i)})$
由于 $X\neq X'$ ,因此， $\Delta Y(i)\neq e$ (单位元)
每轮迭代所用子密钥 $k^{(i)}$ 与明文统计独立，且可认为服从均匀分布；

如图所示为 $r$ 轮迭代分组密码的差分序列：

Lai等引入Markov链描述多轮迭代分组密码的差分序列。并定义了Markov密码
Lai等证明，Markov密码的差分序列 $\Delta X= \Delta Y(0), \Delta Y(1),..., \Delta Y(r)$ 是一齐次Markov链，且若 $\Delta X$ 在群的非零元素上均匀分布，则此Markov链是平稳的；
不少迭代分组密码可归结为Markov密码；
一个Markov型密码，可以用转移概率 $P(\Delta Y(1)=\alpha _j | \Delta X=\alpha _i)$ 的所有可能转移值构成的矩阵描述，称其为齐次Markov链的转移概率矩阵，以 $\Omega$ 表示；
一个n bits分组密码有 $1\geq i,j\leq M=2^n-1$ 。对所有 $r$ ，有 $\Omega^{r}=P_{ij}^{(r)}=P(\Delta Y(r)=\alpha_j |\Delta X=\alpha_i )$ , $\Omega$ 的每一行都是一概率分布，行元素之和为1；
对于Markov型密码，当 $\Delta X$ 在非零元素上为均匀分布，则 $\Delta Y$ 为一平稳Markov链，此时对于每个 $j$ 有即各列元素之和也为1，从而可1知各列也构成一概率分布；
差分密码分析揭示出，迭代密码中的一个轮迭代函数 $f$ ，若已知三元组 $\left \{ \Delta Y(i-1),Y(i),Y'(i) |Y(i)=f(Y(i-1),k^{(i)}),Y'(i)=f(Y'(i-1),k^{(i)} \right \}$ ,则不难决定该轮密钥 $k^{(i)}$ ;
因此轮函数 $f$ 的密码强度不高。如果已知密文对，且有办法得到上一轮输入对的差分，则一般可决定出上一轮的子密钥(或其主要部分)；
在差分密码分析中，通常选择一对具有特定差分 $\alpha$ 的明文，它使最后一轮输入对的差值 $\Delta Y(r-1)$ 为特定值 $\beta$ 的概率很高；