《现代密码学》分组密码笔记

前几周密码学课要么在写软工，要么在跑实验，这个模块算是完全需要从头学习了，现在就坐在教室第一排看几周前的课件的样子，希望一天能补完吧（（（

分组密码

分组密码简介

古典密码学：置换密码与代换密码

置换密码根据一定的规则重新排列明文，以便打破明文的结构特性。置换密码的特点是保持明文的所有字符不变，只是利用置换打乱了明文字符的位置和次序。

代换密码就是将明文中的一个字母由其它字母、数字或符号替代的一种方法。我们需要建立一个代换表，加密时将需要加密的明文依次通过查表，替换为相应的字符，明文字符被逐个替换后，生成无任何意义的字符串，即密文。这样的代换表，通常称为密钥。

古典的代换密码的代换表太小，仅有 26 个字母，不能够抵抗唯密文攻击和已知明文攻击。而“分组密码”可以看成是一个巨大的“代换密码”，其中 DES 可认为有 $2^{64}$ 个元素的代换表，AES 有 $2^{128}$ 个元素的代换表。

但是，这个代换表中的每个元素只被计算一次，这是为了避免将这个巨大的表给存储下来。我们要解决的问题就是，该如何去计算每个分块代换后的元素。

分组密码是这样一种算法，它将 $n$ Bit 的明文分组加密成 $n$ Bit 的密文，其中分组长度 DES $n=64$，AES $n=128$. 其密钥长度 DES $|K| = 56$，AES $|K| = 128, 192, 256$.

我们可以用以下图片来描述分组密码的工作模式。

其加密 $C=E_K(P)$，解密 $P=E_K^{-1}(C)$.

那么这个加密/解密算法 $E$ 该如何设计呢？一般来说，我们采用一种基于轮函数的迭代结构（也称为乘积密码），再辅以一定的密钥生成方案：

轮函数

其中每一个 Round，轮函数均接受上一阶段加密后的文本和本阶段使用的密钥作为输入，经过计算输出其本阶段加密结果。

轮函数应有以下设计策略：

• 混淆：非线性部件
  • 小的代换表 S-box
  • 乘法与异或
  • 加与异或
• 扩散：让所有的 Bit 互相影响
  • 线性变换
  • 置换
  • 移位、循环移位

密钥方案

密钥生成方案（Key Schedule）有多种方法，但目前为止没有完美的方法 。其基本准则：密钥的每个比特应该影响不同位置的很多轮的轮子密钥。

设计方案

下面介绍一些设计轮函数的方案。

Feistel Network

Feistel Network 由 DES 的设计者之一，Horst Feistel 所发明，该结构被广泛使用，AES 最终的 5 个候选算法之中，有 3 个使用了这种 Feistel 网络架构。

这种网络架构具有以下属性：

• 可逆性：$L_i = R_{i-1}, R_i = L_{i-1} \oplus F(K_i, L_i)$.
• 加解密使用同一套逻辑，只不过密钥的使用顺序相反。

在使用时我们需要定义满足上述条件的函数 $F$.

SPN（Substitution-permutation Network）

这种结构被 AES（rijndael）算法所最终采用。其基本架构为：

其架构有 S 盒和 P 盒两个需要我们定义的内容。

S 盒属性：

• 改变输入的 1 比特，输出比特中有一半的比特改变
• 输出的每一个比特依赖输入的所有比特

P 盒属性：

• 好的 P 置换是使得 S 盒的输出比特分布到下一轮的尽可能多的 S 盒

[混淆] 是指让密文和密钥之间的统计关系变得复杂，使得敌手不能通过密文的统计关系，推测出密钥的统计关系。（非线性替换）

[扩散] 扩散就是让明文中的每一位影响密文中的许多位，或者说让密文中的每一位受明文中的许多位的影响．这样可以隐蔽明文的统计特性。

DES

DES 是一种分组加密算法，其消息分组大小为 64 Bit，密钥长度为 56 Bit，另加 8 个冗余 Bit 用于奇偶校验。其采用 Feistel 结构，迭代经过 16 轮轮函数，再经过起始置换与末置换。

起始置换与末置换

F 函数

F 函数中的扩展盒 E

F 函数中的 S-box

使用 8 个 S 盒 $S_1, S_2,\cdots, S_8$，每一个 S 盒: $\{0,1\}^6 \rightarrow \{0,1\}^4$。

可以用 $4 \times 16$ 的矩阵描述。

如：

S1 = {
    14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
    0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
    4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
    15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
};

给定输入 $b_1b_2b_3b_4b_5b_6$，我们将 $b_1b_6$ 作为行索引，$b_2b_3b_4b_5$ 作为列索引，取出矩阵中对应项的二进制表示作为 S-box 的输出。

P 置换

DES 密钥生成方案

64 Bit 的密钥中有 8 位是校验位，我们将其余 56 位经过一个 56 位的置换 PC1，将其分成左右两个 28 位的密钥输入 <<<（代表循环左移）。

当 $i \in \{1,2,9,16\}$ 时，循环左移移位数为 1 位，其他情况移位数为 2 位。PC2 算法是一个从 56 位中选取 48 个有效位的算法。

多重加密

在今天的计算能力下，DES（56 Bit）已不再安全。于是，我们需要增加密钥长度。多重加密便是增加密钥长度的一种实践方式。

• Double-DES 密钥长度 112 Bit
  • $C = E_{K_2}(E_{K_1}(P))$
  • 把密钥拆成两个 56 Bit，过两次不同 Key 的 DES？
  • 不能够抵挡中间相遇攻击…

[中间相遇攻击]

令集合 $I = \{ E_{K_1}(P)\}$，$J=D_{K_2}(C)$，112 Bit 长度的密钥构造出的 $I, J$ 必是相等的！暴力枚举所有的 I 和 J，即 $O(2^{56} + 2^{56})$！

• Triple-DES 密钥长度 168 Bit
  • 加密：$C=E_{K_3}(D_{K_2}(E_{K_1}(P)))$
  • 解密：$C=D_{K_1}(E_{K_2}(D_{K_3}(P)))$
  • 密钥选择
    • 3-key: $K_i$ 相互独立，168 Bit.
    • 2-key：$K_1 = K_2, K_3=K_1$，112 Bit.

AES

AES 是一种分组密码，其分组长度为 128 Bit，采用 SPN 架构，具有三种不同长度的密钥和轮数：

• AES-128：10 轮
• AES-192：12 轮
• AES-256：14 轮

[复习] SPN 结构

以下介绍 AES 的结构。

轮函数

每一轮仅需要经过字节替换、行移位、列混合、与密钥异或的过程。

其总体流程：

字节替换 SubBytes

S-box：8 Bit 输入，8 Bit 输出，可逆

由以下两个步骤计算出 $b’ = S(a)$.

• 在 $GF(2^8)$ 中求 $b = a^{-1}$. （扩展 Euclid）
• 对 $b$ 应用以下仿射变换，这是为了防止 $\vec0$ 映射成 $\vec0$ 的情况.

$$\left[\begin{array}{l} b_{0}^{\prime} \\ b_{1}^{\prime} \\ b_{2}^{\prime} \\ b_{3}^{\prime} \\ b_{4}^{\prime} \\ b_{5}^{\prime} \\ b_{6}^{\prime} \\ b_{7}^{\prime} \end{array}\right]=\left[\begin{array}{llllllll} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{array}\right]\left[\begin{array}{l} b_{0} \\ b_{1} \\ b_{2} \\ b_{3} \\ b_{4} \\ b_{5} \\ b_{6} \\ b_{7} \end{array}\right]+\left[\begin{array}{l} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{array}\right]$$

行移位 ShiftRows

第 $i$ 行进行循环左移 $i$ 位，这里 $1 \le i \le 4$.

列混合 MixColumns

密钥加 AddRoundKey

• 每个轮密钥为 128 Bit.

密钥生成算法

AES 解密

解密因为对列混合求逆时间消耗较大，于是效率慢于加密。

在这里我们强烈建议读者补全 $GF(2^8)$ 上的加法运算与乘法运算的相关概念。

求逆时，AES 采用的不可约多项式为 $x^8+x^4+x^3+x+1$.

分组密码工作模式

上述提到的 AES 只能加密固定位数的消息，而在实际中面对长文本时的使用模式便称为分组密码的工作模式。

电子密码本模式 ECB

是将明文的 $N$ 个分组独立地使用同一密钥 $K$ 加密和解密。

不同明文分组之间的加密独立进行，故保留了单表代替缺点，造成相同明文分组对应相同密文分组，因而不能隐藏明文分组的统计规律和结构规律。

密码分组链接模式 CBC

想法：使输出不仅与当前输入有关，而且与以前输入和输出有关。

CBC 模式中每个明文分组在加密之前都要与以前的密文分组进行异或。第一个分组之前没有密文，故要用到一个伪分组 IV。

• IV 不要求保密
• IV 必须是不可预测的，而且要保证完整性

密码反馈模式 CFB

输出反馈模式 OFB

计数器模式 CTR

工作模式分析

• Padding Oracle Attack：基于填充格式的攻击

分组密码分析

重温：分组密码分析的攻击类型

• 唯密文攻击：仅有当前密钥下截获的密文
• 已知明文攻击：仅知道当前密钥下的明密文对
• [CPA] 选择明文攻击：能够获得当前密钥下的一些特定的明文所对应的密文
• [X, CCA] 选择密文攻击：能够获得当前密钥下的一些特定的密文所对应的明文

重温：攻击复杂度

• 时间复杂度
• 空间复杂度
• 数据复杂度：要 截获/Query 的数据数量

通用密码分析过程

• 穷举密钥搜索攻击：唯密文攻击、已知明文攻击。
• 字典攻击：建立密文->明文的映射字典
• 查表攻击：给定明文 $x$，对于 $2^k$ 个密钥 $K$，打表 $\{(E_K(x), K)\}$.
• 时间存储折中攻击（TMTo）：对固定的明文 $P$ 和某个密文 $C_0$，已知加密算法 $S$，目标恢复加密过程中使用的密钥 $K_0$.

• 其改进方向：Rainbow 表（彩虹表）

差分分析

给定加密算法，比较两个明文的异或与相应的两个密文的异或的概率分布情况。

记 $P_1 \oplus P_2 = \Delta P, C_1 \oplus C_2 = \Delta C$，任给 $X = \Delta P, Y = \Delta C$，研究差分 $\Delta P \rightarrow \Delta C$ 的概率分布问题。

随机函数的差分概率 $P(Y = \Delta C | X = \Delta P) = \dfrac 1 {2^l}$.

寻找高概率差分特征的一般方法 通常差分 $ΔP → ΔC$ 概率主项为一些差分特征概率的乘积，即 $\Delta P \rightarrow \Delta R_1 \rightarrow \Delta R_2 \rightarrow \cdots \rightarrow \Delta R_{n-1} \rightarrow \Delta C$. 如果我们能研究某个差分特征 $\Delta R_{i-1} \rightarrow \Delta R_i$ 的大小，我们就可以利用类似于动态规划的算法求出高概率差分特征。

我们考虑对 DES 算法进行分析。

线性部件 DES 算法的 P 置换 和 E 扩展 两个部件满足 $P(x) \oplus P(y) = P(x \oplus y)$，因此为线性部件，相应差分特征概率为 1。

非线性部件 DES 算法的 S-box 为非线性部件，为此我们计算其差分分布。也就是说，给定差分 $\Delta P$，我们枚举所有的 $P_1, P_2$ 满足 $P_1 \oplus P_2 = \Delta P$，然后我们统计 $\Delta C$ 的分布。

虽然 S-box 为我们寻找高概率差分特征分布时带来了不变，但是 S-box 的存在却可以直接地为我们减少密钥搜索空间。

具体来说，已知 $E$ 和 $E^\star$，$S_1$ 盒的输出差分为 $\Delta C$，则 $S_1$ 盒的输入为 $E \oplus K$ 与 $E^\star \oplus K$，我们查表 $N(E\oplus E^\star, \Delta C) = N((E\oplus K)\oplus (E^\star \oplus K), \Delta C)$，找出 $\Delta P \rightarrow \Delta C$ 对应的所有可能输入值 $P_1, P_2$，于是 $K = E \oplus P_1$。借助这种方法可以直接 hack 掉 3 轮的 DES。

线性分析