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

分组密码

分组密码简介

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

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

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

古典的代换密码的代换表太小,仅有 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$.

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

image-20220323135852327

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

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

image-20220323140208761

轮函数

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

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

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

密钥方案

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

设计方案

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

Feistel Network

image-20220323141451231

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)算法所最终采用。其基本架构为:

image-20220323142600476

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

S 盒属性:

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

P 盒属性:

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

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

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

DES

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

image-20220323145304203

起始置换与末置换

image-20220323145409521

F 函数

image-20220323145941594

F 函数中的扩展盒 E

image-20220323150125087

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 置换

image-20220325150029031

DES 密钥生成方案

image-20220325145910454

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?
    • 不能够抵挡中间相遇攻击…

[中间相遇攻击]

image-20220325151251672

令集合 $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 结构

image-20220323142600476

以下介绍 AES 的结构。

轮函数

image-20220325152532398

image-20220325153306210

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

其总体流程:

image-20220325153407918

字节替换 SubBytes

S-box:8 Bit 输入,8 Bit 输出,可逆

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

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

行移位 ShiftRows

image-20220325162407249

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

列混合 MixColumns

image-20220325162936267

密钥加 AddRoundKey

image-20220325163933137

  • 每个轮密钥为 128 Bit.

密钥生成算法

image-20220325164236844

image-20220325164244363

AES 解密

image-20220325164618807

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

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

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

分组密码工作模式

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

电子密码本模式 ECB

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

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

密码分组链接模式 CBC

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

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

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

image-20220325173018368

密码反馈模式 CFB

image-20220325173124182

image-20220325173130166

输出反馈模式 OFB

image-20220325173350914

计数器模式 CTR

image-20220325173417266

工作模式分析

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

分组密码分析

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

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

重温:攻击复杂度

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

通用密码分析过程

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

image-20220330144402496

image-20220330144422077

  • 其改进方向: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$ 的分布。

image-20220406135550419

虽然 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。

线性分析