对称密码学是现代密码学的基石，其中发送方和接收方共享相同的秘密密钥进行加密和解密操作。本章将深入探讨对称密码学的核心概念，包括流密码、分组密码、运行模式等关键技术，并分析其安全性理论基础。我们将从Claude Shannon的完美保密性理论出发，逐步构建现代对称密码学的理论框架，理解语义安全性的重要性，并深入分析AES算法的设计原理。
学习目标：
Claude Shannon在1949年的开创性工作中首次给出了密码学安全性的严格数学定义。一个加密方案具有完美保密性（Perfect Secrecy）当且仅当：
\[\Pr[M = m | C = c] = \Pr[M = m]\]对于所有明文 $m$ 和密文 $c$，其中 $M$ 表示明文随机变量，$C$ 表示密文随机变量。
这个定义的直观含义是：观察到密文 $c$ 不会提供任何关于明文 $m$ 的信息。换句话说，密文在统计上完全独立于明文。
香农定理：一个加密方案具有完美保密性当且仅当：
| 密钥空间的大小至少等于明文空间的大小：$ | \mathcal{K} | \geq | \mathcal{M} | $ |
证明思路（充分性方向）： 假设条件满足，对于任意明文 $m$ 和密文 $c$：
| 由于密钥等概率分布，$\Pr[K = k] = 1/ | \mathcal{K} | $ |
| 因此 $\Pr[C = c | M = m] = 1/ | \mathcal{K} | $，与 $m$ 无关 |
Rule of thumb：完美保密性需要密钥长度至少等于明文长度，这在实际应用中往往不可行。
一次一密是唯一实用的完美保密系统：
明文： m₁ m₂ m₃ ... mₙ
密钥： k₁ k₂ k₃ ... kₙ (真随机生成)
密文： c₁ c₂ c₃ ... cₙ
其中 cᵢ = mᵢ ⊕ kᵢ
安全性分析：
流密码试图近似一次一密的安全性，通过伪随机数生成器（PRNG）从短密钥生成长密钥流：
\[c_i = m_i \oplus s_i\]其中 $s_i$ 是由种子密钥 $k$ 生成的伪随机序列的第 $i$ 位。
核心思想：用计算安全性替代信息论安全性，密钥流在多项式时间内不可区分于真随机序列。
LFSR是流密码中最基础的组件：
+-----+-----+-----+-----+-----+
| a₄ | a₃ | a₂ | a₁ | a₀ |
+-----+-----+-----+-----+-----+
| | | |
+-----+ XOR +-----+
| |
+-----------+
|
输出
更新规则：$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_L a_{n-L} \pmod{2}$
其中 $c_i \in {0,1}$ 是反馈多项式的系数。
周期性质：
ChaCha20是当前广泛使用的流密码算法，基于ARX设计（Addition, Rotation, XOR）：
状态矩阵（512位）：
常数0 常数1 常数2 常数3
密钥0 密钥1 密钥2 密钥3
密钥4 密钥5 密钥6 密钥7
计数器 随机数0 随机数1 随机数2
四分之一轮函数：
a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;
安全性分析：
Rule of thumb：现代流密码应避免线性结构，采用非线性函数和足够轮数确保安全性。
分组密码将固定长度的明文块映射为相同长度的密文块：
\[E_k: \{0,1\}^n \rightarrow \{0,1\}^n\]其中 $k$ 是密钥，$n$ 是分组长度。
理想分组密码：
Feistel网络是分组密码设计的重要范式：
输入: L₀, R₀
| |
| +-- F(R₀, K₁) --+
| |
+-------- XOR --------+
| |
R₁ L₁
数学描述： \(L_{i+1} = R_i\) \(R_{i+1} = L_i \oplus F(R_i, K_{i+1})\)
关键优势：
SPN网络是另一种重要的分组密码结构，AES即基于此设计：
明文
↓
SubBytes ← 非线性替换
↓
ShiftRows ← 线性扩散
↓
MixColumns ← 线性扩散
↓
AddRoundKey ← 密钥混合
↓
...重复多轮...
↓
密文
设计原则：
AES（Advanced Encryption Standard）是当前最重要的分组密码标准，支持128/192/256位密钥，固定128位分组长度。
状态表示： AES将128位输入组织为 $4 \times 4$ 字节矩阵：
\[\begin{bmatrix} s_{0,0} & s_{0,1} & s_{0,2} & s_{0,3} \\ s_{1,0} & s_{1,1} & s_{1,2} & s_{1,3} \\ s_{2,0} & s_{2,1} & s_{2,2} & s_{2,3} \\ s_{3,0} & s_{3,1} & s_{3,2} & s_{3,3} \end{bmatrix}\]SubBytes变换： 基于有限域 $\mathbb{F}_{2^8}$ 上的乘法逆元和仿射变换：
ShiftRows变换： 对状态矩阵的行进行循环左移：
MixColumns变换： 将每列视为 $\mathbb{F}_{2^8}$ 上的多项式，与固定多项式 $c(x) = 03x^3 + 01x^2 + 01x + 02$ 相乘：
\[\begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{bmatrix} \begin{bmatrix} s_{0,c} \\ s_{1,c} \\ s_{2,c} \\ s_{3,c} \end{bmatrix}\]Rule of thumb：AES的安全性来自四个变换的协同作用：SubBytes提供非线性性，ShiftRows和MixColumns确保扩散，AddRoundKey实现密钥混合。
抗差分密码分析：
抗线性密码分析：
当前最佳攻击：
分组密码只能处理固定长度的数据块，而实际应用中需要加密任意长度的消息。运行模式（Mode of Operation）定义了如何使用分组密码来加密长消息，同时保证安全性。
基本要求：
定义：最简单的运行模式，将消息分割为块，独立加密：
\[C_i = E_k(M_i)\]其中 $M_i$ 是第 $i$ 个明文块，$C_i$ 是对应的密文块。
ECB模式示意图：
M₁ M₂ M₃ ... Mₙ
↓ ↓ ↓ ↓
E_k E_k E_k ... E_k
↓ ↓ ↓ ↓
C₁ C₂ C₃ ... Cₙ
严重安全缺陷：
Rule of thumb：ECB模式绝不应用于实际系统，仅作教学演示。
核心思想：通过链接机制消除块间的独立性。
加密过程： \(C_0 = IV \text{ (初始化向量)}\) \(C_i = E_k(M_i \oplus C_{i-1})\)
解密过程： \(M_i = D_k(C_i) \oplus C_{i-1}\)
CBC模式示意图：
IV ⊕ M₁ C₁ ⊕ M₂ C₂ ⊕ M₃
↓ ↓ ↓
E_k E_k E_k
↓ ↓ ↓
C₁ C₂ C₃
安全性分析：
IV要求：
核心思想：将分组密码转换为流密码。
模式定义： \(C_i = M_i \oplus E_k(\text{CTR} + i)\)
其中 $\text{CTR}$ 是计数器初值。
CTR模式示意图：
CTR+1 CTR+2 CTR+3
↓ ↓ ↓
E_k E_k E_k
↓ ↓ ↓
⊕ ⊕ ⊕
↓ ↓ ↓
M₁ M₂ M₃
↓ ↓ ↓
C₁ C₂ C₃
优势特性：
安全性要求：
GCM是一种认证加密（Authenticated Encryption）模式，同时提供机密性和完整性保护。
数学基础： 基于有限域 $\mathbb{F}_{2^{128}}$ 上的多项式乘法，使用不可约多项式： \(f(x) = x^{128} + x^7 + x^2 + x + 1\)
认证标签计算： \(T = \text{GHASH}_H(A, C) \oplus E_k(J_0)\)
其中：
GHASH函数： \(\text{GHASH}_H(X_1, X_2, \ldots, X_m) = X_1 \cdot H^m + X_2 \cdot H^{m-1} + \cdots + X_m \cdot H\)
其中乘法在 $\mathbb{F}_{2^{128}}$ 中进行。
安全性保证：
Rule of thumb：对于需要认证的应用，优先选择GCM等认证加密模式，避免单独使用加密+MAC的组合。
输出反馈模式（OFB）： \(O_i = E_k(O_{i-1}), \quad O_0 = IV\) \(C_i = M_i \oplus O_i\)
密码反馈模式（CFB）： \(C_i = M_i \oplus E_k(C_{i-1}), \quad C_0 = IV\)
XEX模式族（XTS）： 专为磁盘加密设计，基于调整分组密码： \(C_i = E_{k_1}(M_i \oplus T_i) \oplus T_i\)
其中 $T_i$ 是与扇区和块位置相关的调整值。
语义安全性是现代密码学中最重要的安全概念之一，它形式化了”密文不泄露明文信息”的直观概念。
基于不可区分性的定义（IND-CPA）：
考虑以下实验 $\text{Exp}^{\text{IND-CPA}}_{\mathcal{A},\Pi}(n)$：
定义：加密方案 $\Pi$ 在选择明文攻击下具有语义安全性，当且仅当对于所有概率多项式时间敌手 $\mathcal{A}$：
\[\left|\Pr[\text{Exp}^{\text{IND-CPA}}_{\mathcal{A},\Pi}(n) = 1] - \frac{1}{2}\right| \leq \text{negl}(n)\]其中 $\text{negl}(n)$ 是可忽略函数。
定理：如果加密方案具有完美保密性，则它也具有语义安全性。
证明思路：
| 完美保密意味着 $\Pr[C = c | M = m_0] = \Pr[C = c | M = m_1]$ |
反向不成立：语义安全性是计算概念，而完美保密是信息论概念。
伪随机函数（PRF）： 函数族 $F = {F_k : {0,1}^n \rightarrow {0,1}^m}$ 是伪随机的，如果对于所有概率多项式时间区分器 $D$：
\[\left|\Pr[D^{F_k(\cdot)}(1^n) = 1] - \Pr[D^{f(\cdot)}(1^n) = 1]\right| \leq \text{negl}(n)\]其中 $k$ 均匀随机选择，$f$ 是真随机函数。
伪随机置换（PRP）： 类似定义，但要求函数是可逆的置换。
PRP/PRF切换引理： 对于 $n$ 位置换和 $q$ 次询问： \(\left|\text{Adv}^{\text{PRF}}_D - \text{Adv}^{\text{PRP}}_D\right| \leq \frac{q^2}{2^{n+1}}\)
Rule of thumb：当询问次数 $q \ll 2^{n/2}$ 时，可以安全地将PRP当作PRF使用。
定理：如果 $F$ 是伪随机置换，则CBC模式在随机IV下是IND-CPA安全的。
证明概要：
具体分析： 对于 $\ell$ 块消息和 $q$ 次询问，敌手的优势满足： \(\text{Adv}^{\text{IND-CPA}}_{\mathcal{A},\text{CBC}} \leq \text{Adv}^{\text{PRP}}_{\mathcal{B},F} + \frac{q^2\ell^2}{2^n}\)
定理：如果 $F$ 是伪随机函数，则CTR模式在随机计数器下是IND-CPA安全的。
关键洞察：CTR模式实质上将PRF转换为流密码。
安全性归约： \(\text{Adv}^{\text{IND-CPA}}_{\mathcal{A},\text{CTR}} \leq \text{Adv}^{\text{PRF}}_{\mathcal{B},F} + \frac{q\ell}{2^n}\)
其中第二项来自计数器碰撞概率。
认证加密的安全目标：
AEAD定义： 认证加密与附加数据（Authenticated Encryption with Associated Data）允许对部分数据进行认证但不加密。
正式语法：
其中 $N$ 是随机数（Nonce），$A$ 是附加认证数据。
安全性要求：
GCM的安全性界： 对于 $q$ 次加密询问和 $q_v$ 次验证询问： \(\text{Adv}^{\text{AE}}_{\mathcal{A},\text{GCM}} \leq \frac{0.5(q+q_v)^2}{2^{128}} + \text{Adv}^{\text{PRF}}_{\mathcal{B},\text{AES}}\)
Rule of thumb：对于需要认证的应用，使用经过正式分析的AEAD方案（如AES-GCM、ChaCha20-Poly1305）而非自己组合加密和MAC。
本章系统介绍了对称密码学的核心理论和实践技术，从Shannon的完美保密性理论出发，构建了现代对称密码学的完整理论框架。
完美保密性与信息论安全：
| Shannon定理建立了完美保密的充要条件：$ | \mathcal{K} | \geq | \mathcal{M} | $ |
计算安全性的转变：
流密码的精髓：
分组密码的数学结构：
Shannon完美保密条件： \(\Pr[M = m | C = c] = \Pr[M = m]\)
语义安全性定义： \(\left|\Pr[\text{Exp}^{\text{IND-CPA}}_{\mathcal{A},\Pi}(n) = 1] - \frac{1}{2}\right| \leq \text{negl}(n)\)
主要运行模式：
安全性界限：
| PRP/PRF切换：$ | \text{Adv}^{\text{PRF}} - \text{Adv}^{\text{PRP}} | \leq \frac{q^2}{2^{n+1}}$ |
安全设计原则：
实践经验法则：
本章展示了密码学理论如何指导实际系统设计：
历史演进的启示： 从Enigma机的机械设计到AES的数学精确性，对称密码学经历了从经验设计到理论指导的根本转变。Shannon的信息论为密码学提供了坚实的数学基础，而现代可证明安全理论则确保了密码系统的可靠性。
这一演进过程强调了一个重要观点：密码学不仅是工程技术，更是数学科学。只有深入理解其数学本质，才能设计出真正安全可靠的密码系统。
错误表现：
// 危险的做法
for each block Mi:
Ci = AES_encrypt(key, Mi)
问题根源：
调试技巧：
正确做法： 始终使用CBC、CTR、GCM等安全模式，绝不使用ECB模式处理敏感数据。
错误表现1（CBC模式）：
// 危险：固定IV
IV = "0000000000000000"
for each message:
ciphertext = CBC_encrypt(key, IV, message)
错误表现2（CTR模式）：
// 危险：计数器重用
counter = 0
for each message:
ciphertext = CTR_encrypt(key, counter, message)
// counter没有更新或重置为0
攻击后果：
调试方法：
正确实现：
// CBC: 每次生成随机IV
IV = random_bytes(16)
ciphertext = IV || CBC_encrypt(key, IV, message)
// CTR: 确保计数器/nonce唯一性
nonce = generate_unique_nonce() // 时间戳+随机数
ciphertext = nonce || CTR_encrypt(key, nonce, message)
常见错误：
// 极其危险
const char* key = "MySecretKey12345";
# 危险：可预测的密钥生成
key = hashlib.md5(password.encode()).digest()
// 危险：相同密钥用于不同目的
encryption_key = master_key
mac_key = master_key // 应该派生不同密钥
安全实践：
问题场景： CBC模式中，服务器返回不同的错误消息：
if (padding_valid):
return "Decryption successful"
else:
return "Padding error" // 泄露了填充状态！
攻击原理： 攻击者通过修改密文最后一个字节，观察服务器响应，逐步推导出明文。
防护措施：
时间攻击：
// 危险：非常数时间比较
bool verify_mac(const uint8_t* received, const uint8_t* expected, size_t len) {
for (size_t i = 0; i < len; i++) {
if (received[i] != expected[i]) {
return false; // 提前返回泄露信息
}
}
return true;
}
正确实现：
// 安全：常数时间比较
bool secure_compare(const uint8_t* a, const uint8_t* b, size_t len) {
uint8_t result = 0;
for (size_t i = 0; i < len; i++) {
result |= a[i] ^ b[i];
}
return result == 0;
}
调试技巧：
常见错误：
// 危险：伪随机数生成器用于密码学
srand(time(NULL));
for (int i = 0; i < 16; i++) {
key[i] = rand() % 256; // 可预测！
}
Debian OpenSSL漏洞复现： 2008年Debian系统中OpenSSL的PRNG只有32768种可能状态，导致SSH密钥可被暴力破解。
安全实践：
问题场景：
// 支持多种加密算法的系统
if (supports_aes_256):
use_aes_256()
elif (supports_aes_128):
use_aes_128()
else:
use_des() // 危险：弱算法作为备选
攻击方式： 攻击者伪造不支持强算法的信号，迫使系统使用弱算法。
防护策略：
密码学审计工具：
实践建议：
经验法则：
“任何自己实现的密码学算法都是错误的，除非经过广泛的同行评议和时间考验。优先使用成熟的密码学库，并严格按照官方文档使用。”