【密码学】4. 分组密码

分组密码

分组密码概述

1. 基本定义
   分组密码是将明文消息编码后的数字序列划分为长度为$n$的组（$n$维矢量），在密钥控制下变换为等长的输出数字序列（$m$维矢量），加密函数为$E:V_n\times K\to V_m$，其中$V_n$、$V_m$为$n$维、$m$维矢量空间，$K$为密钥空间。
2. 核心概念
   • 代换：明文分组到密文分组的可逆变换。对于$n$比特分组，有$2^n$个可能取值，可逆变换的总数为$(2^n)!$（所有可能置换）。例如$n=4$时，4 比特输入（16 种状态）通过代换表映射为 4 比特输出，加密与解密可通过代换表定义。
   • 扩散与混淆（Shannon 提出，抗统计分析的核心）：
     • 扩散：将明文的统计特性（如字母频率）散布到密文，使密文统计特性更均匀（例如通过多轮置换 + 函数变换实现）。
     • 混淆：使密文与密钥的统计关系复杂化，避免敌手通过密文统计特性推导密钥（通过复杂非线性代换实现）。

Feistel 密码结构

1. 基本原理
   • 采用 “乘积密码” 思想，将分组分为左右两半（$L_0,R_0$），经多轮迭代变换：
     • 第$i$轮：$L_i=R_{i-1}$，$R_i=L_{i-1}\oplus F(R_{i-1},K_i)$，其中$F$为轮函数，$K_i$为子密钥。
     • 解密：与加密算法相同，但子密钥使用顺序相反（第 1 轮用$K_n$，最后一轮用$K_1$）。
2. 关键参数
   • 分组大小：越大安全性越高，但速度越慢；
   • 密钥大小：越长安全性越高，但速度越慢；
   • 轮数：多轮可提升安全性（单轮不足以抗攻击）；
   • 子密钥产生算法：复杂度越高，密码分析越难；
   • 轮函数：复杂度越高，安全性越强。

数据加密标准（DES）

1. 基本参数
   • 分组长度：64 比特；密钥长度：56 比特（含 8 位奇偶校验位）；轮数：16 轮。
   • 结构：Feistel 网络，包含初始置换、16 轮迭代、逆初始置换。
2. 加密流程
   • 初始置换（IP）：重排 64 比特明文，输出 32 比特左半（$L_0$）和 32 比特右半（$R_0$）。
   • 轮变换：
     1. 扩展置换（E）：将 32 比特$R_{i-1}$扩展为 48 比特（重复 16 个比特）；
     2. 与 48 位子密钥$K_i$异或；
     3. S 盒代换：8 个 S 盒（每个 6 输入 4 输出），将 48 比特压缩为 32 比特；
     4. 置换（P）：重排 32 比特输出，作为轮函数$F$的结果；
     5. 迭代：$L_i=R_{i-1}$，$R_i=L_{i-1}\oplus F(R_{i-1},K_i)$。
   • 逆初始置换（IP⁻¹）：16 轮后交换左右两半，经 IP⁻¹ 输出 64 比特密文。
3. 密钥产生
   • 56 比特密钥经置换选择 1（PC1）分为 28 比特$C_0$和 28 比特$D_0$；
   • 每轮左移（1 或 2 位，依轮数而定），经置换选择 2（PC2）产生 48 位子密钥$K_i$。
4. 变种
   • 二重 DES：用两个 56 比特密钥（总 112 比特），易受 “中途相遇攻击”（需$2^{56}$存储和计算）；
   • 三重 DES：
     • 两个密钥（EDE 模式）：$C=E_{K1}(D_{K2}(E_{K1}(P)))$，密钥长 112 比特；
     • 三个密钥：$C=E_{K3}(D_{K2}(E_{K1}(P)))$，密钥长 168 比特，安全性更高。

差分密码分析与线性密码分析

1. 差分密码分析
   • 原理：通过分析明文对的差值（$\Delta X=X_1\oplus X_2$）对密文对差值（$\Delta Y=Y_1\oplus Y_2$）的影响，恢复密钥。
   • 核心概念：
     • $r$轮特征：差分序列$({\alpha }_0,{\alpha }_1,...,{\alpha }_r)$，其中${\alpha }_0$为明文差分，${\alpha }_i$为第$i$轮输出差分；
     • 概率：$r$轮特征的概率为各轮函数差分概率的乘积。
2. 线性密码分析
   • 原理：利用 “不平衡线性逼近”，寻找明文（$P$）、密文（$C$）、密钥（$K$）的线性方程$P[i_1,...,i_a]\oplus C[j_1,...,j_b]=K[k_1,...,k_c]$，通过已知明文对的统计偏差（概率≠1/2）确定密钥。
3. 改进方法
   • 包括高阶差分分析、不可能差分分析、多重线性分析、能量分析（针对硬件）等。

分组密码的运行模式

1. 电码本模式（ECB）
   • 特点：每个 64 比特明文分组独立用同一密钥加密，密文与明文一一对应（类似 “电码本”）。
   • 优缺点：简单快速，但重复明文产生重复密文，易暴露统计特性，适合短数据（如密钥传输）。
2. 密码分组链接模式（CBC）
   • 特点：当前明文分组与前一密文分组异或后加密，即$C_i=E_K(P_i\oplus C_{i-1})$，首组需初始向量（IV）：$C_0=E_K(P_0\oplus IV)$。
   • 优缺点：隐藏重复明文，安全性高于 ECB；IV 需保密（防止首组被篡改）。
3. 密码反馈模式（CFB）
   • 特点：将分组密码转为流密码，64 比特移位寄存器初始为 IV，加密输出的前$j$比特与明文单元异或得密文，密文单元移入移位寄存器。
   • 优缺点：实时加密（无需填充），密文与明文等长；错误会传播（影响后续解密）。
4. 输出反馈模式（OFB）
   • 特点：移位寄存器反馈加密算法的输出（而非密文），即$S_i=E_K(S_{i-1})$，密文$C_i=P_i\oplus S_i$。
   • 优缺点：错误不传播（仅影响当前单元），但易受篡改（密文比特翻转会导致明文对应比特翻转）。

国际数据加密算法（IDEA）

1. 基本参数
   • 分组长度：64 比特；密钥长度：128 比特；轮数：8 轮迭代 + 1 轮输出变换。
2. 核心运算
   • 三种非线性运算（确保混淆与扩散）：
     • 逐比特异或（$\oplus$）；
     • 模$2^{16}$加法（$+$）；
     • 模$2^{16}+1$乘法（$\odot$，0 视为$2^{16}$）。
3. 加密流程
   • 明文分为 4 个 16 比特子段$(X_1,X_2,X_3,X_4)$；
   • 每轮用 6 个子密钥，通过 “乘加（MA）结构” 处理，输出 4 个子段；
   • 输出变换：用 4 个子密钥，调整子段顺序以抵消最后一轮的交换。
4. 解密
   • 子密钥为加密子密钥的逆元（模$2^{16}+1$乘法逆元、模$2^{16}$加法逆元），轮密钥顺序相反。

高级加密标准（AES，Rijndael）

1. 基本参数
   • 分组长度（$N_b$）：128/192/256 比特（对应列数 4/6/8）；
   • 密钥长度（$N_k$）：128/192/256 比特（对应列数 4/6/8）；
   • 轮数（$N_r$）：10/12/14 轮（依分组和密钥长度而定）。
2. 数学基础
   • 基于有限域$GF(2^8)$，元素表示为 8 次多项式（系数为 0/1），加法为异或，乘法模不可约多项式$m(x)=x^8+x^4+x^3+x+1$（十六进制 “11B”）。
3. 轮函数
   • 字节代换（SubBytes）：通过 S 盒（非线性变换，先求$GF(2^8)$逆元，再仿射变换）替换每个字节；
   • 行移位（ShiftRow）：第 0 行不动，第 1 行左移 1 位，第 2 行左移 2 位，第 3 行左移 3 位（依$N_b$调整）；
   • 列混合（MixColumn）：每列视为$GF(2^8)$上多项式，与固定多项式$c(x)=03x^3+01x^2+01x+02$模$x^4+1$相乘；
   • 密钥加（AddRoundKey）：状态与轮密钥逐比特异或。
   • 最后一轮无 “列混合”。
4. 密钥扩展
   • 种子密钥扩展为$N_b\times (N_r+1)$个字（4 字节），通过循环移位、S 盒代换、轮常量异或生成子密钥。
5. 解密
   • 用逆变换（逆字节代换、逆行移位、逆列混合），轮密钥为加密轮密钥的逆序（最后一轮密钥不变，其余经逆列混合处理）。

中国商用密码 SM4

1. 基本参数
   • 分组长度：128 比特；密钥长度：128 比特；轮数：32 轮。
2. 核心部件
   • S 盒：8 输入 8 输出非线性替换，基于固定表；
   • 非线性变换（$\tau$）：4 个 S 盒并行处理 4 字节；
   • 线性变换（$L$）：$L(B)=B\oplus (B\ll 2)\oplus (B\ll 10)\oplus (B\ll 18)\oplus (B\ll 24)$，实现扩散；
   • 合成变换（$T$）：$T(X)=L(\tau (X))$，结合混淆与扩散。
3. 加密流程
   • 明文分为 4 个 32 比特子段$(X_0,X_1,X_2,X_3)$；
   • 32 轮迭代：$X_{i+4}=X_i\oplus T(X_{i+1}\oplus X_{i+2}\oplus X_{i+3}\oplus r{k}_i)$，$r{k}_i$为轮密钥；
   • 反序处理：$(Y_0,Y_1,Y_2,Y_3)=(X_{35},X_{34},X_{33},X_{32})$。
4. 密钥扩展
   • 由 128 比特密钥生成 32 个轮密钥，使用固定常数$FK$和参数$CK$，通过$T^{\prime }$变换（线性变换$L^{\prime }$替代$L$）生成。

祖冲之密码（ZUC）

1. 结构
   • 三层逻辑：16 级线性反馈移位寄存器（LFSR）、比特重组（BR）、非线性函数（F）。
   • LFSR：16 个 31 比特寄存器，特征多项式为$GF(2^{31}-1)$上的本原多项式，支持初始化（引入非线性函数输出）和工作模式。
   • 比特重组：从 LFSR 抽取 128 比特，组成 4 个 32 比特字$(X_0,X_1,X_2,X_3)$。
   • 非线性函数：压缩 96 比特（$X_0,X_1,X_2$）为 32 比特，含 S 盒（4 个 8×8 S 盒并行）和线性变换。
2. 应用
   • 用于 4G 移动通信加密（128-EEA3 算法），基于初始密钥和向量生成密钥流，与消息异或实现加解密。