密码学 - 基础概念与对称密码

期中考点导引： 本次期中重点考查教材第 1 至 7 章。建议优先研读针对期中精炼的知识解析：第1至2章基础解析 · 第3至5章对称密码解析 · 第6至7章数论与RSA解析，并配套完成 31道重点课后习题详解。本篇原专题内容翔实，仍可作为深入理解 DES、AES 轮变换及认证加密模式的权威参考。

本篇对应《深入浅出密码学》第 1、2、3、4、5 章（书内第 1—140 页，PDF 第 14—153 页）。返回学习导航。

各节穿插 9 道完整例题，先给条件，再展示计算或判断过程。可以顺着正文学习，也可以遮住解答自行推演；文末问题用于复习，跨主题计算题另见前7章指定课后题详解。

⭐ 本篇核心问题：通信双方在完全公开、可能被窃听和篡改的信道上，如何利用共享秘密实现大规模数据的高效、保密传输？算法如何通过“混淆”与“扩散”抵抗统计分析、代数求解与差分/线性密码分析？

---

一、密码学基石：安全目标与攻击模型

1.1 经典安全属性与现实误区

在设计或分析任何系统时，最常犯的错误就是笼统地说一句“我们把数据加密一下就安全了”。“加密”只解决机密性，它无法自动保证真实性、完整性或防止重放。

安全属性	核心防御目标	典型破坏手段	对应密码学原语
机密性（Confidentiality）	防止未授权的第三方读取消息内容	网络窃听、内存嗅探、流量抓包	对称加密（AES/ChaCha20）、公钥加密
完整性（Integrity）	确保消息在传输中未被篡改、删减或插入	翻转密文比特、篡改网络数据包	消息认证码（MAC）、数字签名、认证加密（AEAD）
真实性（Authenticity）	确认消息确由声称的实体发出（防冒充）	伪造数据包来源、冒充服务器	实体认证握手、消息认证码、数字签名
抗抵赖性（Non-repudiation）	发送方事后无法否认其曾经生成并发送该消息	恶意撤销交易、否认合同签署	数字签名（具有公钥可公开验证性）
新鲜性（Freshness）	防止合法的历史旧消息被原样重新发送	重放旧的转账报文、重放认证握手包	时间戳、随机挑战数（Nonce）、严格递增序号

💡 转账直观案例：假设 Alice 发送转账指令 向 Bob 转账 100 元。

• 如果只加密（没有 MAC 或数字签名），攻击者 Eve 即使看不懂密文，只要知道金额字段的位置，就可以通过翻转密文比特篡改金额（延展性攻击）；
• 即使使用了完美的认证加密，Eve 无法篡改内容，但如果协议缺少新鲜性验证，Eve 只需将截获的合法密文原封不动地向银行服务器连续重放 100 次，银行就会扣款 100 次！因此，安全是协议维度的系统工程。

1.2 柯克霍夫原则（Kerckhoffs's Principle）

1883 年，奥古斯特·柯克霍夫提出密码学最核心的设计准则：

即使密码系统的所有机制（包括算法、实现逻辑、硬件结构）都被公开，系统的安全性应当依赖密钥保密，而不依赖算法保密。这个原则本身不保证无条件安全。

为什么绝不能依赖“保密算法”（Security through Obscurity）？

1. 现实中算法根本无法长久保密：算法会被编译进二进制程序、烧录进芯片、部署在千万台终端设备上，通过逆向工程、固件提取或内存 Dump 很容易还原；
2. 更换代价不对称：如果算法被攻破，必须重新设计、验证并升级全网软件和硬件，代价极其高昂；而密钥可以按用户或会话更换；实际撤销、重新分发和处置历史泄露仍需要相应流程；
3. 开源公开审阅带来韧性：公开算法可以接受独立分析，但公开不等于安全：DES 的 56 位密钥已不足以抵抗穷举。

1.3 现代密码分析的四种攻击模型

评估一个密码体制是否安全，必须明确攻击者拥有的能力边界（Capabilities）。密码学根据攻击者获取的信息量，划分出由弱到强的四级阶梯：

flowchart LR
    COA["1. 唯密文攻击 COA"] --> KPA["2. 已知明文攻击 KPA"]
    KPA --> CPA["3. 选择明文攻击 CPA"]
    CPA --> CCA["4. 选择密文攻击 CCA"]

1. 唯密文攻击（Ciphertext-Only Attack, COA）：
   • 攻击者手头仅有截获的一批密文 $C_1, C_2, \dots$。
   • 这是攻击者能力最弱的模型。现代密码体制抵御 COA 是绝对的最低底线。
2. 已知明文攻击（Known-Plaintext Attack, KPA）：
   • 攻击者掌握若干对已知的明文和对应密文 $(P_1, C_1), (P_2, C_2), \dots$。
   • 现实中极其普遍：网络协议通常有固定头部（如 HTTP 的 GET / HTTP/1.1，TLS 记录头）、文件有固定魔数（如 PDF 开头 %PDF-）。算法必须保证已知明文对无法帮助推导后续密钥或其他未知消息。
3. 选择明文攻击（Chosen-Plaintext Attack, CPA）：
   • 攻击者拥有加密黑盒的访问权，可以自由挑选任意明文并获取对应的密文。
   • 例如：公钥密码中，公钥完全公开，攻击者可以在本地用目标公钥加密任意自己挑选的明文；又如攻击者发送一封已知邮件诱使安全网关加密转发。
4. 选择密文攻击（Chosen-Ciphertext Attack, CCA / CCA2）：
   • 攻击者拥有解密黑盒的查询权，可以向解密端提交任意构造的密文，并观察其解密结果或错误反馈（但不允许直接查询目标密文自身）。
   • 现实案例：Padding Oracle 填充预言机攻击。现代公钥和对称标准通常要求达到适应性选择密文安全性（IND-CCA2）。

---

二、古典密码的兴衰与一次一密（OTP）

2.1 统计学击穿单表替换

单表替换密码（Monoalphabetic Substitution）将字母表的每个字母一对一映射到打乱的字母。由于 26 个字母有 $26! \approx 4 \times 10^{26} \approx 2^{88}$ 种不同排列，曾一度被认为“密钥空间巨大，不可能暴力穷举”。

然而，自然语言具有极强的统计规律冗余：

• 在英文中，字母 E 的出现频率高达约 $12.7\%$，其次是 T（$9.1\%$）、A（$8.2\%$）；字母对 TH、HE、IN 的出现频率也高度固定；
• 攻击者无需遍历 $26!$ 种映射，只需统计长密文中的字符频率，将最高频字符尝试映射为 E，配合词根特征即可在数分钟内破译全文。

教训：密钥空间大仅仅是安全的必要条件，绝非充分条件！ 如果算法无法抹除明文的统计冗余特征，安全性将彻底破产。

2.2 仿射密码与数学可逆性

仿射密码（Affine Cipher）在模 26 下对字母序号（$A=0, B=1, \dots, Z=25$）进行一次线性变换：

$$C = e_k(P) = (a \cdot P + b) \bmod 26$$

解密公式为：

$$P = d_k(C) = a^{-1} \cdot (C - b) \bmod 26$$

为什么必须要求 $\gcd(a, 26) = 1$？

因为解密必须求解乘法逆元 $a^{-1} \pmod{26}$。如果 $a$ 与 26 不互素（如取 $a = 4$ 或 $a = 13$）：

• 设 $a = 2, b = 0$，加密 $P_1 = 0$（字母 A）得到 $C = 0$；加密 $P_2 = 13$（字母 N）得到 $C = (2 \times 13) \bmod 26 = 0$；
• 不同的明文被映射到了同一个密文上！发生了信息丢失（坍塌），解密端根本无法唯一还原原意。
• 模 26 下与 26 互素的数字仅有 $\varphi(26) = \varphi(2) \times \varphi(13) = 1 \times 12 = 12$ 个。总密钥数仅为 $12 \times 26 = 312$ 种，既能被一秒穷举，也完全无法抵御频率分析。

例题 1：仿射密码怎样加密、解密，又怎样被反推出密钥？

题目。 采用 $A=0,\ldots,Z=25$，密钥为 $(a,b)=(5,8)$。加密 CAT，再从密文恢复原文。如果攻击者另外知道 A → I、B → N 两组对应关系，能否求出密钥？

第一步：确认这把密钥能解密。 $\gcd(5,26)=1$，所以 5 有模 26 的乘法逆元。由于 $5\times21=105=4\times26+1$，得到 $5^{-1}\equiv21\pmod{26}$。

第二步：逐字母加密。 把字母换成数字，再代入 $C=(5P+8)\bmod26$：

明文字母	数值 $P$	代入计算	密文字母
C	2	$5\times2+8=18$	S
A	0	$5\times0+8=8$	I
T	19	$5\times19+8=103\equiv25$	Z

因此密文为 SIZ。重复字母仍会得到重复密文字母，仿射变换没有消除这种统计特征。

第三步：解密时先减，再乘逆元。

$$P=21(C-8)\bmod26$$

S 对应 18，得到 $21(18-8)=210\equiv2$，即 C；I 对应 8，得到 0，即 A；Z 对应 25，得到 $21(25-8)=357\equiv19$，即 T。

第四步：站到攻击者一边。 已知 A → I 意味着 $0a+b\equiv8$，于是 $b=8$；已知 B → N 意味着 $a+b\equiv13$，于是 $a=5$。本例只凭两组已知明密文就恢复了密钥。

易错点。 模运算里的“除以 5”是乘以 21，不能对普通整数除法结果取整。两组明密文也不是在所有情况下都能唯一确定仿射密钥：消元后仍要检查明文差值是否可逆；本例差值是 1，恰好可逆。

对应教材 §1.4.4（书内第 18—19 页，PDF 第 31—32 页）；本题参数与消息为自设。

2.3 完美的代价：香农一次一密（One-Time Pad）

1917 年 Vernam 提出，并于 1949 年由香农（Claude Shannon）严格从信息论上证明：一次一密（OTP）是理论上绝对无法攻破的（无条件安全 / 完美保密性 Perfect Secrecy）。

完美保密性的数学定义

在观察到密文 $C = c$ 后，攻击者推断明文为特定 $M = m$ 的后验概率，与先验概率完全相等（即密文没有透露任何关于明文的信息）：

$$P(M = m \mid C = c) = P(M = m)$$

为什么成立？

设明文长度为 $n$ 位，密钥 $K$ 是由物理真随机源独立生成的 $n$ 位比特串，每个候选密钥选中的概率均为 $2^{-n}$。加密为按位异或：

$$C = M \oplus K \iff K = M \oplus C$$

对于任意给定的明文 $m$ 和任意截获的密文 $c$，在整个密钥空间中，有且仅有一把唯一的密钥 $k = m \oplus c$ 能够将 $m$ 加密成 $c$。
由于所有 $2^n$ 把密钥出现的概率完全均等（$P(K = k) = 2^{-n}$）：

$$P(C = c \mid M = m) = P(K = m \oplus c) = 2^{-n}$$

根据全概率公式：

$$P(C = c) = \sum_{m'} P(M = m') P(C = c \mid M = m') = 2^{-n} \sum_{m'} P(M = m') = 2^{-n}$$

带入贝叶斯公式：

$$P(M = m \mid C = c) = \frac{P(C = c \mid M = m) P(M = m)}{P(C = c)} = \frac{2^{-n} P(M = m)}{2^{-n}} = P(M = m)$$

这说明观察密文不会改变攻击者对各明文的先验判断。每个明文的后验概率等于它自己的先验概率，不意味着不同明文彼此等概率。 如果某条消息原本更可能出现，观察密文后它仍然更可能；密文没有增加这方面的信息。这里讨论固定长度消息。

观察密文前 · 先验

消息 A

60%

消息 B

30%

消息 C

10%

观察某个密文 c 后 · 后验

消息 A

60%

消息 B

30%

消息 C

10%

A 仍比 C 更可能，为什么还叫完美保密？

因为这份偏好在观察密文前就存在。密文没有让攻击者多知道任何事；完美保密要求前后不变，而不是把三根柱子变成一样高。

教学设定：三条消息长度相同，概率为 60%、30%、10%；密钥独立、均匀、等长且仅使用一次。

OTP 无法在工程中普及的三大枷锁

1. 真随机要求：密钥必须是完全不可预测的真物理随机数（算法生成的伪随机数不满足）；
2. 等长密钥分发困境：传输 10 TB 数据，必须先安全分发 10 TB 的秘密密钥——如果双方已经拥有能安全传递 10 TB 密钥的信道，为什么不直接用该信道传输数据？
3. 一次一密绝不可复用：每段密钥使用一次后必须彻底销毁。

2.4 密钥流复用（Two-Time Pad）的毁灭性推导

如果通信方偷懒，将同一段密钥流 $S$ 使用了两次：

$$C_1 = P_1 \oplus S,\qquad C_2 = P_2 \oplus S$$

攻击者只需将截获的两段密文进行异或：

$$C_1 \oplus C_2 = (P_1 \oplus S) \oplus (P_2 \oplus S) = P_1 \oplus P_2$$

秘密密钥流 $S$ 被瞬间完全抵消！ 密文异或直接退化为两段明文的异或。

密文异或给出了两条明文之间的关系。结合已知片段、格式和语言冗余，攻击者可以进一步推断；但仅凭一次异或通常不能唯一恢复两条消息：

• 在 ASCII 中，英文字母的二进制最高位为 0，大写字母是 0x41—0x5A，小写字母是 0x61—0x7A，而空格字符（Space）为 0x20（即 00100000）；
• 当任何一个英文字母与空格异或时，结果恰好是该字母的大小写反转（即第 6 比特翻转，ASCII 落在 0x41—0x5A 或 0x61—0x7A 之间）；
• 攻击者可以把字母范围内的结果作为“其中一侧可能是空格”的线索，再结合上下文检验。仅凭这个现象不能确定空格在哪一侧，也不能保证恢复全部明文。

同时，异或加密具有延展性（Malleability）：攻击者虽然不知道 $P$，但若将密文第 $i$ 位翻转，解密后明文的第 $i$ 位必然精确翻转。OTP 毫无完整性保障。

例题 2：复用密钥流后，已知一条消息会泄露什么？

题目。 两条等长消息为 AB、CD。它们的 ASCII 十六进制编码分别为 41 42、43 44，错误地使用同一段密钥流 10 20。求两条密文；再假设攻击者只知道两条密文和第一条明文，恢复第二条消息。

第一步：逐字节异或。 本题表中每个数都用十六进制表示。

位置	$P_1$	$P_2$	密钥流 $S$	$C_1=P_1\oplus S$	$C_2=P_2\oplus S$
第 1 字节	41	43	10	51	53
第 2 字节	42	44	20	62	64

第二步：消去未知密钥流。 攻击者并不需要事先知道表中的 $S$：

$$C_1\oplus C_2=(\texttt{51 62})\oplus(\texttt{53 64})=\texttt{02 06}=P_1\oplus P_2$$

第三步：用已知明文恢复另一条。

$$P_2=P_1\oplus(C_1\oplus C_2)=(\texttt{41 42})\oplus(\texttt{02 06})=\texttt{43 44}$$

结果就是 CD。也可以先求 $S=C_1\oplus P_1=\texttt{10 20}$，再解密 $C_2$，两种做法等价。

易错点。 如果不知道任何明文，只能直接得到 02 06 这个异或关系，不能据此声称两条消息已被唯一还原。如果仅知道第一条消息的一个字节，也只能直接恢复另一条在同一密钥流位置上的一个字节。错误复用同一密钥流的 CTR 也会出现这个问题。

对应教材第 2 章的异或加解密与一次一密机制；本题为自设的密钥流复用对照例子。

三、序列密码（流密码）与伪随机数生成

由于 OTP 的真随机长密钥无法落地，现代密码学采取了折中路线——序列密码（Stream Cipher）：

用双方预先共享的短种子密钥（Seed Key，如 128 位），通过密码学安全的伪随机数生成器（CSPRNG），在收发两端同步在算法规定的输出限制内展开成长的、看似随机的伪随机密钥流（Keystream）$s_0, s_1, s_2, \dots$，再逐位与明文异或。

共享主密钥 K + 每次独立的 Nonce / IV
              │
              ▼
   ┌──────────────────────┐
   │ 伪随机数生成器 CSPRNG │ ───► 密钥流 s0, s1, s2, ...
   └──────────────────────┘                 │
                                            ▼
                          明文 x0, x1, ... ──⊕──► 密文 y0, y1, ...

3.1 线性反馈移位寄存器（LFSR）

在硬件设计中，最简单、最高效生成长序列的方式是 LFSR。
一个 $m$ 级的移位寄存器包含 $m$ 个触发器（$s_{m-1}, \dots, s_0$）。每过一个时钟脉冲，状态右移一位，最右端输出一位密钥流，最左端则由预设的某些特定“抽头”（Tap）进行异或累加作为新的反馈输入：

$$s_{i+m} = p_0 s_i \oplus p_1 s_{i+1} \oplus \dots \oplus p_{m-1} s_{i+m-1}$$

其中反馈多项式 $P(x) = x^m + p_{m-1}x^{m-1} + \dots + p_1 x + p_0$。

• 最大周期：如果反馈多项式是 $GF(2)$ 上的本原多项式（Primitive Polynomial），且初始状态不全为 0，LFSR 的输出序列周期可达到最大值 $2^m - 1$（全 0 状态会死锁输出全 0，故排除）。

3.2 为什么 LFSR 绝不能单独用于加密？

很多非专业开发者看到“周期长达 $2^{64}-1$、0/1 统计极其均匀”，就误以为 LFSR 足够安全。这是混淆了“统计随机性”与“密码学不可预测性”！

LFSR 的致命弱点在于其纯线性的代数结构：

• 递推式本质是模 2 线性方程。如果攻击者通过已知明文攻击获取了 $2m$ 位的连续密钥流输出： $$s_0, s_1, \dots, s_{m-1}, s_m, \dots, s_{2m-1}$$
• 攻击者可以列出关于 $m$ 个未知系数 $p_0, p_1, \dots, p_{m-1}$ 的线性方程组： $$\begin{bmatrix} s_0 & s_1 & \dots & s_{m-1} \\ s_1 & s_2 & \dots & s_m \\ \vdots & \vdots & \ddots & \vdots \\ s_{m-1} & s_m & \dots & s_{2m-2} \end{bmatrix} \begin{bmatrix} p_0 \\ p_1 \\ \vdots \\ p_{m-1} \end{bmatrix} = \begin{bmatrix} s_m \\ s_{m+1} \\ \vdots \\ s_{2m-1} \end{bmatrix} \pmod 2$$
• 若系数矩阵满秩，可以用高斯消元求出反馈系数；若存在冗余，不能仅凭方程条数断言原硬件抽头唯一。更一般地，Berlekamp-Massey 算法能从足够的连续输出恢复最短线性递推关系（线性复杂度为 $L$ 时，至多需 $2L$ 位），从而预测后续输出。

📌 核心结论：单纯的线性反馈是脆弱的。安全的密码学原语必须引入非线性组件（Non-linear Components），彻底打破线性方程组的可解性。

例题 3：六个输出比特，怎样反推出三级 LFSR？

题目。 已知一个三级 LFSR 满足

$$s_{i+3}=p_0s_i\oplus p_1s_{i+1}\oplus p_2s_{i+2}$$

反馈系数未知，观察到连续输出 $(s_0,\ldots,s_5)=(1,0,0,1,0,1)$。求 $p_0,p_1,p_2$，并预测接下来的三个比特。

第一步：按时间顺序列方程。 不要把“初始状态写在纸上从左到右的顺序”与输出编号混在一起；直接按题目给出的递推式代入：

代入哪一步	方程	得到的信息
$i=0$，计算 $s_3$	$1=p_0\cdot1\oplus p_1\cdot0\oplus p_2\cdot0$	$p_0=1$
$i=1$，计算 $s_4$	$0=p_0\cdot0\oplus p_1\cdot0\oplus p_2\cdot1$	$p_2=0$
$i=2$，计算 $s_5$	$1=p_0\cdot0\oplus p_1\cdot1\oplus p_2\cdot0$	$p_1=1$

因此递推关系为 $s_{i+3}=s_i\oplus s_{i+1}$，按本文的系数约定，反馈多项式为 $x^3+x+1$。

第二步：接着向前算。

$$\begin{aligned} s_6&=s_3\oplus s_4=1\oplus0=1,\\ s_7&=s_4\oplus s_5=0\oplus1=1,\\ s_8&=s_5\oplus s_6=1\oplus1=0. \end{aligned}$$

接下来的三个比特是 110。注意最后一步已经用到了刚算出的 $s_6$。

第三步：解释攻击者如何拿到输出。 如果 LFSR 被直接用作密钥流生成器，已知明文与密文给出 $s_i=P_i\oplus C_i$。所以这里的“观察到输出”可以来自已知明文攻击，而不需要读取寄存器硬件。

易错点。 这里的三个方程确实独立，反馈系数才被唯一解出。一般情形需检查秩或恢复最短递推关系，不能只数“方程数等于未知数数目”。即使序列能遍历很多非零状态，这种线性可预测性仍然存在。

对应教材 §2.3.1—§2.3.2（书内第 40—43 页，PDF 第 53—56 页）；本题的输出与列方程过程为自设。

3.3 现代硬件流密码：Trivium

为了在资源极度受限的嵌入式/IoT 硬件上实现轻量且安全的流加密，eSTREAM 项目选出了 Trivium 算法。

flowchart LR
    subgraph trivium_state ["Trivium 288 位内部状态"]
        A["寄存器 A: 93 位"] -->|非线性 AND 与反馈| B["寄存器 B: 84 位"]
        B -->|非线性 AND 与反馈| C["寄存器 C: 111 位"]
        C -->|非线性 AND 与反馈| A
    end
    A --> Out(("XOR"))
    B --> Out
    C --> Out
    Out --> Stream["输出密钥流比特"]

• 非线性机制：Trivium 的核心创新在于寄存器抽头更新时，除了异或（线性加法），还引入了 按位与（AND） 操作（例如 $s_i \oplus (s_j \land s_k)$）。在布尔代数中，AND 相当于代数乘法，引入了二次非线性项，使得攻击者无法构建线性方程组。
• 1152 步空转预热（Warm-up）：装载 80 位密钥与 80 位 IV 后，系统必须先空转执行 $4 \times 288 = 1152$ 步而不产生输出。这是为了让密钥和 IV 经过充分的非线性级联混淆，使初始比特彻底“雪崩”，抹除输入之间的任何局部关联。

---

四、分组密码核心架构与 DES / Feistel 网络

分组密码（Block Cipher）将固定长度的明文分组（如 64 位或 128 位）转换为等长的密文分组。香农指出，优秀的分组密码必须具备两大支柱：

1. 混淆（Confusion）：使密文与密钥之间的统计关系尽可能复杂、非线性，阻止通过代数分析反解密钥（通常由 S 盒代换 实现）；
2. 扩散（Diffusion）：使明文的每一位和密钥的每一位影响尽可能多的密文位，实现“牵一发而动全身”的雪崩效应（通常由 P 置换 / 行移位 / 列混淆 实现）。

4.1 Feistel 网络的精妙：轮函数不可逆为何整体可逆？

1970 年代，IBM 的 Horst Feistel 提出了著名的 Feistel 结构。其最天才的设计在于：即使内部的核心变换轮函数 $f(R, K)$ 是一个不可逆的单向压缩映射，整个网络在数学上依然天然绝对可逆！

正向加密计算

将输入分组均分为左半边 $L$ 和右半边 $R$。第 $i$ 轮迭代规则为：

$$L_i = R_{i-1}$$ $$R_i = L_{i-1} \oplus f(R_{i-1}, K_i)$$

逆向解密推导

解密端收到第 $i$ 轮的输出 $(L_i, R_i)$，如何反推 $(L_{i-1}, R_{i-1})$？

1. 由定义直接得出原右半边： $$R_{i-1} = L_i$$
2. 将 $R_{i-1} = L_i$ 代入异或等式： $$R_i = L_{i-1} \oplus f(L_i, K_i)$$ 两边同时异或 $f(L_i, K_i)$，由异或自反性（$X \oplus Y \oplus Y = X$）： $$L_{i-1} = R_i \oplus f(L_i, K_i)$$

🔍 关键顿悟：注意看！在求 $L_{i-1}$ 时，我们调用的依然是正向的轮函数 $f$！送入 $f$ 的输入正是完好无损保存在 $L_i$ 中的原右半边。我们根本不需要求轮函数 $f$ 的逆函数 $f^{-1}$！ 这意味着 $f$ 内部可以任意使用丢弃信息、非单射的极度复杂的代换（如 DES 的 6 位压缩到 4 位的 S 盒）。

用 4 位玩具数据走回来

设 L = 1010，R = 1100，本轮 f(R,K) = 0110，则输出为 (1100, 1100)。恢复时先取 R = 左输出 = 1100，再算 L = 右输出 ⊕ f(1100,K) = 1100 ⊕ 0110 = 1010。只重算 f，无需求 f 的逆。

图中交叉线不相连。示例中的 4 位数据用于展示异或；DES 的每一半实际是 32 位。

例题 4：用不可逆的轮函数，完成两轮 Feistel 加密再解密

题目。 每半块只有 4 位，规定玩具轮函数 $f(R,K)=R\mathbin{\&}K$，其中 $\&$ 是按位与。输入 $L_0=1010$、$R_0=1100$，两轮密钥 $K_1=0110$、$K_2=1001$。求 $(L_2,R_2)$，再恢复输入。

先看轮函数。 固定 $K_1=0110$ 时，$f(0000,K_1)=f(1000,K_1)=0000$，不同输入得到同一输出，因此这个 $f$ 不可逆。但 Feistel 逆运算需要的只是重新计算 $f$。

正向：每轮先计算，再交换。

轮次	输入 $(L,R)$	$f(R,K)$	新左半 $L'=R$	新右半 $R'=L\oplus f(R,K)$
第 1 轮	(1010, 1100)	1100 & 0110 = 0100	1100	1010 XOR 0100 = 1110
第 2 轮	(1100, 1110)	1110 & 1001 = 1000	1110	1100 XOR 1000 = 0100

得到 $(L_2,R_2)=(1110,0100)$。本题输出就是第二轮的左右状态，未额外增加 DES 最后的交换或置换。

逆向：从第 2 轮开始，先找回原右半。

$$\begin{aligned} R_1&=L_2=1110,\\ L_1&=R_2\oplus f(L_2,K_2)=0100\oplus1000=1100;\\[2pt] R_0&=L_1=1100,\\ L_0&=R_1\oplus f(L_1,K_1)=1110\oplus0100=1010. \end{aligned}$$

原输入完整恢复。逆向先用 $K_2$，再用 $K_1$，而 $f$ 始终还是同一个按位与函数。

这里一直沿用加密时的名字，从下标 2 倒推到 0。老师解密图里的 $L_0^d$、$R_0^d$ 则是给解密过程重新编号，下标从 0 向上数。下面接着用同一组数字，把这两种写法对起来。

易错点。 不能一边更新左半变量，一边用更新后的值计算右半；应先保留本轮的两个输入。“结构可逆”也不等于“密码安全”：这个按位与玩具函数只用来演示可逆性，不具备 DES 轮函数的安全设计。

对应教材 §3.2 与 §3.4 的 Feistel 结构和解密思路；4 位参数与轮函数为自设。

4.2 DES 算法全流程剖析

DES（Data Encryption Standard）于 1977 年被确立为美国国家标准，采用 16 轮 Feistel 结构。

flowchart TD
    In["64 位明文"] --> IP["初始置换 IP"]
    IP --> Split["拆分为 L0 和 R0 各 32 位"]
    Split --> Round1["第 1 轮 Feistel: 轮密钥 K1"]
    Round1 --> Dots["..."]
    Dots --> Round16["第 16 轮 Feistel: 轮密钥 K16"]
    Round16 --> Swap["左右交换并拼接: R16 ∥ L16"]
    Swap --> FP["逆初始置换 IP⁻¹"]
    FP --> Out["64 位密文"]

DES 解密：$L_0^d$、$R_0^d$ 到底是哪两块？

看到这组符号，先不要急着背公式。上标 $d$ 是 decryption（解密）的标签，不是乘方；下标表示在各自的过程中，已经做完几轮。 本节不带 $d$ 的符号都指加密过程。

记号	读成人话
$(L_0,R_0)$	明文经过 $IP$ 后，加密尚未开始第一轮时的左右两半
$(L_{16},R_{16})$	加密做完 16 轮、尚未额外交换时的左右两半
$(L_0^d,R_0^d)$	密文经过 $IP$ 后，解密尚未开始第一轮时的左右两半
$(L_1^d,R_1^d)$	解密做完第 1 轮后的左右两半

为什么解密的左半，等于加密最后的右半？ 回头看加密流程：16 轮结束后，还要额外交换左右两半，再做 $IP^{-1}$。设明文为 $M$、密文为 $C$，$\parallel$ 表示拼接，则：

$$C=IP^{-1}(R_{16}\parallel L_{16}).$$

解密先对密文做 $IP$，恰好抵消加密最后的 $IP^{-1}$：

$$IP(C)=R_{16}\parallel L_{16}.$$

把当前左边的 32 位叫作 $L_0^d$，右边的 32 位叫作 $R_0^d$，自然得到：

$$\boxed{(L_0^d,R_0^d)=(R_{16},L_{16})}$$

同一份数据，在加密终点和解密起点有不同名字。 “解密的左半”只表示它现在放在左边，不代表它原来也是加密的左半。这里的交换已经发生在加密结尾；解密做完 $IP$ 后，直接按当前位置命名即可，不要再额外交换一次。

接着例题 4：加上最后交换，用解密记号完整算一遍

仍用 2 轮、每半块 4 位的教学模型，轮函数仍是 $f(R,K)=R\mathbin{\&}K$。本次补上 DES 的“最后额外交换”，省略外围的 $IP$、$IP^{-1}$，专门观察轮运算与左右位置。真实 DES 是 16 轮、每半块 32 位，轮函数也不是按位与。

已知输入与轮密钥：

$$(L_0,R_0)=(1010,1100),\qquad K_1=0110,\quad K_2=1001.$$

第一步：回看加密结果，确定解密从哪里开始。 所有四位数字都表示二进制位串，$\oplus$ 表示逐位异或。

加密进度	左半	右半
开始	$1010$	$1100$
第 1 轮，用 $K_1$	$1100$	$1010\oplus(1100\mathbin{\&}0110)=1110$
第 2 轮，用 $K_2$	$1110$	$1100\oplus(1110\mathbin{\&}1001)=0100$
最后额外交换	$0100$	$1110$

所以解密开始时，拿到的是：

$$(L_0^d,R_0^d)=(0100,1110)=(R_2,L_2).$$

注意：这里的下标 0 只表示“解密还没做第一轮”，绝不是说已经回到原始明文。

第二步：解密第 1 轮，先用最后一把密钥 $K_2$。 解密仍使用和加密相同的轮结构：新左等于旧右，新右等于旧左异或轮函数输出。

$$\begin{aligned} L_1^d&=R_0^d=1110,\\[4pt] R_1^d&=L_0^d\oplus f(R_0^d,K_2)\\ &=0100\oplus(1110\mathbin{\&}1001)\\ &=0100\oplus1000\\ &=1100. \end{aligned}$$

于是：

$$\boxed{(L_1^d,R_1^d)=(1110,1100)=(R_1,L_1)}$$

对照加密表：已经退回加密第 1 轮的那两块数据，只是左右位置相反。 能退回去，是因为加密第 2 轮把 $1100$ 与 $1000$ 异或得到 $0100$；解密又算出了同一个 $1000$，再异或一次便抵消了：

$$\underbrace{(1100\oplus1000)}_{0100}\oplus1000=1100.$$

这也解释了为什么必须先用 $K_2$：要抵消最后一轮，就得重新生成最后一轮用过的那个轮函数输出，无需求 $f^{-1}$。

第三步：解密第 2 轮，再用 $K_1$。

$$\begin{aligned} L_2^d&=R_1^d=1100,\\[4pt] R_2^d&=L_1^d\oplus f(R_1^d,K_1)\\ &=1110\oplus(1100\mathbin{\&}0110)\\ &=1110\oplus0100\\ &=1010. \end{aligned}$$

得到 $(L_2^d,R_2^d)=(1100,1010)=(R_0,L_0)$，最后再额外交换一次：

$$(1100,1010)\xrightarrow{\text{最后交换}}\boxed{(1010,1100)}.$$

原输入恢复。整个过程都在用同一个轮函数、同一套轮结构，只把轮密钥顺序反了过来。

从两轮例题回到真正的 16 轮 DES

解密进度	使用的轮密钥	对应加密时的状态
开始，已经做过 $IP$	尚未使用	$(L_0^d,R_0^d)=(R_{16},L_{16})$
做完第 1 轮	$K_{16}$	$(L_1^d,R_1^d)=(R_{15},L_{15})$
做完第 2 轮	$K_{15}$	$(L_2^d,R_2^d)=(R_{14},L_{14})$
$\cdots$	$\cdots$	$\cdots$
做完第 16 轮	$K_1$	$(L_{16}^d,R_{16}^d)=(R_0,L_0)$

也就是：

$$\boxed{(L_j^d,R_j^d)=(R_{16-j},L_{16-j})},\qquad 0\le j\le16.$$

解密每向前做一轮，就退回加密的一轮；过程中左右位置相反。解密做完 16 轮后，最后交换得到 $L_0\parallel R_0$，再做 $IP^{-1}$，才恢复原明文：

$$M=IP^{-1}(L_0\parallel R_0).$$

和前面的“逆向推导”有什么区别？ 前面保留加密的名字，直接算出上一轮的 $(L_{i-1},R_{i-1})$；这里为了复用加密轮结构，给解密状态另起名字，并把同一对数据按相反的左右位置保存。两者恢复的是同一份数据，不能把两套命名里的“左半”直接当成同一个变量。

合上笔记检查一下： 解密做完第 3 轮，$(L_3^d,R_3^d)$ 对应加密的哪两块？下一轮该用哪把密钥？为什么 $(L_{16}^d,R_{16}^d)$ 还不能直接拼起来当明文？

展开核对

$(L_3^d,R_3^d)=(R_{13},L_{13})$，下一轮使用 $K_{13}$。做完第 16 轮时得到的是 $(R_0,L_0)$，还要交换左右，并用 $IP^{-1}$ 撤销明文最初经历的 $IP$。

记号与流程对应教材 §3.4、图 3-13（书内第 65 页，PDF 第 78 页）；两轮、4 位数据与按位与轮函数为教学简化，沿用例题 4。

参数辨析（考试极易混淆点）

参数项	数值	易错与辨析
分组长度	64 位	每次处理 8 字节
输入密钥总长度	64 位	包含 8 个奇校验位（第 8, 16, 24, ..., 64 位）
有效安全密钥长度	56 位	校验位不提供任何密钥熵，真实穷举空间仅 $2^{56}$
迭代轮数	16 轮	每轮使用一把由主密钥扩展出的子密钥
单轮子密钥长度	48 位	经 PC-2 压缩选出

轮函数 $f(R_{i-1}, K_i)$ 的四步实现

$$f(R, K) = P\Big(S\big(E(R) \oplus K\big)\Big)$$

1. 扩展置换 $E$（32 位 $\to$ 48 位）：将 32 位右半部分成 8 组（每组 4 位），每组左右借入相邻组的边界位扩充为 6 位。这不仅使尺寸与 48 位轮密钥匹配，更让一个比特的变化能同时波及两个相邻 S 盒。
2. 轮密钥加：与当前轮的 48 位子密钥 $K_i$ 进行按位异或。
3. S 盒非线性代换（48 位 $\to$ 32 位）：
   • 核心防线！由 8 个不同的 S 盒（$S_1$ 到 $S_8$）并行工作，每个 S 盒输入 6 位、输出 4 位。
   • 查表映射规则：设 6 位输入为 $b_1 b_2 b_3 b_4 b_5 b_6$。
     • 行号（Row）：由首尾两位拼接组成 $b_1 b_6$（二进制取值 0 到 3）；
     • 列号（Col）：由中间四位拼接组成 $b_2 b_3 b_4 b_5$（二进制取值 0 到 15）；
     • 取出表中 Row 行 Col 列的 4 位数值输出。
4. P 盒置换（32 位 $\to$ 32 位）：对 8 个 S 盒的 32 位输出进行固定的比特位置重排，确保当前轮某一个 S 盒的局部扩散在下一轮被分散送入多个不同的 S 盒。

例题 5：DES 的 6 位输入，到底怎样查 S 盒？

题目。 送入 $S_1$ 的输入为 100101。已知标准 $S_1$ 表中，行号 3、列号 2 的值为 8。求 4 位输出。所有行列编号从 0 开始。

第一步：标清每个位的角色。

位的位置	$b_1$	$b_2$	$b_3$	$b_4$	$b_5$	$b_6$
输入	1	0	0	1	0	1
用途	行号高位	列号高位	列号	列号	列号低位	行号低位

第二步：首尾拼行，中间取列。

$$\text{row}=(b_1b_6)_2=(11)_2=3,\qquad \text{col}=(b_2b_3b_4b_5)_2=(0010)_2=2$$

因此查的是视觉上的第 4 行、第 3 列，不是第 3 行、第 2 列。

第三步：把表值写满 4 位。

$$S_1(100101)=8=(1000)_2$$

这只完成一个 S 盒。完整 DES 轮函数要把 48 位输入切为八组，各自送入不同的 $S_1,\ldots,S_8$，拼成 32 位后再做 P 置换。

易错点。 行号不是最左边两位；输入的十进制值 37 也不是行号。查表值小于 8 时仍要补前导零，例如表值 5 应写成 0101。

对应教材示例 3.2 与表 3-4（书内第 59—60 页，PDF 第 72—73 页）；这里展开了查表的中间步骤。

4.3 DES 的安全性瓶颈与双重加密的陷阱

• 暴力穷举破产：$2^{56} \approx 7.2 \times 10^{16}$，1998 年 EFF 制造的专用硬件“深裂（Deep Crack）”仅用 56 小时就穷举破解了 DES。实际穷举时间取决于硬件数量、吞吐率和成本，不能脱离这些条件给出固定分钟数。
• 能不能搞“双重 DES（2DES）”？
  • 有人提出用两把独立 56 位密钥连环加密：$C = E_{K_2}(E_{K_1}(P))$，认为安全性可以达到 $2^{112}$。
  • 大错特错！ 存在经典的 中间相遇攻击（Meet-in-the-Middle Attack）： $$E_{K_1}(P) = D_{K_2}(C) = M_{\text{mid}}$$
    1. 攻击者拿到一对已知明密文 $(P, C)$；
    2. 枚举所有 $2^{56}$ 种可能的 $K_1$，计算中间值 $E_{K_1}(P)$ 并存入哈希查找表；
    3. 枚举所有 $2^{56}$ 种可能的 $K_2$，计算解密中间值 $D_{K_2}(C)$，在哈希表中检索匹配；
    4. 在约 $2^{56}$ 条存储记录的条件下，两端枚举约需 $2^{56}+2^{56}=2^{57}$ 次密码运算；匹配的候选密钥对还要用额外明密文复核。
• 三重 DES（3DES / TDEA）：
  采用 EDE（加密-解密-加密）结构：$C = E_{K_3}(D_{K_2}(E_{K_1}(P)))$。
  中间使用解密是为了向后兼容：当 $K_1 = K_2 = K_3$ 时，等价于单次 DES。两把和三把独立 DES 密钥分别含 112 位和 168 位密钥材料，这不等于对应的有效安全强度。三密钥版本的经典安全强度通常按约 112 位计，两密钥版本还受更强攻击与数据量条件影响。
  标准状态：NIST 于 2024 年 1 月 1 日撤回 SP 800-67 Rev. 2，不再允许用 TDEA 施加新的密码保护；仍允许对已保护的数据解密、解封装密钥和验证 MAC。这不是对所有系统、所有用途的一概禁止。见 NIST 撤回说明。

例题 6：双重 DES 的“中间相遇”，为什么还要第二组明密文？

题目。 两把独立 DES 密钥各有 56 位，分组为 64 位。已知 $C=E_{K_2}(E_{K_1}(P))$。估算中间相遇攻击的时间、存储量，以及一组明密文可能留下多少个错误密钥对。

第一步：拆开两端搜索。 枚举全部 $K_1$，保存 $(E_{K_1}(P),K_1)$；再枚举全部 $K_2$，查询 $D_{K_2}(C)$ 是否在表内。匹配的必要条件为：

$$E_{K_1}(P)=D_{K_2}(C)$$

两边各做 $2^{56}$ 次密码运算，总量约为 $2^{57}$；表中约有 $2^{56}$ 条记录。同一个中间值可能对应多个密钥，不能只保存其中一个。

第二步：匹配不等于唯一命中。 在理想密码近似下，每个错误密钥对恰好把固定的 $P$ 映到 $C$ 的概率约为 $2^{-64}$。密钥对共有 $2^{112}$ 种，因此一组明密文留下的错误候选期望约为：

$$2^{112}\times2^{-64}=2^{48}$$

这解释了为什么“表里找到匹配就结束”不对。用另一组不同的明密文复核，错误候选期望约降为 $2^{112-2\times64}=2^{-16}$；用三组则约为 $2^{-80}$。这是模型下的期望量，不是绝对保证。

第三步：把存储成本也记下来。 即使每条记录只用 8 字节保存中间值、7 字节保存密钥，也需要约 $15\times2^{56}$ 字节，约 1.08 EB，还没有计入索引开销。$2^{57}$ 因而是巨大存储条件下的理论时间估算，不代表普通电脑就能轻松完成。

易错点。 112 位密钥材料不等于 112 位有效安全强度；时间复杂度也不能脱离空间复杂度单独解释。

对应教材 §5.2—§5.3.1（书内第 129—132 页，PDF 第 142—145 页），在这里与双重 DES 放在一起理解。

五、现代标准：高级加密标准 AES 与有限域 $\text{GF}(2^8)$ 数学

1997 年，NIST 发起征集取代 DES 的新一代加密算法，比利时密码学家 Joan Daemen 和 Vincent Rijmen 设计的 Rijndael 最终胜出，于 2001 年发布为 FIPS 197 标准，即 AES。

⚠️ 核心认知：AES 不采用 Feistel 网络，而是采用 代换-置换网络（SPN, Substitution-Permutation Network）。在每一轮中，AES 并行对整个 128 位状态的所有 16 个字节同时进行非线性和线性变换。

5.1 为什么必须引入有限域 $\text{GF}(2^8)$？

在计算机中，1 个字节由 8 个比特构成，取值范围为 0 到 255。我们能否直接在普通整数模环 $\mathbb Z_{256}$ 下进行加法和乘法？

• 绝不能！ 考察模 256 下的乘法：$2 \times 128 = 256 \equiv 0 \pmod{256}$。
• 在 $\mathbb Z_{256}$ 中存在大量零因子（Zero Divisors），所有偶数都没有乘法逆元！因此，不能用这个环替代 AES 所定义的非零字节求逆。环上也可以构造可逆变换，但那不是这里的 AES 运算。
• 为了让所有 256 个字节在加、减、乘、除（除以非零元素）下都能形成一个封闭、一致、每个非零元素都拥有唯一逆元的优美代数结构，AES 选择使用 伽罗瓦域（Galois Field） $\text{GF}(2^8)$。

5.2 $\text{GF}(2^8)$ 的代数运算与 xtime 算法

1. 元素的多项式表示

一个字节的 8 个比特 $(b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0)_2$ 被视为最高次数为 7 的多项式系数：

$$b(x) = b_7 x^7 + b_6 x^6 + b_5 x^5 + b_4 x^4 + b_3 x^3 + b_2 x^2 + b_1 x + b_0,\quad b_i \in \{0, 1\}$$

例如十六进制 0x57（二进制 01010111）对应：$x^6 + x^4 + x^2 + x + 1$。

2. 域加法与减法

多项式系数相加在模 2 下进行，不产生任何进位：$1+1=0, 0+1=1$。
域内的加法和减法完全等价于按位异或（XOR）！

$$\texttt{0x57} \oplus \texttt{0x83} = (01010111)_2 \oplus (10000011)_2 = (11010100)_2 = \texttt{0xD4}$$

3. 域乘法与不可约多项式

两个字节多项式相乘后，次数可能达到 14，必须对 AES 规定的不可约多项式取模约减：

$$m(x) = x^8 + x^4 + x^3 + x + 1 \quad (\text{十六进制记为 } \texttt{0x11B})$$

取模等价于在多项式长除法中，遇到 $x^8$ 就用 $x^4 + x^3 + x + 1$（0x1B）进行异或替换。

4. xtime 乘 2 算法（实现核心）

乘 0x02 即多项式乘 $x$（左移 1 位）。如果左移前最高位 $b_7 = 1$，左移后溢出产生 $x^8$，必须异或 0x1B：

def xtime(b):
    # 若最高位为1，左移后低8位与0x1b异或；否则直接左移
    return ((b << 1) & 0xFF) ^ (0x1B if (b & 0x80) else 0x00)

✍️ 手算演练：

• 计算 0x83 × 0x02：0x83（10000011），最高位是 1。左移得 0x06，异或 0x1B：0x06 ^ 0x1B = 0x1D。
• 计算 0x83 × 0x03：分解为 (0x83 × 0x02) ^ 0x83 = 0x1D ^ 0x83 = 0x9E。

5.3 AES 状态矩阵与四大轮变换

AES 处理的固定分组大小为 128 位（16 字节）。这 16 字节被排列为一个 $4 \times 4$ 的字节矩阵，称为 状态（State）。

🚨 排布陷阱（列优先规范）：输入字节 $a_0, a_1, \dots, a_{15}$ 是按列填入的！

$$\begin{bmatrix} a_0 & a_4 & a_8 & a_{12} \\ a_1 & a_5 & a_9 & a_{13} \\ a_2 & a_6 & a_{10} & a_{14} \\ a_3 & a_7 & a_{11} & a_{15} \end{bmatrix}$$

0. 输入状态1. SubBytes2. ShiftRows3. MixColumns4. AddRoundKey

a₀a₄a₈a₁₂a₁a₅a₉a₁₃a₂a₆a₁₀a₁₄a₃a₇a₁₁a₁₅

先按列装入，不是按行

每个 aᵢ 是一个字节。编号 0、1、2、3 竖着排在第一列。下边框颜色追踪字节来自哪一列。

b₀b₄b₈b₁₂b₁b₅b₉b₁₃b₂b₆b₁₀b₁₄b₃b₇b₁₁b₁₅

只换数值，不换位置

bᵢ = S(aᵢ)。每个字节分别查 S 盒；这一步没有把相邻字节混在一起。

b₀b₄b₈b₁₂b₅b₉b₁₃b₁b₁₀b₁₄b₂b₆b₁₅b₃b₇b₁₁

第 r 行循环左移 r 格

第一列现在是 b₀、b₅、b₁₀、b₁₅，恰好来自原来的四列。可切回上一步观察位置变化。

m₀m₄m₈m₁₂m₁m₅m₉m₁₃m₂m₆m₁₀m₁₄m₃m₇m₁₁m₁₅

同一列的四个字节共同参与运算

例如 m₀ = 02·b₀ ⊕ 03·b₅ ⊕ b₁₀ ⊕ b₁₅。乘法在 GF(2⁸) 中进行；四色边框表示来自四列的信息已混合。

t₀t₄t₈t₁₂t₁t₅t₉t₁₃t₂t₆t₁₀t₁₄t₃t₇t₁₁t₁₅

逐字节异或本轮密钥

tᵢ = mᵢ ⊕ kᵢ。密钥矩阵也按列编号。这里展示中间轮：初始轮只有 AddRoundKey，最后一轮省略 MixColumns。

点击步骤切换；键盘可用 Tab 聚焦后以方向键选择。字母下标保留来源，颜色仅作辅助。图示追踪结构，不代表某组具体数值。

1. SubBytes（字节代换，非线性混淆层）：
   • 独立对矩阵中的每个字节进行非线性映射。
   • 构造数学逻辑：先求其在 $\text{GF}(2^8)$ 上的乘法逆元（0 映射为 0），再施加固定的可逆仿射变换（破坏代数简单性）。
   • 是 AES 整个算法中唯一的非线性组件，提供抵御差分分析和线性分析的核心强度。
2. ShiftRows（行移位，置换层）：
   • 第 0 行：循环左移 0 字节；第 1 行：循环左移 1 字节；第 2 行：循环左移 2 字节；第 3 行：循环左移 3 字节。
   • 目的：打破字节在列方向上的孤立状态，将同列数据分散到四列中。
3. MixColumns（列混淆，扩散层）：
   • 独立对状态矩阵的每一列乘以一个固定的 MDS 最大距离可分矩阵： $$\begin{bmatrix} s'_{0,c} \\ s'_{1,c} \\ s'_{2,c} \\ s'_{3,c} \end{bmatrix} = \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}$$
   • 矩阵元素在 $\text{GF}(2^8)$ 下进行乘法和异或加法。
   • 巨大扩散力：配合 ShiftRows，单个输入字节的差分经过两轮可传播到全部 16 个字节。影响范围覆盖整个状态，不等于每次都翻转全部 128 位，也不能单凭这一点证明安全。
4. AddRoundKey（轮密钥加，秘密注入层）：
   • 将当前状态与本轮的 128 位轮密钥进行逐位异或。

例题 7：把 AES 列混淆完整算出一列，再接上轮密钥

题目。 经过 ShiftRows 后，某一列自上而下为 DB 13 53 45。求 MixColumns 的输出；若本轮对应密钥列为 01 02 03 04，再求 AddRoundKey 后的结果。以下所有字节值都按十六进制解释。

第一步：先算会反复使用的域乘法。 ×02 是 xtime，×03 则等于 xtime(x) XOR x：

字节 $x$	最高位	左移后低 8 位	$02\cdot x$	$03\cdot x$
DB	1	B6	B6 XOR 1B = AD	AD XOR DB = 76
13	0	26	26	26 XOR 13 = 35
53	0	A6	A6	A6 XOR 53 = F5
45	0	8A	8A	8A XOR 45 = CF

以第一行为例，DB 左移得到的完整多项式编码是 1B6。约减应为 1B6 XOR 11B = AD；如果已经截掉最高位，才写成 B6 XOR 1B = AD。两种记法不能混用。

第二步：按矩阵的每一行组合。 使用上文给出的四行系数：

$$\begin{aligned} c_0&=02\cdot\texttt{DB}\oplus03\cdot\texttt{13}\oplus\texttt{53}\oplus\texttt{45}\\ &=\texttt{AD}\oplus\texttt{35}\oplus\texttt{53}\oplus\texttt{45}=\boxed{\texttt{8E}},\\ c_1&=\texttt{DB}\oplus02\cdot\texttt{13}\oplus03\cdot\texttt{53}\oplus\texttt{45}\\ &=\texttt{DB}\oplus\texttt{26}\oplus\texttt{F5}\oplus\texttt{45}=\boxed{\texttt{4D}},\\ c_2&=\texttt{DB}\oplus\texttt{13}\oplus02\cdot\texttt{53}\oplus03\cdot\texttt{45}\\ &=\texttt{DB}\oplus\texttt{13}\oplus\texttt{A6}\oplus\texttt{CF}=\boxed{\texttt{A1}},\\ c_3&=03\cdot\texttt{DB}\oplus\texttt{13}\oplus\texttt{53}\oplus02\cdot\texttt{45}\\ &=\texttt{76}\oplus\texttt{13}\oplus\texttt{53}\oplus\texttt{8A}=\boxed{\texttt{BC}}. \end{aligned}$$

得到输出列 8E 4D A1 BC。例如第一项可以分步核对为 AD XOR 35 = 98、98 XOR 53 = CB、CB XOR 45 = 8E。

第三步：逐字节异或轮密钥。

列内位置	列混淆后	轮密钥	AddRoundKey 后
第 0 行	8E	01	8F
第 1 行	4D	02	4F
第 2 行	A1	03	A2
第 3 行	BC	04	B8

最终这一列变为 8F 4F A2 B8。

易错点。 03·13 不是普通整数乘法的 39，而是域乘法的 35；四项相加也必须用 XOR。本题只计算中间轮的一列，没有执行完整 AES；最后一轮没有 MixColumns。

运算方法对应教材 §4.4.2—§4.4.3（书内第 99—101 页，PDF 第 112—114 页）。本题选用非均匀输入列，逐项展示域乘法如何进入矩阵计算。

5.4 完整轮次编排与参数标准

标准名称	密钥长度	分组长度	轮数 $N_r$	轮密钥总数（128位）
AES-128	128 位 (16 字节)	128 位 (16 字节)	10 轮	11 个
AES-192	192 位 (24 字节)	128 位 (16 字节)	12 轮	13 个
AES-256	256 位 (32 字节)	128 位 (16 字节)	14 轮	15 个

为什么最后一轮要拿掉 MixColumns？

• 完整的执行流程为：
  • 初始轮：仅执行一次 AddRoundKey(State, K_0)；
  • 第 1 到 $N_r - 1$ 轮：执行完整的四大变换（SubBytes $\to$ ShiftRows $\to$ MixColumns $\to$ AddRoundKey）；
  • 最后一轮（第 $N_r$ 轮）：省去 MixColumns，仅执行 SubBytes $\to$ ShiftRows $\to$ AddRoundKey。
• 设计初衷：在硬件和底层代码中，为了让解密电路的结构与加密电路保持高度对称。省略末轮列混淆有助于构造结构相近的等价逆密码；不能据此断言所有实现都会大幅减少硬件面积。

5.5 侧信道预警：查表（T-table）实现的 Cache-timing 漏洞

在早期的 OpenSSL 等实现中，为了在 32 位 CPU 上追求极致吞吐率，开发者将 SubBytes、ShiftRows 和 MixColumns 合并为 4 张各 1 KB 的静态预计算表（称为 T-table）。
然而，查表的下标依赖于 明文 ^ 轮密钥 的敏感数据。现代 CPU 的高速缓存（L1/L2 Cache）机制会导致：命中 Cache 时耗时极短，未命中（Cache Miss）时耗时增加数百周期。黑客可以在同一物理机上通过测量解密耗时（如 Flush+Reload 攻击），逆向还原全部 AES 私钥！
实现应避免秘密相关的时间和访存行为；可使用 AES 专用指令，或经过审查的恒定时间软件实现。

---

六、分组密码操作模式（Modes of Operation）与认证加密

分组密码一次只能吃进固定 16 字节。现实中海量网络流量和文件如何切块加密？工作模式定义了具体的衔接机制。

6.1 ECB 模式：模式泄露的灾难

每个分组独立加密：$C_i = E_K(P_i)$。

• 致命弱点：相同的明文块永远生成完全相同的密文块！著名的“ECB 企鹅图”表明，即便对位图文件进行了强力 AES 加密，原始图像的轮廓依然在密文中清晰可见；
• 攻击者可以随意调换、拼接、删除密文块（例如将转账报文中的账户字段密文块互换），解密端无法察觉。ECB 绝不能用于多块消息加密！

6.2 CBC 模式：密码分组链接与 Padding Oracle 攻击

令 $C_0 = IV$（初始化向量），加密时当前明文先与前一块密文异或再送入加密器：

$$C_i = E_K(P_i \oplus C_{i-1}),\qquad P_i = D_K(C_i) \oplus C_{i-1}$$

flowchart LR
    subgraph cbc_encrypt ["CBC 加密: 串行依赖"]
        P1["明文 P1"] --> XOR1(("XOR"))
        IV["随机 IV"] --> XOR1
        XOR1 --> E1["E_k"] --> C1["密文 C1"]
        P2["明文 P2"] --> XOR2(("XOR"))
        C1 --> XOR2
        XOR2 --> E2["E_k"] --> C2["密文 C2"]
    end

• 并行性：加密时由于存在前后依赖，必须完全串行计算；解密时所有密文已知，$D_K(C_i)$ 可实现完全并行。
• IV 的铁律：IV 不必保密，可以随密文传输或按协议安全地产生；CBC 的 IV 必须不可预测（不能使用简单递增的序号作为 IV，否则易受选择明文攻击）。
• PKCS#7 填充标准：若缺 $k$ 字节（$1 \le k \le 16$），则补充 $k$ 个数值为 $k$ 的字节；若恰好对齐，也必须额外填充整整一个 16 字节的完整块（16 个 0x10），以便解密端无歧义剥离。
• Padding Oracle 填充预言机攻击：如果服务器在解密后，区分并返回了“填充错误（Padding Error）”与“业务逻辑错误”，攻击者只需不断篡改前一个密文块 $C_{i-1}$ 的末尾字节并反复尝试提交，平均每个字节仅需发起 128 次请求，就能像剥洋葱一样在完全不知道密钥的情况下恢复出全部明文！

P₁ · 保持原样

Dₖ(C₁) ⊕ IV

········

P₂ · 整块不可预测

Dₖ(C₂ ⊕ Δ) ⊕ C₁

????????

P₃ · 同位置翻转

Dₖ(C₃) ⊕ C₂ ⊕ Δ

··↕·····

P₄ 及以后：恢复正常，因为 C₃ 本身未改变。

同样的修改放进 CTR，会发生什么？

CTR 中 P₂ = C₂ ⊕ 密钥流₂，故只有 P₂ 的对应位翻转，其余位和其余块不受影响。这也说明：可预测地改动明文，并不要求攻击者先知道密钥。

这里分析未加认证的解密效果，Δ 只有一个置位比特。CBC 中“整块不可预测”不表示每个比特都必然翻转；小格仅示意位的位置。

例题 8：CBC 的填充、解密与位翻转，怎样连起来算？

题目。 使用 AES-CBC，原始消息长 20 字节，采用 PKCS#7 填充。已知第二个明文块 $P_2$ 的第一个字节为 ASCII 字符 1（31）。攻击者能修改密文且系统没有消息认证，若要把该字节改为 9（39），应修改哪里？会影响哪些块？

第一步：先确定块边界与填充。 AES 每块 16 字节。第一块放满 16 字节，第二块已有 4 字节，还缺 $16-4=12$ 字节，所以补 12 个 0C，最终密文有两块。常见长度可这样对照：

原消息长度	填充长度	附加的字节	填充后长度
15 字节	1	01	16 字节
16 字节	16	16 个 10	32 字节
20 字节	12	12 个 0C	32 字节

这些长度只计算消息和填充，不包括另外传输的 IV。已对齐的消息仍要补一整块，否则无法区分真实数据尾部与填充。

第二步：计算目标字节的差值。

$$\Delta=\texttt{31}\oplus\texttt{39}=\texttt{08}$$

这里不是把密文直接替换成 39，也不是对密文做整数加 8。

第三步：看解密公式，定位修改位置。

$$P_2=D_K(C_2)\oplus C_1$$

要可控地改变 $P_2$，应改的是前一密文块 $C_1$ 的对应字节：令 $C_1'[0]=C_1[0]\oplus\texttt{08}$，其他字节和 $C_2$ 保持不变。那么：

$$P_2'[0]=P_2[0]\oplus\texttt{08}=\texttt{31}\oplus\texttt{08}=\texttt{39}$$

第四步：检查副作用。 $P_1'=D_K(C_1')\oplus IV$ 会变得不可预测；$P_2$ 只有目标字节改变，尾部 12 个 0C 不变，所以填充检查仍会通过。第一块被破坏后，业务报文未必仍能被接受，但 “填充合法”显然不能证明“消息未被篡改”。

易错点。 修改当前密文块 $C_2$ 会使当前明文块不可预测；要精确翻转 $P_2$ 的位，应改 $C_1$。如果目标在第一明文块，则可通过修改未受认证保护的 IV 做同样的异或操作，而且不会破坏更早的明文块。

CBC 依赖关系对应教材 §5.1.2（书内第 122—123 页，PDF 第 135—136 页）；消息长度、填充与位翻转情境为自设。

6.3 OFB、CFB 与 CTR 模式对比

分组密码也可以通过模式转化为流密码：

模式	核心递推关系	能否并行处理	密文翻转 1 比特时的解密错误传播
ECB	$C_i = E_K(P_i)$	加密解密均可并行	对应明文块 $P_i$ 彻底损坏（不可预测雪崩），其他块不受影响
CBC	$C_i = E_K(P_i \oplus C_{i-1})$	仅解密可并行	当前明文块 $P_i$ 彻底损坏；下一明文块 $P_{i+1}$ 相同位置精确翻转 1 比特！
OFB	$S_i = E_K(S_{i-1}), C_i = P_i \oplus S_i$	密钥流生成串行	仅当前明文块 $P_i$ 对应比特精确翻转，无任何错误扩散
CFB	$C_i = P_i \oplus E_K(C_{i-1})$	仅解密可并行	当前明文块 $P_i$ 对应比特精确翻转；下一明文块 $P_{i+1}$ 彻底损坏
CTR	$S_i = E_K(\text{Nonce} \| i), C_i = P_i \oplus S_i$	加密解密均可全并行，支持随机寻址读写	仅当前明文块 $P_i$ 对应比特精确翻转，无任何错误扩散

🚨 CTR 模式的生死线：在同一密钥下，Nonce || Counter 绝不可重复使用！ 一旦两篇消息使用了相同的计数器流，直接退化为 Two-Time Pad 密钥流复用，两个密文异或会暴露两个明文的异或关系；恢复明文还需已知片段等额外信息。

6.4 现代黄金标准：AEAD 与 AES-GCM

传统做法先用 CBC 加密、再用 HMAC 生成认证标签（Encrypt-then-MAC），开发人员极易在拼接、顺序、时序校验上写出严重漏洞。
现代密码学全面转向 AEAD（Authenticated Encryption with Associated Data，带附加数据的认证加密），其中最著名的代表是 AES-GCM（Galois/Counter Mode）。

路径 A · 加密明文

J₀ = Nonce 的初始计数块
计数块：inc₃₂(J₀), …
密钥流 = AESₖ(计数块)
C = P ⊕ 密钥流

路径 B · 认证数据

H = AESₖ(0¹²⁸)
S = GHASH_H(AAD, C, 长度块)

AAD 与 C 分别补齐到块边界；长度以位数编码。

两条路径共享 K 和 Nonce，但承担不同工作 ↓

标签 · 用初始计数块的加密结果作掩码

T = MSB_t(AESₖ(J₀) ⊕ S)

接收方计算并核对完整标签；验证成功后才把明文交给应用。

为什么不能在同一把 K 下复用 Nonce？

相同的 Nonce 会重复计数器密钥流，使两个密文的异或等于两个明文的异或；同时也重复标签掩码，破坏认证安全。

常用 96 位 Nonce 时 J₀ = Nonce ∥ 0³¹ ∥ 1；其他长度需按标准另行构造。图示 t 位标签，完整长度为 128 位。

1. 三类输入：
   • 明文（Plaintext）：需要被保密并认证的数据；
   • 附加认证数据（AAD）：例如网络报文的源 IP、目标端口、协议版本号。AAD 在这次 AEAD 操作中不被加密，但其完整性受标签保护。它可以是协议头、序号或上下文，未必用于路由，也不一定单独传输；
   • Nonce（初始化数）：标准推荐 96 位（12 字节），每次通信严格唯一。
2. 底层引擎：
   • 机密性：使用 AES-CTR 模式对明文进行极高吞吐的并行流加密；
   • 完整性与真实性：使用 GHASH，将 AAD 和密文按 128 位切块，在有限域 $\text{GF}(2^{128})$ 下进行霍纳法则（Horner's rule）多项式快速累加，最后与 Nonce 派生的掩码异或，输出 128 位认证标签（Tag）。
3. 验证原则：
   • 解密端收到密文和 Tag 后，必须按 GCM 的完整标签计算规则（包含 GHASH 与本次 nonce 对应的掩码）核验 Tag；
   • 一旦 Tag 比对失败，立即丢弃并报错，绝对不能把解密产生的残损明文交付给上层应用程序！

例题 9：GCM 验证通过，为什么仍可能重复扣款？

题目。 一个教学协议用 GCM 发送转账请求。设消息内容为 amount=100，附加认证数据 AAD 包含 version=1, seq=7，本次 Nonce 为 $N$，输出密文与标签 $(C,T)$。假设同一密钥下 Nonce 不重复使用，讨论以下三种情况：

1. 攻击者改动密文的一位，继续附上原标签；
2. 攻击者将 AAD 中的 seq=7 改为 seq=8，继续附上原标签；
3. 攻击者把 $(N,\mathrm{AAD},C,T)$ 完整重发一次。

第一步：区分“受保护的内容”和“接收方保存的状态”。

攻击方式	标签核验的输入是否改变？	接收方应如何处理？
改密文	是，$C$ 改变	原标签通常不再匹配；核验失败则拒绝交付明文
改序号	是，AAD 改变	虽然序号未加密，仍受认证；核验失败则拒绝
原样重放	否，所有输入和标签都相同	密码核验仍可通过，需要协议额外检查是否已处理

前两行的“通常”保留了认证方案的伪造概率边界；不能把有限长度标签说成数学上绝无碰撞。

第二步：把防重放落实到接收流程。 对这个只允许严格顺序处理的简化协议，可以规定：先核验标签，再检查经过认证的序号是否等于预期值；首次成功处理 seq=7 后，把预期值推进到 8。重复到来的 seq=7 就不能再次执行业务。业务执行与“已处理”状态更新还需保持一致，否则并发或崩溃仍可能造成重复处理。

第三步：不要混淆两种“重复”。 发送方在同一密钥下重新加密时复用 Nonce，会破坏 GCM 的安全条件；攻击者原样重发一个旧数据包，则是重放问题。发送方把 Nonce 管理正确，并不会自动让接收方识别旧消息。

易错点。 “把序号放进 AAD”只保证序号不能被随意改写。接收方还必须检查并记录序号，才能判断这份有效消息是不是已经处理过。

GCM 的认证输入对应教材 §5.1.6（书内第 127—129 页，PDF 第 140—142 页）；序号与业务处理流程是为理解协议边界增加的教学情境。

七、本篇复习问题与自我检验

请尝试合上笔记，独立回答下列问题并在草稿纸上完成推导：

1. 为什么“一次一密”在数学上拥有完美保密性，但只要密钥流复用了一次，就会遭到毁灭性破译？请写出代数抵消过程，并区分“已知一段明文可直接恢复对应片段”与“依靠 ASCII 特征猜测明文”。
2. 线性反馈移位寄存器（LFSR）可以产生长达 $2^m - 1$ 的巨大周期，为什么仍被认为在密码学上极度脆弱？求解反馈系数的核心算法思想是什么？
3. 在 Feistel 网络中，如果轮函数 $f(R, K)$ 内部将数据压缩、丢弃信息且不可逆，为什么整个解密过程依然可以精确还原原明文？请写出解密的代数证明。
4. 计算机内存里的 1 字节由 8 比特构成，为什么 AES 必须在 $\text{GF}(2^8)$ 有限域下定义多项式运算，而不能直接使用普通整数模 256 加减乘除？
5. 手算验证：在 AES 的 $\text{GF}(2^8)$ 域（不可约多项式为 $x^8 + x^4 + x^3 + x + 1$）中，计算十六进制 0x57 × 0x02 以及 0x57 × 0x03 的结果。
6. AES 算法中，单靠 SubBytes 能否实现全局扩散？单靠 MixColumns 能否抵御代数分析？四大变换是如何分工协作的？为什么最后一轮要特意去掉 MixColumns？
7. 为什么 ECB 模式加密位图时会出现轮廓泄露？在 CBC 模式中，如果在网络传输中将密文第二块的第 3 个比特翻转了，解密后的各个明文块会发生什么变化？
8. 什么是 Padding Oracle 攻击？为什么在现代协议设计中，业界强烈要求弃用“先解密后验 MAC”的模式，全面拥抱 AEAD（如 AES-GCM）？

👉 查看核对思路与要点提示

• 第 1 题：$C_1 \oplus C_2 = P_1 \oplus P_2$。空格 0x20 与字母异或会精确翻转大小写（第 6 比特），这只能提供空格位置的候选线索，不能保证唯一分离明文。
• 第 2 题：纯线性递推关系。已知连续明密文可恢复密钥流，进而构建模 2 线性方程组；满秩时可唯一求出反馈系数。更一般地，用 Berlekamp-Massey 恢复最短线性递推关系，再预测后续输出。
• 第 3 题：由于 $L_i = R_{i-1}$，解密端利用 $L_i$ 重新代入正向的 $f(L_i, K_i)$ 即可重新生成掩码，再与 $R_i = L_{i-1} \oplus f$ 异或抵消，恢复 $L_{i-1}$。
• 第 4 题：$\mathbb Z_{256}$ 存在大量零因子（所有偶数均无乘法逆元，不可逆）；而 $\text{GF}(2^8)$ 是域，所有非零元素均存在唯一乘法逆元。
• 第 5 题：0x57（01010111），最高位为 0，左移一位得 0xAE；乘 0x03 为 0xAE ^ 0x57 = 0xF9。
• 第 6 题：SubBytes 仅提供局部非线性混淆；MixColumns 仅提供列内线性扩散；ShiftRows 打破列独立性。三者交替实现全矩阵雪崩。最后一轮去掉 MixColumns 是为了让解密与加密电路在硬件架构上对称。
• 第 7 题：ECB 相同明文块映射为相同密文块。CBC 解密时，$P_2 = D(C_2) \oplus C_1$ 会由于 $C_2$ 变动而彻底不可预测雪崩；而 $P_3 = D(C_3) \oplus C_2$ 中 $C_2$ 仅参与异或，故 $P_3$ 的第 3 个比特精确翻转，其余块完好。
• 第 8 题：利用解密端返回的填充校验差异作为预言机逐字节探测明文。GCM 使用 CTR 加密，不需要 CBC 式填充；接收方按完整标签规则验证密文与 AAD，只有验证成功才向应用交付明文。即使实现内部提前计算了候选明文，也不能让未认证结果或错误差异泄露出去。