第3章 分组密码¶
3.1 分组密码的基本原理及发展现状¶
基本原理¶
分组密码 (Block Cipher) 是对称密码体制中的一个重要类别。与流密码逐比特或逐字节处理明文不同,分组密码将明文消息分割成固定长度的数据块 (blocks),然后使用相同的密钥对每个数据块独立地进行加密和解密操作。
核心概念:
- 数据块 (Block): 明文和密文都被分割成固定大小的单元,称为数据块。典型的数据块大小有 64 比特 (如 DES、3DES)、128 比特 (如 AES)。如果最后一段明文不足一个完整块,通常需要进行填充 (Padding)。
- 密钥 (Key): 一个固定长度的比特序列,用于控制加密和解密过程。密钥的长度(密钥空间大小)是衡量密码强度的一个重要指标。
- 轮函数 (Round Function): 分组密码的加密过程通常不是一步完成,而是通过多次迭代相同的或相似的变换函数来完成,每一次迭代称为一轮 (Round)。每一轮都使用一个从主密钥派生出来的轮密钥 (Round Key)。
- 代换 (Substitution): 将输入数据块中的一部分(例如几个比特)替换为另一部分。这通常通过S盒 (Substitution Box) 实现,S盒是非线性组件,用于引入混淆。
- 置换 (Permutation): 将输入数据块中的比特位置进行重新排列。这通常通过P盒 (Permutation Box) 实现,P盒是线性组件,用于引入扩散。
香农 (Shannon) 的设计原则:
现代分组密码的设计深受克劳德·香农提出的两个基本原则的影响,旨在抵抗统计分析:
- 混淆 (Confusion): 使密文与密钥之间的统计关系尽可能复杂,使得攻击者即使拥有大量密文和明文,也难以从中推断出密钥。主要通过代换操作(如S盒)来实现。
- 扩散 (Diffusion): 将明文的统计特性散布到尽可能多的密文中,使得明文中的一位改变会导致密文中多位(理想情况下约一半)的改变,并且密文中的一位也依赖于明文中的多位。主要通过置换操作(如P盒或更复杂的线性变换)来实现。重复多轮的代换和置换操作可以有效地达到混淆和扩散的目的。
理想分组密码 (Ideal Block Cipher):
一个理想的 \(n\) 比特分组密码可以被看作是一个巨大的、固定的、可逆的代换表,其中每个可能的 \(n\) 比特明文块都唯一地映射到一个 \(n\) 比特密文块,具体映射关系由密钥决定。对于一个 \(n\) 比特的块,有 \(2^n!\) 种可能的这样的映射。密钥的作用就是从这些映射中选择一个。然而,实际构造这样一个巨大的密码本是不现实的,因此实际的分组密码通过轮函数迭代来逼近这种理想特性。
发展现状¶
分组密码的发展经历了几个重要阶段:
- 早期阶段与 DES (Data Encryption Standard):
- 1970年代,IBM 设计了 Lucifer 算法,后被美国国家标准局 (NBS,现在的 NIST) 采纳并修改为 DES。
- DES 是第一个被广泛应用的商业级分组密码标准,块大小为64位,密钥长度为56位(实际输入64位,但8位为奇偶校验位)。它采用了Feistel结构。
-
由于其56位密钥长度在计算能力飞速发展的今天已不足以抵抗暴力破解,DES 已不再被认为是安全的(尽管 3DES 仍在某些传统系统中使用)。
-
AES (Advanced Encryption Standard) 的出现:
- 1990年代末,NIST 发起公开竞赛,旨在征集一个新的、更安全、更高效的分组密码标准来取代 DES。
- 2001年,比利时密码学家 Joan Daemen 和 Vincent Rijmen 提交的 Rijndael 算法胜出,成为 AES。
- AES 支持128位、192位和256位三种密钥长度,数据块大小固定为128位。它采用代换-置换网络 (Substitution-Permutation Network, SPN) 结构。
-
AES 目前是全球应用最广泛的对称加密标准,被认为是安全的。
-
后AES时代与新挑战:
- 密码分析的进展: 尽管 AES 本身仍然安全,但密码分析技术(如线性密码分析、差分密码分析、积分密码分析、不可能差分、中间相遇攻击等)不断发展,对新的密码设计提出了更高的要求。
- 轻量级密码 (Lightweight Cryptography): 随着物联网 (IoT)、RFID 标签、嵌入式系统等资源受限设备的大量涌现,对能够在计算能力、功耗、存储空间等方面都非常有限的环境下高效运行的密码算法的需求日益增加。NIST 近期也完成了轻量级密码的标准化项目(如 ASCON 算法族)。
- 侧信道攻击 (Side-Channel Attacks): 这类攻击利用密码算法在物理实现(硬件或软件)过程中的信息泄露(如功耗、电磁辐射、执行时间等)来获取密钥信息,对分组密码的实际部署提出了严峻挑战。对应的防御措施(掩码、隐藏、乱序执行等)是研究热点。
- 量子计算的威胁: 虽然 Grover 算法理论上可以将暴力破解对称密钥的复杂度从 \(O(2^k)\) 降低到 \(O(2^{k/2})\),但对于 AES-256 这样的长密钥分组密码,量子计算的威胁相对较小(仍需 \(2^{128}\) 量级操作)。然而,对未来更强大的量子计算机的预期,也促使研究者思考后量子时代的对称密码设计,尽管目前主流观点认为现有安全分组密码(如AES)在后量子时代仍是安全的,只需适当增加密钥长度。
- 专用算法和新设计理念: 不断有新的分组密码设计被提出,探索新的结构、新的非线性组件和新的安全证明方法。例如,基于 ARX (Addition-Rotation-XOR) 的设计因其在软件中高效实现而受到关注。
- 可证明安全性 (Provable Security): 密码设计越来越重视形式化的安全模型和在这些模型下的安全性证明,尽管完全的可证明安全仍然是一个挑战。
总的来说,分组密码领域仍然是一个活跃的研究领域,不断适应新的应用场景、新的攻击技术和新的计算范式。
3.2 Feistel 结构和 DES 算法¶
Feistel 结构 (Feistel Network)¶
Feistel 结构是一种用于构造分组密码的对称结构,由 Horst Feistel 在 IBM 的 Lucifer 项目中首次使用,并因其在 DES 中的应用而广为人知。其核心思想是将数据块分成左右两半,并通过多轮处理,在每一轮中,一半数据通过一个轮函数 \(F\) 进行变换,然后与另一半数据进行异或操作。
Feistel 结构的一轮操作通常如下:
设 \(L_i\) 和 \(R_i\) 分别是第 \(i\) 轮加密输入的左半部分和右半部分, \(K_i\) 是第 \(i\) 轮的轮密钥。
- 输入分割: 将输入的 \(2w\) 比特数据块分为左右两半,每半 \(w\) 比特:\((L_{i-1}, R_{i-1})\)。
- 右半部分处理: 右半部分 \(R_{i-1}\) 与轮密钥 \(K_i\) 一起作为轮函数 \(F\) 的输入,即 \(F(R_{i-1}, K_i)\)。
- 异或操作: 轮函数 \(F\) 的输出与左半部分 \(L_{i-1}\) 进行异或操作:\(L_i = L_{i-1} \oplus F(R_{i-1}, K_i)\)。
- 左右交换 (通常在下一轮之前): 新的右半部分直接等于上一轮的右半部分:\(R_i = R_{i-1}\) (这是经典描述,但更常见的是 \(L_i = \text{old } L_{i-1} \oplus F(\text{old } R_{i-1}, K_i)\) 和 \(R_i = \text{old } R_{i-1}\),然后将 \((L_i, R_i)\) 传递给下一轮,或者在传递前交换 \(L_i\) 和 \(R_i\))。
更标准的 Feistel 轮结构描述:
经过 \(n\) 轮迭代后,通常在最后一轮之后不再进行左右交换(或者说,进行一次额外的交换以统一加密和解密的形式)。
Feistel 结构的优点:
- 加密和解密过程相似: 这是 Feistel 结构最显著的优点。解密过程可以使用与加密完全相同的算法,只需将轮密钥按相反的顺序使用即可。
- 对于一轮加密:\(L_i = R_{i-1}\), \(R_i = L_{i-1} \oplus F(R_{i-1}, K_i)\)
- 要进行解密,从 \((L_i, R_i)\) 得到 \((L_{i-1}, R_{i-1})\):
- \(R_{i-1} = L_i\)
- \(L_{i-1} = R_i \oplus F(R_{i-1}, K_i) = R_i \oplus F(L_i, K_i)\)
- 这意味着轮函数 \(F\) 不需要是可逆的,大大简化了 \(F\) 函数的设计。
- 灵活性: 轮函数 \(F\) 的具体设计可以非常复杂,可以包含代换、置换等多种操作,以实现良好的混淆和扩散。
DES 算法 (Data Encryption Standard)¶
DES 是一个典型的 Feistel 结构分组密码。
- 历史: 1970年代由IBM基于Lucifer算法开发,1977年被美国国家标准局 (NBS,后来的NIST) 选定为官方的加密标准。
- 参数:
- 块大小 (Block Size): 64 比特。
- 密钥长度 (Key Length): 表面上是64比特,但每8比特的最后1比特是奇偶校验位,因此有效密钥长度为 56 比特。
- 轮数 (Number of Rounds): 16 轮。
DES 加密过程概述:
- 初始置换 (Initial Permutation, IP): 64位明文块首先经过一个固定的初始置换,重新排列比特顺序。这个置换没有密码学意义,据称是为了方便在1970年代的硬件上装载数据。
- 16轮 Feistel 迭代:
- 经过 IP 后的64位块被分成左右两半,各32位:\((L_0, R_0)\)。
- 进行16轮迭代,每轮操作如下 (\(i\) 从 1 到 16):
其中 \(K_i\) 是48位的轮密钥,由56位主密钥通过密钥调度算法 (Key Schedule) 生成。
- 最终置换 (Final Permutation, FP): 16轮迭代后,将 \((L_{16}, R_{16})\) 合并(但通常是在 \((R_{16}, L_{16})\) 的顺序上,即最后一轮后不交换或等效于交换),然后经过一个初始置换的逆置换 FP,得到64位密文块。
DES 的轮函数 \(F(R, K)\):
轮函数 \(F\) 是 DES 安全性的核心,它对32位的右半部分 \(R_{i-1}\) 和48位的轮密钥 \(K_i\) 进行操作,输出32位。
- 扩展置换 (Expansion Permutation, E): 将32位的 \(R_{i-1}\) 扩展为48位。这个扩展通过复制 \(R_{i-1}\) 中的某些比特来实现,使得扩展后的结果能够与48位的轮密钥 \(K_i\) 进行异或。
- 密钥混合 (Key Mixing): 扩展后的48位结果与48位轮密钥 \(K_i\) 进行异或。
- S盒代换 (S-box Substitution): 异或结果被分成8个6比特的小组,每个小组输入到一个对应的S盒 (Substitution Box)。DES 有8个不同的S盒 (\(S_1, S_2, \dots, S_8\))。每个S盒都是一个固定的非线性代换表,将6比特输入映射为4比特输出。这是DES中唯一的非线性操作,也是其安全性的关键来源(提供混淆)。
- 每个6比特输入 \((b_1 b_2 b_3 b_4 b_5 b_6)\) 中,\(b_1b_6\) 两位决定S盒的行号 (0-3),\(b_2b_3b_4b_5\) 四位决定S盒的列号 (0-15)。
- P盒置换 (P-box Permutation, P): 8个S盒输出的4比特结果(共32比特)再经过一个固定的32位P盒置换,进一步打乱比特顺序,以实现扩散。
DES 密钥调度算法:
从56位主密钥生成16个48位轮密钥的过程:
- 初始密钥置换 (Permuted Choice 1, PC-1): 64位输入密钥(含校验位)先去掉校验位,然后对剩余的56位进行置换,并分成左右两半 \(C_0\) 和 \(D_0\) (各28位)。
- 循环左移 (Circular Left Shift): 在每一轮 \(i\),根据一个预设的移位数目(第1, 2, 9, 16轮移1位,其他轮移2位),分别对 \(C_{i-1}\) 和 \(D_{i-1}\) 进行循环左移,得到 \(C_i\) 和 \(D_i\)。
- 轮密钥生成 (Permuted Choice 2, PC-2): 将 \(C_i\) 和 \(D_i\) 合并成56位,然后通过另一个置换选择 (PC-2) 从中选出48位作为轮密钥 \(K_i\)。
DES 的安全性与弱点:
- 密钥长度: 56位密钥长度是 DES 最主要的弱点。在1990年代末,通过暴力破解(尝试所有 \(2^{56}\) 个可能密钥)已经变得可行。
- S盒设计: DES的S盒设计准则最初并未公开,引发了一些关于是否存在后门或隐藏弱点的猜测。后来分析表明S盒设计良好,能抵抗差分密码分析。
- 弱密钥 (Weak Keys): DES有4个弱密钥,使用这些密钥加密和解密过程完全相同 (\(E_K(E_K(P)) = P\))。
- 半弱密钥 (Semi-weak Keys): DES有6对(12个)半弱密钥。若用一对中的一个密钥加密,用另一个密钥解密,效果等同于用前者加密。
- 补特性 (Complementation Property): \(E_{\overline{K}}(\overline{P}) = \overline{E_K(P)}\),其中 \(\overline{X}\) 是 \(X\) 的按位取反。这可以将暴力破解的密钥空间减半。
DES 的变体:
- 2DES (Double DES): \(C = E_{K2}(E_{K1}(P))\)。由于中间相遇攻击 (Meet-in-the-Middle Attack),其有效密钥长度仅为 \(2 \times 56\) 理论强度的一小部分,大约为 \(2^{57}\),因此安全性提升有限。
- 3DES (Triple DES): 最常见的是 EDE (Encrypt-Decrypt-Encrypt) 模式:
- 双密钥3DES (2TDES): \(C = E_{K1}(D_{K2}(E_{K1}(P)))\)。有效密钥长度为 \(2 \times 56 = 112\) 位。
- 三密钥3DES (3TDES): \(C = E_{K3}(D_{K2}(E_{K1}(P)))\)。有效密钥长度为 \(3 \times 56 = 168\) 位。 3DES 通过增加密钥长度和迭代次数,显著增强了对暴力破解的抵抗能力,曾被广泛用于替代DES。但其操作速度较慢(三次DES运算),且块大小仍为64位,不适合处理大量数据。目前也逐渐被 AES 取代。
3.3 AES 算法 (Advanced Encryption Standard)¶
AES,即高级加密标准,是由美国国家标准与技术研究院 (NIST) 于2001年发布的一个对称分组密码标准,用以取代DES。AES基于比利时密码学家 Joan Daemen 和 Vincent Rijmen 提出的 Rijndael 算法。
主要特点:
- 结构: 采用代换-置换网络 (Substitution-Permutation Network, SPN) 结构,而非 Feistel 结构。这意味着加密和解密路径不同(但密切相关)。
- 块大小 (Block Size): 固定为 128 比特。
- 密钥长度 (Key Lengths): 支持三种长度:128 比特、192 比特、256 比特。
- 轮数 (Number of Rounds): 轮数取决于密钥长度:
- 128位密钥:10 轮
- 192位密钥:12 轮
- 256位密钥:14 轮
AES 的数据单元:
AES 的所有操作都在一个称为状态 (State) 的 \(4 \times 4\) 字节矩阵上进行。输入的128位明文块被排列成这个矩阵,其中矩阵的列优先填充。例如,明文块 \(b_0, b_1, \dots, b_{15}\) 形成状态:
每一轮变换都会更新这个状态矩阵。
AES 加密过程:
- 初始轮密钥加 (Initial AddRoundKey): 将状态与第一个轮密钥(也称为白化密钥,直接从主密钥派生或等于主密钥)进行按字节异或。
- 主要轮 (Rounds): 进行 \(N_r-1\) 轮标准迭代,其中 \(N_r\) 是总轮数。每轮包含以下四个步骤:
- SubBytes (字节代换):
- ShiftRows (行移位):
- MixColumns (列混淆):
- AddRoundKey (轮密钥加):
- 最终轮 (Final Round): 进行最后一轮迭代,与主要轮类似,但不包含 MixColumns 步骤。
- SubBytes
- ShiftRows
- AddRoundKey
AES 的轮操作详解:
- a) SubBytes (字节代换):
- 这是一个非线性代换步骤,状态矩阵中的每个字节都通过一个固定的8位S盒 (Rijndael S-box) 进行独立的代换。
- 该S盒是通过在有限域 GF(\(2^8\)) 中先计算每个字节的乘法逆元(0映射到0),然后再对结果字节进行一个固定的仿射变换 (affine transformation) 得到的。
-
此步骤提供混淆,是AES中唯一的非线性操作。
-
b) ShiftRows (行移位):
- 这是一个线性置换步骤,状态矩阵的每一行中的字节都进行循环左移。
- 第0行:不移位。
- 第1行:循环左移1个字节。
- 第2行:循环左移2个字节。
- 第3行:循环左移3个字节。
-
此步骤提供跨列的扩散。
-
c) MixColumns (列混淆):
- 这是一个线性混合步骤,对状态矩阵的每一列独立进行操作。
- 每一列被视为 GF(\(2^8\)) 上的一个四项式,然后乘以一个固定的四项式 \(a(x) = \{03\}x^3 + \{01\}x^2 + \{01\}x + \{02\}\),模 \(x^4+1\)。
-
这等效于将每列向量左乘一个固定的 \(4 \times 4\) 矩阵 (其元素在 GF(\(2^8\)) 中):
\[ \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix} \] -
此步骤提供列内的扩散,与 ShiftRows 结合,确保经过几轮后每个字节都依赖于所有明文字节。
-
注意: 在最终轮中省略此步骤。
-
d) AddRoundKey (轮密钥加):
- 将当前轮的状态矩阵与该轮的128位轮密钥(同样排列成 \(4 \times 4\) 字节矩阵)进行按字节异或。
- 轮密钥由主密钥通过密钥扩展算法 (Key Expansion / Key Schedule) 生成。
AES 密钥扩展算法 (Key Schedule):
密钥扩展算法从主密钥生成 AES 加密所需的全部轮密钥。总共需要 \(N_r+1\) 个128位的轮密钥。
- 主密钥首先被复制到扩展密钥数组的前 \(N_k\) 个字 (\(N_k\) 是主密钥的字数,128位密钥为4字,192位为6字,256位为8字)。
- 后续的字 \(w_i\) 通过前一个字 \(w_{i-1}\) 和 \(N_k\) 个字之前的字 \(w_{i-N_k}\) 的组合来生成。
- 如果 \(i\) 是 \(N_k\) 的倍数,则 \(w_{i-1}\) 在组合前会经过一个称为 g函数 的特殊处理:
- RotWord: 将 \(w_{i-1}\) 的四个字节循环左移一位。
- SubWord: 对 RotWord 结果的每个字节应用 AES 的 S盒。
- Rcon: 将 SubWord 结果的第一个字节与一个轮常数 (Round Constant, Rcon) 进行异或。Rcon 是一个预定义的值,每轮不同,用于消除对称性。
- 如果 \(i\) 不是 \(N_k\) 的倍数 (并且对于 \(N_k > 6\),当 \(i \pmod{N_k} = 4\) 时有特殊处理,仅对256位密钥):
(对于256位密钥且 \(i \pmod{N_k} = 4\),则 \(w_i = w_{i-N_k} \oplus \text{SubWord}(w_{i-1})\))
AES 解密过程:
解密过程是加密过程的逆运算。它使用相同的轮密钥,但顺序相反,并且每一轮操作都替换为其逆操作:
- 初始轮密钥加 (Initial AddRoundKey): 使用最后一个轮密钥 (\(K_{N_r}\))。
- 主要轮 (Rounds): \(N_r-1\) 轮 (从 \(N_r-1\) 轮到第1轮):
- InvShiftRows (逆行移位): ShiftRows 的逆操作(循环右移)。
- InvSubBytes (逆字节代换): SubBytes 的逆操作(使用逆S盒)。
- AddRoundKey (轮密钥加): 使用对应的轮密钥。
- InvMixColumns (逆列混淆): MixColumns 的逆操作(乘以逆矩阵)。
- 最终轮 (Final Round):
- InvShiftRows
- InvSubBytes
- AddRoundKey (轮密钥加): 使用第一个轮密钥 (\(K_0\))。
注意 AddRoundKey 的逆操作就是它本身(因为异或的逆是异或)。InvMixColumns 是在最终轮之前,与加密过程的结构对应。
AES 的安全性与现状:
- 安全性: AES 被认为是目前最安全和分析最透彻的分组密码之一。已知的针对 AES 的最佳攻击(如积分攻击、不可能差分攻击、中间相遇攻击的变种)都远未达到实际可行的程度,通常需要不切实际的数据量或计算复杂度,或者只能攻击简化的轮数版本。
- 性能: AES 在硬件和软件上都能高效实现。许多现代处理器都内置了 AES 指令集 (AES-NI),可以极大地加速 AES 的运算。
- 广泛应用: AES 已成为全球范围内数据加密的事实标准,广泛应用于各种安全协议 (如 TLS/SSL, SSH, IPsec)、磁盘加密 (如 BitLocker, FileVault)、文件加密、数据库加密等。
3.4 分组密码的工作模式 (Modes of Operation for Block Ciphers)¶
分组密码本身只能加密固定长度的数据块。为了能够安全地加密长度可变的明文消息(通常远大于一个数据块的长度),需要使用工作模式 (Modes of Operation)。工作模式定义了如何重复使用分组密码的单块加密功能来处理多块数据。
选择合适的工作模式对于保证整体加密方案的安全性至关重要。不同的模式在错误传播、并行性、是否需要填充、是否能用于流加密等方面有不同特性。
以下是一些常见的分组密码工作模式:
0. 电子密码本模式 (Electronic Codebook Mode, ECB) - 作为对比基线¶
- 原理: 最简单的工作模式。将明文分割成多个数据块,然后对每个明文块使用相同的密钥独立进行加密。
- 优点:
- 简单直观。
- 每个块的加密/解密可以并行处理,速度快。
- 一个密文块的错误不会影响其他块的解密。
- 缺点:
- 致命缺陷: 如果明文中存在重复的数据块,那么加密后对应的密文块也会完全相同。这会暴露明文数据的模式和统计特性。例如,一张位图图像用 ECB 模式加密后,图像的轮廓通常依然可见。
- 容易受到重放攻击、块替换攻击等。
- 应用: 由于其严重的安全性缺陷,ECB 模式通常不推荐用于大多数应用,除非是在极少数情况下,例如加密完全随机的数据(如会话密钥)且数据量很小。
- 填充: 如果最后一个明文块不足一个完整块,需要进行填充。
1. 密文分组链接模式 (Cipher Block Chaining Mode, CBC)¶
- 原理: 为了克服 ECB 的缺点,CBC 模式引入了链接机制。每个明文块在加密前,首先与前一个密文块进行异或 (XOR) 操作,然后再用密钥加密。对于第一个明文块,由于没有“前一个密文块”,它会与一个称为初始化向量 (Initialization Vector, IV) 的随机数据块进行异或。
- 初始化向量 (IV): IV 必须是不可预测的(最好是随机生成的),并且对于使用相同密钥加密的每条消息都必须是唯一的。IV 不需要保密,但其完整性必须得到保护。通常与密文一起传输。
- 优点:
- 相同的明文块如果出现在消息的不同位置,或者在两条用不同IV加密的不同消息中,会产生不同的密文块,隐藏了明文的模式。
- 是最常用的模式之一。
- 缺点:
- 加密过程是串行的: 加密第 \(i\) 块必须等待第 \(i-1\) 块的密文 \(C_{i-1}\) 生成。
- 错误传播 (Error Propagation) - 加密时: 如果明文块 \(P_i\) 中有一位错误,那么 \(C_i\) 及其后的所有密文块都会受到影响。
- 错误传播 (Error Propagation) - 解密时:
- 如果密文块 \(C_i\) 中有一位错误,则解密后的 \(P_i\) 会完全损坏(平均一半的比特出错)。
- 同时,\(C_i\) 中的错误只会影响 \(P_{i+1}\) 中与 \(C_i\) 错误比特对应的那个比特,即 \(P_{i+1} = D_K(C_{i+1}) \oplus C_i\),错误在 \(C_i\) 中影响了 \(P_{i+1}\)。之后的 \(P_{i+2}, P_{i+3}, \dots\) 不受影响。这种有限的错误传播性有时被视为一种优势。
- 需要填充: 如果最后明文块不完整,需要填充到标准块大小。填充方案必须明确,以便解密时能正确移除。
- 解密并行性: 解密时,如果所有密文块 \(C_i\) 和 \(C_{i-1}\) 都已知,则 \(D_K(C_i)\) 可以并行计算,然后与 \(C_{i-1}\) 异或得到 \(P_i\)。
2. 计数器模式 (Counter Mode, CTR)¶
- 原理: CTR 模式将分组密码用作一个密钥流产生器,从而将分组密码转换成流密码。它通过加密一个计数器 (Counter) 的连续值来生成密钥流块,然后将密钥流块与明文块进行异或得到密文块。
- 计数器通常由两部分组成:一个随机数或一次性数 (Nonce),对每条消息唯一;以及一个从0开始递增的序列号。
其中 \(\text{Counter}_i\) 通常是 \(0, 1, 2, \dots\)。
- Nonce 和 Counter: 组合的 (Nonce, Counter) 值对于给定的密钥必须是唯一的。Nonce 的作用是确保即使计数器序列相同,不同消息的密钥流也不同。Nonce 不需要保密,但必须唯一。
- 优点:
- 高度并行性: 加密和解密过程中的 \(E_K(\text{Nonce} || \text{Counter}_i)\) 操作可以完全并行执行,因为每个密钥流块的生成独立于其他块。
- 随机访问: 可以直接解密密文中的任意块,而无需先解密前面的块。
- 无需填充: 因为它是流模式,如果最后一个明文块不完整,只需使用相应长度的密钥流即可。
- 预处理: 密钥流 \(O_i\) 可以在明文到达之前预先计算好。
- 缺点:
- 密钥流重用是灾难性的: 如果 (Nonce, Counter, Key) 的组合被重用(例如,两条消息使用了相同的Nonce和Key,导致相同的计数器序列生成了相同的密钥流),则会导致严重的安全问题 (类似于流密码中的 "two-time pad")。\(C_1 \oplus C_2 = (P_1 \oplus O) \oplus (P_2 \oplus O) = P_1 \oplus P_2\)。
- 对IV(Nonce)的唯一性要求非常严格。
- 错误传播: 密文中的一位错误只影响对应明文中的一位,不影响其他块。
3. 密文反馈模式 (Cipher Feedback Mode, CFB)¶
- 原理: CFB 模式也可以将分组密码用作成一个自同步的流密码。它将前一个密文块(或其一部分)作为分组密码的输入,加密后的输出再与当前明文块异或得到当前密文块。
- 对于第一个块,使用一个初始化向量 (IV) 作为“前一个密文块”。
- 可以定义为 CFB-\(s\) 模式,其中 \(s\) 是反馈的比特数 (通常 $s=1, 8, $ 或块大小)。这里以全块反馈 (\(s=\)块大小) 为例:
注意,这里解密时仍然使用的是分组密码的加密函数 \(E_K\),因为 \(E_K(C_{i-1})\) 扮演的是密钥流的角色。
- 初始化向量 (IV): 与CBC类似,IV需要随机且唯一,不需要保密。
- 优点:
- 自同步 (Self-synchronizing): 如果密文中丢失或损坏了一些比特,经过一定数量的正确密文块后,解密过程可以自动恢复同步(具体是当错误数据完全移出反馈寄存器后)。
- 可以加密小于一个完整块的数据单元 (例如CFB-8模式,每次处理1字节)。
- 缺点:
- 加密过程是串行的: 生成 \(C_i\) 依赖于 \(C_{i-1}\)。
- 错误传播 (Error Propagation) - 解密时: 密文块 \(C_i\) 中的一位错误会使 \(P_i\) 完全损坏,并且还会影响后续 \(P_j\) 的解密,直到错误的 \(C_i\) 被移出反馈链(对于全块CFB,会影响 \(P_{i+1}\) 的一个比特)。具体来说,如果 \(C_j\) 有一个比特错误,那么 \(P_j\) 会被损坏,并且 \(C_{j+1}\) 的解密也会出错(因为 \(E_K(C_j)\) 出错)。
- 效率: 如果 \(s\) 远小于块大小 (如 CFB-1, CFB-8),则每加密 \(s\) 位明文就需要执行一次完整的分组密码加密操作,效率较低。
- 解密并行性: 与加密类似,解密也是串行的。
4. 输出反馈模式 (Output Feedback Mode, OFB)¶
- 原理: OFB 模式也将分组密码用作一个同步的流密码。它通过将分组密码的输出(而不是密文)反馈回输入来生成密钥流。
- 首先,使用一个初始化向量 (IV) 作为分组密码的第一次输入。
- 后续,将前一次分组密码的输出 \(O_{i-1}\) 作为下一次的输入。
- 初始化向量 (IV): 与CTR模式类似,IV对于给定的密钥必须是唯一的,不需要保密。
- 优点:
- 无错误传播到明文: 密文块 \(C_i\) 中的一位错误只会导致解密后对应明文 \(P_i\) 中的一位错误,不会影响其他明文块。
- 密钥流可以预计算: 与 CTR 模式类似。
- 缺点:
- 密钥流生成是串行的: \(O_i\) 的生成依赖于 \(O_{i-1}\)。
- 同步性要求高: 如果发送方和接收方的密钥流产生过程失去同步(例如,IV不同或实现有误),则所有后续解密都会失败。
- 对IV唯一性要求严格: 如果 (IV, Key) 被重用,则会产生相同的密钥流,导致与 CTR 模式相同的 "two-time pad" 安全问题。
- 内部状态周期: 如果密钥流产生器 \(O_i = E_K(O_{i-1})\) 进入一个短周期,那么密钥流也会重复,可能导致安全风险。CTR模式通过显式使用计数器避免了这个问题。
- 与CFB的区别: OFB将加密算法的输出反馈,而CFB将密文反馈。因此,OFB的密钥流生成独立于明文和密文,而CFB的密钥流依赖于先前的密文。
选择工作模式的考虑因素:
- 安全性需求: 是否需要抵抗特定模式的攻击?是否能容忍IV重用带来的风险?
- 错误容忍度: 应用是否对传输错误敏感?错误传播的特性是否可接受?
- 性能需求: 是否需要并行处理?是否可以预计算?
- 实现复杂度:
- 随机访问需求: 是否需要能随机解密密文的某一部分?
目前,AES-GCM (Galois/Counter Mode) 和 AES-CCM (Counter Mode with CBC-MAC) 等认证加密模式 (Authenticated Encryption with Associated Data, AEAD) 因其能同时提供机密性、完整性和真实性认证,越来越受到推荐和广泛使用。这些模式通常基于 CTR 模式来提供加密。