《现代密码学》分组密码笔记
前几周密码学课要么在写软工,要么在跑实验,这个模块算是完全需要从头学习了,现在就坐在教室第一排看几周前的课件的样子,希望一天能补完吧(((
分组密码
分组密码简介
古典密码学:置换密码与代换密码
置换密码根据一定的规则重新排列明文,以便打破明文的结构特性。置换密码的特点是保持明文的所有字符不变,只是利用置换打乱了明文字符的位置和次序。
代换密码就是将明文中的一个字母由其它字母、数字或符号替代的一种方法。我们需要建立一个代换表,加密时将需要加密的明文依次通过查表,替换为相应的字符,明文字符被逐个替换后,生成无任何意义的字符串,即密文。这样的代换表,通常称为密钥。
古典的代换密码的代换表太小,仅有 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$ 的情况.
行移位 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。