密码学专题| 四、实际分组密码 —— DES 和 AES

实际密码方案与实际安全

分组密码加密方案假设了分组代换-置换是一种伪随机函数，这是一个非常典型的安全假设。另一个 RSA 算法假设大数分解是困难。这些假设的引入，使得加密方案的安全性不再等于计算安全。

如果假设成立，分组代换-置换是一种伪随机函数，那么可以证明这种加密方案是满足计算安全假设的。然而，如果分组置换并不满足伪随机函数的定义，此时基于分组代换-置换的分组密码就无法达到了计算安全假设了。RSA 的例子也是如此，我们都假设大数分解难题是一个 NP 问题，因此一个线性多项式时间的敌手攻破 RSA 算法的可能性很低。但是如果 N=NP，此时 RSA 算法就不再是安全的了。

我们称这样一种基于长期认为可靠、或者是有大量理论认为成立的假设的安全为实际安全。通常，这时候，我们认为这些加密方案在一个非常可靠的时间内是安全的（比如十年或者一百年）。

代换-置换网络是分组密码的基本结构

将 n 个数随机置换，有约 \(n*2^n\) 种可能性。分组置换中，分组大小 n 应当充分的大，分组密码的安全性和 n 的大小直接相关。就目前来说 128 bit 几乎是最低标准， 256 bit 和 512 bit 的分组将变得更加流行。

一个分组置换网络通常具有许多轮，比较典型的数字是 16 轮及以上。每一轮中，子秘钥将和明文进行混合，通过被称为 “S盒” 的固定置换函数，并进行位置代换。

注意到此时 “S 盒” 是一个一一映射的函数，也就是说这种置换是可逆的。此时可以发现这种映射可以说是线性的，那么还需要位置轮换，进行非线性映射。

通常，在这种网络中，需要充分利用雪崩效应，也就是单个 bit 的改变也应当影响其他尽可能多的 bit 。这要求算法设计满足下面一些条件： S 盒的设计，使得单个 bit 输入的差值可以输出在尽可能多的位数上；单个 S 盒的改变，应当进入下一轮多个 S 盒中；尽可能增加分组置换的轮数。

DES 算法族和 Feistel 网络

Feistel 网络

这种网络是一个可逆的分组置换网络，其具有基本的变换形式如下：将第 i 轮输入分为左侧输入 \(L_i\) 和右侧属于 \(R_i\)。还有一个和子秘钥 \(k_i\) 相关的不可逆函数 \(f_i\)。那么： \[L_i = R_{i-1}, R_i = L_{i-1} \bigotimes f_i(k_i, R_{i-1}) \]

可以证明即便是使用了不可逆函数 fi, 但是网络整体是可逆的。

DES 加密标准

DES 是一种基于 Feistel 网络的加密标准，使用 64 bit 秘钥（实际 56 bit），目前由于分组长度不足，导致安全性已经被攻破了，因此已经不再使用了，取而代之的是 AES 以及 3DES。

DES 算法由 16 轮 Feistel 置换构成，每轮分组长度 64 bit，秘钥长度 56 bit。f 的选取输入和输出均为 32 bit，在 f 中扩展为 48 bit，有 8 个进行挑选的 S 盒。

双重 DES 加密和中间相遇攻击

使用双重 DES 加密使用了两个 56 bit 秘钥，因此秘钥空间是 \(2^{112}\)。

设 E(k,m) 表示 DES 加密算法，而 D(k,c) 表示 DES 解密算法，则双重 DES 加密描述如下： \(c = E(k_2, E(k_1, m) )\)

此时存在中间相遇攻击，使得攻击复杂和 DES 相同，即 \(2^{56}\)。假设敌手 A 拥有一对明文密文对 m,c :

1. 使用 i 表示指标，遍历 k 的秘钥空间。计算中间结果 \(z_1^i = E(k_1^i, m)\) 并存表 \( (z_1^i, k_1^i) \)
2. 使用 j 表示指标，遍历 k 的秘钥空间。计算中间结果 \(z_2^j = D(k_2^j, c)\) 并存表 \( (z_2^j, k_2^j) \)
3. 对中间结果进行排序并比对，找出 \( z_1^i = z_2^j \)。此时 \( k_1^i \) 和 \(k_2^j \) 就是秘钥。

3DES

为了对抗中间相遇攻击，因此提出了 3DES 算法，作为 AES 算法的过度算法。但是由于其进行了三次 DES 操作，因此加密解密开销较大。 3DES 的形式如下： \[ c = E(k_3, D(k_2, E(k_1, m)) \]

有两点值得说明：

1. 有时候 k3 和 k1 使用同一个秘钥，此时总秘钥长度是 128 bit （实际 112 bit）
2. 使用 EDE 的方案使得加密和解密使用了同样的过程，而无需单独编程。

高级加密标准 AES

AES 算法使用了 AES 置换网络结构，而不是 Feistel 结构。 AES 算法使用 128 bit 分组长度。秘钥长度有 128 bit，192bit 和 256 bit，分别对应 10, 12 和 14 轮变换。每一轮变换有加秘钥、字节代换、行位移和列混合四个步骤。

分组密码的攻击

1. 差分攻击

差分攻击是一种选择明文攻击。此时构建了输入的查分 \(\Delta_m\)，并在随机秘钥k 的情形下，统计输出的差分 \(\Delta_c\)的 p 。如果分组置换网络设计合理，并与伪随机函数无法区分，那么输出的概率 p 应接近 \( 2^{-n}\)。如果偏离了这样的分布，那么这种分组置换网络则是不安全的。

2. 线性攻击

线性攻击是一种已知明文攻击。此时假定比特位 \( i_1,i_2 … i_l \) 和 \( i_1’,i_2’ … i_l’ \) 有偏移。那么：

\[ Pr[m_{i_1} \bigotimes … \bigotimes m_{i_l} \bigotimes c_{i_1’} \bigotimes … \bigotimes c_{i_l’} = 0] = p \]

如果分组置换网络设计合理，并与伪随机函数无法区分，那么输出的概率 p 应接近 \( \frac{1}{2} \)。如果偏离了这样的分布，那么这种分组置换网络则是不安全的。