《应用密码学》总复习知识必看

1. 绪论（引言）

1.1 信息安全三要素（CIA）

• 机密性 Confidentiality：确保信息只被授权用户访问。
• 完整性 Integrity：确保信息未被未授权修改。
• 可用性 Availability：确保授权用户可以正常使用信息和系统。

1.2 密码学的两大分支

• 密码编码学 Cryptography：研究如何设计密码体制，实现保密、认证等。
• 密码分析学 Cryptanalysis：研究如何破译密码体制，恢复明文或密钥。

1.3 被动攻击与主动攻击

• 被动攻击（passive attack）：对保密性攻击，不修改数据流。
  • 窃听/截获：获取消息内容。
  • 流量分析：分析通信频率、长度、格式等。
  • 特点：难检测、易预防，加密是主要防御手段。
• 主动攻击（active attack）：修改数据流或伪造数据流。
  • 篡改：重放攻击、消息更改。
  • 伪造/伪装：插入伪造消息或假冒身份。
  • 中断/拒绝服务：破坏可用性。
  • 特点：难预防、需检测和恢复，完整性与认证机制是关键。

1.4 安全业务

常见安全业务：认证、访问控制、数据保密性、数据完整性、不可否认性、可用性。

1.5 保密通信系统模型

六元组常写为 (M, C, K, E, D) 或 (M, C, K1, K2, E, D)：

• M：明文空间；C：密文空间。
• K / K1：加密密钥；K2：解密密钥。
• E：加密算法；D：解密算法。
• 对称密码：K1 = K2；公钥密码：K1 ≠ K2，通常公钥加密、私钥解密。

1.6 Kerckhoffs 原则

密码系统的安全性应仅依赖于密钥的保密性，而不依赖于算法或系统的保密性。算法公开、密钥保密是现代密码学的基本假设。

1.7 两类密码体制

• 对称密码体制：加密和解密使用相同密钥（或可互相推导）。
  • 流密码：逐位/逐字符加密，有记忆性。
  • 分组密码：按固定长度分组加密，无记忆性。
  • 优点：速度快、效率高；缺点：密钥分配和管理困难，无法自然提供不可否认性。
• 非对称/公钥密码体制：一对密钥 (PK, SK)。
  • 公钥公开，私钥保密。
  • 解决密钥分配问题，可支持数字签名。
  • 速度慢，主要用于密钥管理和数字签名，或加密短数据。

1.8 对密码系统的攻击类型

按攻击者掌握的信息从弱到强：

1. 唯密文攻击：只有密文和算法。
2. 已知明文攻击：掌握若干明文-密文对。
3. 选择明文攻击：可选择明文并获得对应密文。
4. 选择密文攻击：可选择密文并获得对应明文（或解密结果）。

攻击复杂性指标：数据复杂性、处理复杂性、存储需求。原则是取三者中的最小值。

安全级别：

• 无条件安全性/信息安全性：理论上敌手不可能破解。
• 计算安全性：实践中敌手破解不可行。
• 可证明安全性：通过规约证明，如果某困难问题不可解，则密码系统安全。

1.9 古典密码

置换密码（换位密码）

只重新排列明文中元素的位置，不改变元素本身。现代分组密码中的 P 盒（置换）就来源于此。

代换密码

用一个符号替换另一个符号，分为单表代换、多表代换、多字母代换等。

移位密码（凯撒密码）

• 加密：c = (m + k) mod q
• 解密：m = (c - k) mod q
• 通常 q = 26，密钥空间 {0,1,...,25}，共 26 个；若排除 k=0 则 25 个。
• 例：k=5，明文 H（7）→ 密文 M（12）。

乘数密码

• 加密：c = (m × k) mod q
• 解密：m = (k⁻¹ × c) mod q
• 要求 gcd(k, q) = 1，否则 k 没有模 q 的逆元。
• q=26 时有效密钥：1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25。

仿射密码

• 加密：c = (k1 × m + k2) mod q
• 解密：m = k1⁻¹ × (c - k2) mod q
• 要求 gcd(k1, q) = 1。
• 例：q=26, k1=7, k2=3。加密 H(7)：c = 7×7+3 = 52 ≡ 0 mod 26，即 A。解密：7⁻¹ mod 26 = 15，m = 15×(0-3) = -45 ≡ 7 mod 26，恢复 H。

1.10 绪论必背清单

• CIA 三要素。
• 被动攻击 vs 主动攻击。
• Kerckhoffs 原则。
• 对称密码 vs 公钥密码。
• 四种攻击类型。
• 凯撒/移位、乘数、仿射密码的公式和可逆条件。
• 置换密码与代换密码的区别。

---

2. 流密码

2.1 基本思想与特点

流密码把明文按比特或字符逐位加密：

• 密钥流：k = k0 k1 k2 ...
• 密文：c_i = m_i ⊕ k_i
• 解密：m_i = c_i ⊕ k_i

特点：

• 仿效“一次一密”，密钥流应尽量接近随机。
• 加密速度快、错误传播低、硬件实现简单。
• 缺点：低扩散、无扩散；密钥流重复使用会非常危险。

流密码 vs 分组密码：核心区别是有无记忆性。

• 流密码：加密器中存在记忆元件（如移位寄存器），密钥流随时间/状态变化。
• 分组密码：每次处理固定长度的分组，加密变换不随时间变化。

2.2 同步流密码与自同步流密码

• 同步流密码：密钥流只由密钥和初始状态决定，与明文、密文无关。
  • 加解密双方必须严格同步。
  • 若传输中丢失或插入 1 位，后续全部错位。
  • 单个密文位错误通常只影响对应明文位，不传播。
• 自同步流密码（异步流密码）：密钥流依赖于之前的若干密文位。
  • 收到一定数量密文后可自动重新同步。
  • 存在有限错误传播：1 位密文错误会影响后续若干位明文，但之后恢复。

2.3 有限状态自动机（FSA）

有限状态自动机由三部分组成：

• 有限状态集 S；
• 有限输入字符集 A；
• 有限输出字符集 B；
• 状态转移函数 f: S × A → S；
• 输出函数 g: S × A → B；
• 初始状态 s0。

可用状态转移图/表表示。

2.4 密钥流生成器

密钥流生成器可分成：

• 驱动子系统：常用一个或多个 LFSR，产生周期大、统计特性好的序列。
• 非线性组合子系统：用非线性函数组合多个 LFSR 的输出，提高线性复杂度，抵抗代数攻击。

设计要点：采用线性状态转移函数 + 非线性输出函数，兼顾可分析性和安全性。

2.5 线性反馈移位寄存器 LFSR

n 级 LFSR 由 n 个二元存储器和 1 个反馈函数组成。

• 当前状态：(a_i, a_{i+1}, ..., a_{i+n-1})
• 输出：通常取 a_i
• 下一状态：每位右移，最高位由反馈函数填入
• 线性反馈函数：a_{i+n} = c1·a_{i+n-1} ⊕ c2·a_{i+n-2} ⊕ ... ⊕ cn·a_i
• 特征多项式：f(x) = 1 + c1 x + ... + cn xⁿ
• 若特征多项式为本原多项式，则 LFSR 输出最大周期序列。

LFSR 优点：硬件实现方便、周期大、统计特性好、便于代数分析。

2.6 m 序列与 Golomb 三假设

• m 序列：由 n 级 LFSR 产生、周期达到理论最大值 2ⁿ - 1 的非零输出序列。
• 产生条件：特征多项式为本原多项式。
• m 序列的线性复杂度为 n（即生成它的最短 LFSR 级数）。
• 伪随机序列：周期序列中，若截获长度小于周期，无法预测后续比特或找到生成规律。

Golomb 三假设（伪随机性假设）：

1. 平衡性：一个周期内，0 和 1 的个数相差不超过 1。
2. 游程分布：长度为 i 的 0 游程和 1 游程数量各占约 1/2^i；长度为 1 的游程约占 1/2，长度为 2 的约占 1/4，依此类推。
3. 自相关函数：序列的自相关函数为二值函数（在移位为 0 时最大，其他位置为同一较小常数）。

2.7 LFSR 小计算示例

设 3 级 LFSR：初始状态 (a0,a1,a2) = (1,0,1)，反馈函数 a_{i+3} = a_i ⊕ a_{i+1}。

状态与输出：

时刻	状态 (a_i,a_{i+1},a_{i+2})	输出 a_i	反馈 a_
0	1 0 1	1	1
1	0 1 1	0	1
2	1 1 1	1	0
3	1 1 0	1	0
4	1 0 0	1	1
5	0 0 1	0	0
6	0 1 0	0	1
7	1 0 1	—	回到初始状态

输出序列：1 0 1 1 1 0 0 ...，周期为 7，是该 LFSR 的 m 序列。

2.8 流密码易错点

• 同步流密码“无错误传播”不等于“不会失步”，丢位后会永久错位。
• 自同步流密码有有限错误传播，但能自动重新同步。
• m 序列周期是 2ⁿ-1，不是 2ⁿ；全零状态是死状态，不能进入。
• 线性复杂度不是周期，也不是密钥长度。
• Golomb 三假设是伪随机性的必要条件，不是充分条件。

---

3. 分组密码

3.1 分组密码基本概念

• 把明文分成固定长度的分组，如 64 位、128 位。
• 对每个分组使用同一密钥和同一加密变换。
• 无记忆性；分组之间有混淆和扩散要求。
• 扩散 Diffusion：明文或密钥的 1 位变化影响尽可能多的密文位。
• 混淆 Confusion：使密文与密钥之间的统计关系尽量复杂，让敌手难以从密文推出密钥。

3.2 分组密码结构

SPN 结构（代换-置换网络）

• 每一轮：S 盒代换 + P 盒置换 + 轮密钥混合。
• 代换提供混淆，置换提供扩散。
• 加解密结构不一定相同，S 盒需可逆。

Feistel 网络

• 将分组分为左右两半 L、R。
• 第 i 轮：
  • L_i = R_{i-1}
  • R_i = L_{i-1} ⊕ F(R_{i-1}, K_i)
• 加密和解密结构相同，解密时子密钥顺序相反。
• 轮函数 F 不需要可逆，设计限制小。
• DES 是 Feistel 网络的典型代表。

3.3 DES 算法

• 分组 64 位；种子密钥 64 位，其中有效密钥 56 位（8 位奇偶校验）。
• 16 轮 Feistel 结构。
• 初始置换 IP 和逆初始置换 IP⁻¹。
• 轮函数：F(R, K) = P(S(E(R) ⊕ K))
  • E：扩展置换，32 位 → 48 位。
  • 轮密钥 K：48 位。
  • S：8 个 S 盒，每个 6 位输入 → 4 位输出，共 32 位输出。
  • P：置换，32 位 → 32 位。
• 子密钥生成：
  • 64 位密钥经 PC-1 置换为 56 位，分成 C、D 各 28 位。
  • 每轮循环左移 1 或 2 位。
  • 经 PC-2 压缩为 48 位轮密钥。
• 解密：与加密相同的算法，但 16 个子密钥逆序使用。
• DES 特点：算法对称、雪崩效应、完全性；但 56 位密钥太短，已能被穷举破解。

3.4 二重 DES、三重 DES 与中途相遇攻击

• 二重 DES：C = E_{K2}(E_{K1}(P))
• 中途相遇攻击：已知一对明密文，枚举 K1 得到中间值表，再用 K2 解密 C 查表，攻击复杂度约为 2^56，并没有把安全性提高到 2^112。
• 三重 DES（2-key 3DES）：C = E_{K1}(D_{K2}(E_{K1}(P)))，有效安全性约 112 位。
• 3-key 3DES：安全性更高，但速度慢，逐渐被 AES 替代。

3.5 AES 算法

• 分组 128 位；密钥长度 128 / 192 / 256 位；轮数分别为 10 / 12 / 14。
• 状态矩阵：4×4 字节，按列优先排列。
• 加密轮函数四个步骤：
  1. SubBytes：字节代换，使用 16×16 S 盒。
  2. ShiftRows：第 0 行不动，第 1 行左移 1 字节，第 2 行左移 2 字节，第 3 行左移 3 字节。
  3. MixColumns：每列在 GF(2⁸) 上与固定多项式矩阵相乘。
  4. AddRoundKey：状态与轮密钥异或。
• 最后一轮没有 MixColumns，只有 SubBytes、ShiftRows、AddRoundKey。
• 密钥扩展：字 w[i]；当 i 不是 4 的倍数时，w[i] = w[i-1] ⊕ w[i-4]；当 i 是 4 的倍数时，先对 w[i-1] 做 RotWord、SubWord、异或 Rcon，再与 w[i-4] 异或。
• AES 的数学基础：GF(2⁸) 上模不可约多项式 m(x) = x⁸ + x⁴ + x³ + x + 1（十六进制 0x11B）。
  • 例：0x57 · 0x83 = 0xC1。

3.6 SM4 算法

• 中国商用分组密码标准，分组长度和密钥长度均为 128 位。
• 32 轮非线性迭代结构，加解密结构相同，解密轮密钥逆序使用。
• 采用 S 盒、线性变换 L 和合成置换 T。
• 常用于 WAPI、国密 SSL 等场景。

3.7 分组密码运行模式

模式	加密/解密公式要点	并行性	错误传播	主要特点
ECB	C_i = E(P_i)	加密、解密都可并行	只影响对应密文分组	相同明文分组产生相同密文，泄露结构，不安全
CBC	C_i = E(P_i ⊕ C_{i-1})，C_0 = IV	加密串行，解密可并行	影响当前明文分组和下一位/下一分组	需填充；IV 要随机且不可预测
CFB	C_i = P_i ⊕ E(C_{i-1})（取 s 位）	加密串行，解密可并行	有有限错误传播，约 s+1 个单元	可作自同步流密码；解密也使用加密函数
OFB	O_i = E(O_{i-1})，C_i = P_i ⊕ O_i	可并行做密钥流	单比特错误只影响对应比特，不传播	同步流密码；IV 不能重复；不能提供完整性
CTR	O_i = E(IV + i)，C_i = P_i ⊕ O_i	加密、解密都可并行	单比特错误只影响对应比特	可随机访问；nonce 绝对不能重复

模式选择速记：

• 不要用 ECB 加密有结构的数据。
• CBC 适合文件加密，需随机 IV。
• CFB 适合流式数据，能自同步。
• OFB 是同步流密码，不能做完整性。
• CTR 适合并行、随机访问场景，但 nonce 重用会直接泄露密钥流。

3.8 分组密码计算/对比常考

• 给一轮 DES，写出轮函数 F 的结构。
• 给 AES 状态矩阵，说明 SubBytes、ShiftRows、MixColumns、AddRoundKey 的操作。
• 比较 ECB、CBC、CFB、OFB、CTR 的优缺点、并行性、错误传播。
• 说明为什么二重 DES 不能显著提高安全性（中途相遇攻击）。
• 说明 AES 最后一轮为什么没有 MixColumns。

3.9 分组密码易错点

• Feistel 网络的轮函数不需要可逆，但 SPN 的每一层通常需要可逆。
• “DES 密钥 64 位”不等于“有效密钥 64 位”，实际有效 56 位。
• 3DES 不是“三重 AES”，速度慢，安全性约 112 位（2-key）。
• CBC 中 IV 不需要保密，但必须随机、不可预测，不能用固定值。
• CTR 中 nonce 重用等价于密钥流重用，必须严格避免。
• OFB/CTR 是流密码，天然不提供完整性，不能代替 MAC。

---

4. 哈希函数与消息认证

注：考试大纲把本章列为第 4 章；李佩豪老师 PPT 的“4567 章”把公钥密码放第 4 章、哈希函数放第 5 章，内容相同。

4.1 消息认证

消息认证用于验证：

• 消息确实来自声称的发送方；
• 消息内容没有被篡改；
• 消息的时序、顺序等符合要求。

常用手段：

• 对称加密：只有共享密钥者能产生合法密文；
• 消息认证码 MAC：用共享密钥对消息生成认证符；
• 哈希函数 + 数字签名：提供完整性和不可否认性。

4.2 哈希函数定义与安全需求

哈希函数 H 把任意长度消息 M 映射为固定长度摘要 H(M)。

应满足的条件：

1. 输入任意长度，输出固定长度。
2. 对任意 M，计算 H(M) 容易。
3. 单向性：已知 h，找到 M 使 H(M) = h 计算上不可行。
4. 弱抗碰撞（弱单向）：已知 M，找到 M' ≠ M 使 H(M') = H(M) 计算上不可行。
5. 强抗碰撞：找到任意一对 M ≠ M' 使 H(M) = H(M') 计算上不可行。
6. 雪崩效应：输入 1 位变化，输出约一半比特变化。

4.3 三类哈希函数

• 单向 Hash 函数：由摘要不能反推消息。
• 弱抗碰撞 Hash 函数：给定一个消息，难以找到另一个消息与它碰撞。
• 强抗碰撞 Hash 函数：难以找到任意两个不同消息具有相同摘要。

4.4 生日问题与生日攻击

第 I 类生日问题（找一个和指定摘要相同的输入）

• 设哈希输出有 n 种可能。
• 近似结论：k ≈ n/2 时概率约 1/2（PPT 中的简化推导）。
• 更精确：k ≈ n·ln2 ≈ 0.69n。
• 若输出为 m 位，则 n = 2^m，约需 0.69 × 2^m 次尝试。

第 II 类生日问题（找任意两个碰撞的输入）

• 近似结论：k ≈ √n。
• 更精确：k ≈ 1.18√n。
• 若输出为 m 位，则碰撞攻击复杂度约为 2^{m/2}。
• 例：64 位哈希，找碰撞约需 1.18 × 2³² ≈ 5.1 × 10⁹ 次；128 位哈希约需 2⁶⁴ 次。
• 结论：哈希输出长度必须足够大，才能抵抗生日攻击。

4.5 迭代型哈希函数、MD5 与 SHA

Merkle-Damgård 迭代结构

• 把消息填充并分块，逐块输入压缩函数。
• 压缩函数 f 的碰撞会导致整个哈希函数的碰撞，因此 f 的抗碰撞性是核心。
• 填充通常包含消息长度，防止长度扩展等攻击。

MD5

• 输出 128 位，分组 512 位。
• 4 轮，每轮 16 步，共 64 步。
• 曾广泛使用，现已不抗碰撞，不应再用于安全场景。

SHA 系列

• SHA-1：输出 160 位，已不推荐。
• SHA-2：SHA-224、SHA-256、SHA-384、SHA-512。
• SHA-3：Keccak 海绵结构，与 SHA-2 结构不同。
• SM3：中国商用哈希标准，输出 256 位，用于 SM2 等。

4.6 MAC、CBC-MAC 与 HMAC

MAC（消息认证码）

• MAC = C_K(M)，使用共享密钥 K 和公开函数。
• 提供完整性和消息源认证。
• 不能提供不可否认性，因为双方都知道密钥，第三方无法判断是谁生成的 MAC。

CBC-MAC

• 用分组密码的 CBC 模式，把最后一个密文分组作为 MAC。
• 对固定长度消息较简单；对变长消息需注意安全使用方式。

HMAC

• HMAC(K, M) = H((K ⊕ opad) || H((K ⊕ ipad) || M))
• 基于哈希函数构造 MAC，安全性依赖哈希函数。
• 广泛用于 TLS、IPSec 等协议。

4.7 Hash / MAC / 数字签名对比

机制	密钥	能否验证来源	能否防否认	典型用途
Hash	无	否	否	完整性校验、口令存储
MAC	对称共享密钥	能向共享者验证	否	消息认证、完整性
数字签名	私钥签名、公钥验证	能向任何人验证	能	认证、完整性、不可否认

4.8 哈希与认证易错点

• 哈希不是加密，不能用来保密；哈希用于完整性。
• 生日攻击攻击的是碰撞，不是原像；2^{m/2} 而不是 2^m。
• MAC 不能提供不可否认性；数字签名可以。
• 先签名再加密、先加密再签名，安全目标和性质不同。
• MD5、SHA-1 已不抗碰撞，不能用在新系统里。

---

5. 公钥密码

5.1 公钥密码体制基本原理

• 每个用户有一对密钥：公钥 PK（公开）和私钥 SK（保密）。
• 加密：发送方用接收方公钥加密；解密：接收方用自己私钥解密。
• 认证/签名：发送方用自己的私钥签名；验证者用发送方公钥验证。
• 可同时提供保密性和认证性：先用自己的私钥签名，再用对方的公钥加密（“先签后加”），或先加密再签名，按协议目标选择。
• 本质：构造一个陷门单向函数。
  • 正向容易计算；
  • 反向没有陷门时计算不可行；
  • 拥有陷门（私钥）时可容易求逆。
• 公钥密码要抵抗的攻击：穷举密钥搜索、由公钥求私钥、可能字攻击等。
• 公钥密码主要用于：密钥分配/协商、数字签名、加密短数据；大数据加密一般用对称密码（混合加密）。

5.2 RSA 算法

密钥生成

1. 选两个保密的大素数 p 和 q。
2. 计算 n = p × q，φ(n) = (p-1)(q-1)。
3. 选整数 e，满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。
4. 计算 d，满足 e × d ≡ 1 mod φ(n)，即 d = e⁻¹ mod φ(n)。
5. 公钥 (e, n)，私钥 d；p、q、φ(n) 必须保密或销毁。

加密与解密

• 明文分组 m 必须满足 0 ≤ m < n，分组长度小于 log₂n。
• 加密：c = m^e mod n
• 解密：m = c^d mod n

正确性

因为 e × d ≡ 1 mod φ(n)，由欧拉定理可证 (m^e)^d ≡ m mod n（当 gcd(m,n)=1 时；其他情况也可通过中国剩余定理证明）。

RSA 示例

• p = 11, q = 13 → n = 143，φ(n) = 120。
• 取 e = 7，则 d = 103（因为 7×103 = 721 ≡ 1 mod 120）。
• 加密 m = 5：c = 5⁷ mod 143 = 47。
• 解密 c = 47：m = 47¹⁰³ mod 143 = 5。
• 公钥 (7, 143)，私钥 d = 103。

RSA 安全性

• 基于大整数分解困难性：已知 n 分解出 p, q，就能求出 φ(n) 和 d。
• 参数选择不当会导致攻击：
  • 共模攻击：多个用户共用同一个 n，不同 e，可能被恢复明文。
  • 低指数攻击：多个用户使用小 e 加密同一明文，可用中国剩余定理恢复。
  • 小解密指数攻击：d 太小可被 Wiener 攻击等。
  • 选择密文攻击：RSA 具有乘法性质，需要 OAEP 等填充。
• 实际使用要点：p、q 足够大且不同，e 常用 65537，d 不能太小；必须使用安全填充。

5.3 ElGamal 算法

基于离散对数问题。

密钥生成

1. 选大素数 p，选生成元 g（模 p 的原根）。
2. 随机选私钥 x，1 ≤ x ≤ p-2。
3. 计算公钥 y = g^x mod p。
4. 公钥 (p, g, y)，私钥 x。

加密

1. 随机选整数 r，要求 gcd(r, p-1) = 1（也常直接随机取 r）。
2. C1 = g^r mod p
3. C2 = y^r × m mod p
4. 密文 (C1, C2)

解密

• 先求 (C1)^x mod p，再求其乘法逆元，或直接计算：
• m = C2 × (C1^x)⁻¹ mod p
• 因为 C1^x = g^{rx}，C2 = m × g^{xr}，约去即可。

安全要点

• 同一个随机数 r 不能加密两条不同消息。
  • 若两条密文使用相同 r，则 C1 相同，C2₁/C2₂ = m₁/m₂，已知一个明文就能求出另一个。
• p 应为强素数或满足安全要求，g 应为生成元。
• 私钥 x 和随机数 r 不能太小。
• ElGamal 密文长度是明文的两倍，且加密具有随机性（同一明文每次密文不同）。

5.4 Diffie-Hellman 密钥交换

流程

1. 公开参数：大素数 p 和生成元 g。
2. Alice 选私密随机数 a，计算 A = g^a mod p，发送 A。
3. Bob 选私密随机数 b，计算 B = g^b mod p，发送 B。
4. Alice 计算 K = B^a = g^{ab} mod p。
5. Bob 计算 K = A^b = g^{ab} mod p。
6. 双方得到相同的会话密钥 K。

示例（PPT 例题）

• p = 97, g = 5；Alice 取 a = 36，得 A = 5³⁶ mod 97 = 50。
• Bob 取 b = 58，得 B = 5⁵⁸ mod 97 = 44。
• 共享密钥 K = 44³⁶ mod 97 = 75 = 50⁵⁸ mod 97。

安全性

• 窃听者只能得到 p、g、g^a、g^b，要得到 g^{ab} 需解决离散对数问题。
• 不能抵抗中间人攻击（MITM）：攻击者分别与双方建立 DH 密钥，转发消息并窃听。
• 解决办法：用数字签名/证书对 DH 公钥进行认证，或使用站到站协议（STS）。

5.5 ECC 椭圆曲线密码

基本概念

• 有限域 F_p 上的椭圆曲线：y² = x³ + ax + b mod p，且 4a³ + 27b² ≠ 0。
• 曲线上的点加上无穷远点 O 构成阿贝尔群。
• 点加法：P + Q；倍点：2P = P + P；标量乘：kP = P + P + ... + P。
• 椭圆曲线离散对数问题（ECDLP）：已知 P 和 Q = kP，求 k 困难。

加密思路（类 ElGamal）

• 密钥生成：选基点 P（阶为大素数 n），私钥 x，公钥 Q = xP。
• 加密明文点 Pm：随机选 k，计算 C1 = kP，C2 = Pm + kQ。
• 解密：Pm = C2 - xC1。

ECC 优点

• 相同安全强度下密钥更短：160 位 ECC ≈ 1024 位 RSA；256 位 ECC ≈ 3072 位 RSA。
• 计算量、存储、带宽更小，适合移动设备。
• 破解难度基本是指数级，而 RSA 是亚指数级。

5.6 SM2 算法

• 中国商用公钥密码标准，基于 256 位素数域上的椭圆曲线。
• 用于数字签名、密钥交换、公钥加密。
• 加密和签名中大量使用 SM3 哈希函数。
• 加密思路与 ECC/ElGamal 类似：C1 = kP，C2 = M ⊕ KDF(x2 || y2)，C3 = Hash(x2 || M || y2)。
• 重点掌握：基于 ECC、国密标准、配合 SM3、安全性依赖于 ECDLP。

5.7 其他公钥体制（了解）

• 背包密码：基于背包问题（NP 完全），早期公钥密码，多已被攻破。
• Rabin 密码：安全性等价于大整数分解，加密 c = m² mod n，解密有四个可能根，需冗余信息确定明文。
• McEliece 密码：基于纠错码译码困难，可抵抗量子计算机，但密钥很大。

---

6. 数字签名

6.1 数字签名的安全需求

数字签名用于提供：

• 身份认证：确认签名者身份。
• 数据完整性：消息被篡改后签名验证失败。
• 不可否认性：签名者事后不能否认自己的签名。

注意：数字签名本身不提供保密性；需要保密时应结合加密。

数字签名通常先对消息的哈希值签名，而不是直接对长消息签名，以兼顾效率和安全性。

6.2 RSA 数字签名

• 签名：s = H(m)^d mod n
• 验证：计算 H(m)' = s^e mod n，比较 H(m)' 与 H(m)。
• 也可写作 s = m^d mod n 并对 m 有格式要求。
• 安全性：基于 RSA 问题；必须使用哈希和填充，否则存在伪造攻击：
  • 任意 s，可计算 m = s^e mod n，得到“随机消息”的合法签名。
  • RSA 具有乘法性：若知道 m1、m2 的签名，可构造 m1m2 的签名。
  • 因此实际使用 RSA-PSS 等填充方案。

6.3 ElGamal 数字签名

• 密钥：大素数 p，生成元 g，私钥 x，公钥 y = g^x mod p。
• 签名：
  1. 随机选 k，要求 gcd(k, p-1) = 1。
  2. r = g^k mod p。
  3. s = (H(m) - x·r) · k⁻¹ mod (p-1)。
  4. 签名为 (r, s)。
• 验证：验证 y^r · r^s ≡ g^{H(m)} mod p。
• 随机数 k 必须每次不同且保密；重复使用 k 会泄露私钥。

6.4 DSA 数字签名标准

• 基于离散对数，使用两个素数 p 和 q，其中 q | (p-1)。
• g = h^{(p-1)/q} mod p，1 < h < p-1。
• 私钥 x，公钥 y = g^x mod p。
• 签名：
  • 随机 k，r = (g^k mod p) mod q
  • s = k⁻¹ (H(m) + x·r) mod q
• 验证：
  • w = s⁻¹ mod q
  • u1 = H(m)·w mod q，u2 = r·w mod q
  • v = ((g^{u1} · y^{u2}) mod p) mod q，验证 v = r。
• 特点：签名较短，安全性基于离散对数；k 必须随机且不能泄露。

6.5 Schnorr 签名

• 同样基于离散对数，签名更短、计算效率更高。
• 常用参数：p 为大素数，q | p-1，g 为 q 阶元素。
• 签名过程：
  • 随机 k，r = g^k mod p
  • e = H(m || r)
  • s = k + x·e mod q
  • 签名 (e, s)
• 验证：计算 r' = g^s · y^{-e} mod p，验证 H(m || r') = e。
• 特点：签名短、可证明安全；适合智能卡等场景。

6.6 特殊数字签名（了解概念）

• 盲签名：签名者不知道消息内容就签名，常用于电子现金、匿名凭证。
• 代理签名：原始签名者授权代理人代为签名。
• 群签名：群成员可匿名代表群签名，群管理员可追踪身份。
• 多重签名：多人共同对同一消息签名。
• 不可否认签名：验证需要签名者配合，否则无法验证。
• 前向安全签名：私钥泄露后，之前的签名仍然有效。

6.7 签名 vs MAC

• MAC 使用对称密钥，速度更快，但只能由共享密钥的双方验证，不能防否认。
• 数字签名使用私钥签名、公钥验证，可向任何人证明，能防否认。
• 两者都能提供完整性和认证，但适用场景不同。

6.8 综合题模板：混合加密 + 数字签名

目标：同时实现机密性、完整性、认证、不可否认性。

方案示例：

1. A 随机生成会话密钥 K。
2. A 用 K 对消息 M 做对称加密：C = E_K(M)（建议 AES-GCM 或 AES + HMAC）。
3. A 用自己的私钥对 H(M) 签名：sig = Sign_{SK_A}(H(M))。
4. A 用 B 的公钥加密会话密钥：CK = E_{PK_B}(K)。
5. A 发送 (CK, C, sig, Cert_A)。
6. B 用自己的私钥解密 CK 得到 K；用 K 解密 C 得到 M；用 A 的公钥验证 sig。

安全性分析：

• 机密性：会话密钥被 B 的公钥保护，消息被对称加密。
• 完整性：签名验证 H(M)，篡改会导致验证失败。
• 认证：B 用 A 的公钥验证签名，确认消息来自 A。
• 不可否认性：只有 A 拥有 SK_A，A 不能否认签名。
• 还需考虑：证书有效性、重放攻击（加 nonce/时间戳）、密钥新鲜性。

---

7. 密钥管理与身份认证

7.1 密钥管理基本概念

密钥生命周期包括：生成、分配、存储、使用、更新、撤销、销毁。

• 主密钥（Master Key）：用于保护其他密钥。
• 密钥加密密钥（KEK）：用于加密会话密钥/数据密钥。
• 数据密钥（Data Key）：直接加密数据。
• 会话密钥：一次通信或一段时间内使用，用完即弃。

7.2 密钥分配的基本方法

1. 人工信道：物理方式传递，安全但效率低。
2. 密码技术：
   • 密钥分配中心 KDC：适用于对称密码。
   • Diffie-Hellman：双方协商会话密钥。
   • 公钥密码/证书：加密传输或签名认证。
3. 物理现象：量子密钥分配 QKD 等。

7.3 KDC 密钥分配

KDC 与每个用户共享一个主密钥，如 K_A、K_B。

简化流程：

1. A 向 KDC 请求与 B 通信的会话密钥。
2. KDC 生成会话密钥 K_S。
3. KDC 用 K_A 加密 (K_S, ID_B) 发给 A。
4. KDC 用 K_B 加密 (K_S, ID_A) 发给 B。
5. A、B 用各自主密钥解密得到 K_S，开始通信。

安全要点：加入 nonce/时间戳防重放；主密钥必须安全；KDC 是信任中心，可能成为单点故障。

7.4 公钥分配与 PKI

公钥分配方式：

• 公开发布：简单，但容易被冒充。
• 公开目录：由可信机构维护，但仍需认证。
• 公钥授权机构：在线查询，权威但可能成为瓶颈。
• 公钥证书：由 CA 用私钥签名，绑定身份与公钥，最常用。

PKI 组件：

• CA（认证中心）：签发、管理证书。
• RA（注册中心）：审核身份、辅助注册。
• 证书：包含公钥、身份、有效期、CA 签名等。
• CRL/OCSP：证书撤销列表/在线状态查询。

7.5 Shamir (t, n) 门限秘密共享

目标：把秘密 S 分成 n 份，任意 t 份可恢复 S，少于 t 份无法获得 S。

方案：

1. 选大素数 p（p > S，也大于所有份额）。
2. 令 a0 = S。
3. 随机选 a1, a2, ..., a_{t-1} mod p。
4. 构造多项式：f(x) = a0 + a1x + a2x² + ... + a_{t-1}x^{t-1} mod p。
5. 第 i 个份额为 (x_i, y_i = f(x_i))，x_i 互不相同且非 0。
6. 任意 t 个份额用拉格朗日插值恢复：
   • S = f(0) = Σ y_i · λ_i mod p
   • λ_i = ∏_{j≠i} (0 - x_j)/(x_i - x_j) mod p

示例：p = 17, S = 5, t = 2，取 a1 = 3，f(x) = 5 + 3x mod 17。

• 份额：(1,8), (2,11), (3,14)。
• 用 (1,8) 和 (2,11) 恢复：
  • λ1 = (0-2)/(1-2) = 2
  • λ2 = (0-1)/(2-1) = -1
  • S = 2×8 + (-1)×11 = 16 - 11 = 5 mod 17。

7.6 身份认证与会话密钥建立

• 单向认证：只验证一方身份。
• 双向认证：双方互相验证身份。
• 常用手段：口令、挑战-响应、时间戳、nonce、数字签名、证书。
• 基于对称密钥的挑战-响应：
  1. B 发送随机数 R_B。
  2. A 返回 E_K(R_B)。
  3. B 验证解密结果是否等于 R_B。
• 基于公钥的双向认证：
  1. 双方交换证书。
  2. 用 nonce 挑战，对方用私钥签名。
  3. 验证签名并建立会话密钥。
• 安全目标：身份认证、密钥确认、抗重放、前向保密（视协议而定）。

7.7 密钥托管

密钥托管（Key Escrow）：把用户的密钥或恢复信息交给可信第三方保存，以便在法律授权下恢复数据。

• 优点：支持合法访问、密钥恢复。
• 风险：隐私、信任、滥用问题；需严格法律和技术控制。

---

8. 计算题专项（必会）

复习方法：每一类先看懂例题，再自己手算一遍，最后只看题目回忆步骤。

8.1 仿射密码

• 加密：c = (k1·m + k2) mod q
• 解密：m = k1⁻¹(c - k2) mod q
• 条件：gcd(k1, q) = 1
• 例：q=26, k1=7, k2=3，加密 H(7)：
  • c = 7×7+3 = 52 ≡ 0 mod 26，即 A。
  • 解密 A(0)：7⁻¹ mod 26 = 15，m = 15×(0-3) = -45 ≡ 7 mod 26，即 H。

8.2 LFSR / m 序列

• 写状态表：输出当前最高位，计算反馈位，整体移位。
• 周期：直到状态回到初始状态。
• 若周期为 2ⁿ-1 且非零状态都出现，则为 m 序列。
• 例：3 级 LFSR，初态 101，反馈 a_{i+3} = a_i ⊕ a_{i+1}，输出序列 1011100...，周期 7。

8.3 DES / AES 轮操作

DES 轮函数简答：

1. 右半部分 R 经扩展置换 E 从 32 位扩展到 48 位。
2. 与 48 位轮密钥异或。
3. 分成 8 组 6 位，分别通过 8 个 S 盒，输出 8 组 4 位。
4. 合并为 32 位，经 P 盒置换。
5. 结果与左半部分异或，作为下一轮右半部分。

AES 一轮：

• SubBytes → ShiftRows → MixColumns → AddRoundKey。
• 最后一轮没有 MixColumns。
• 密钥扩展：w[i] = w[i-1] ⊕ w[i-4]（i 不是 4 的倍数）；否则先 RotWord、SubWord、异或 Rcon 后再与 w[i-4] 异或。

8.4 运行模式错误传播

• ECB：一个密文分组出错，只影响对应明文分组；分组可重排、重放。
• CBC：C_i 出错影响 P_i 的对应位和 P_{i+1} 的对应位（因为 P_i = D(C_i) ⊕ C_{i-1}，P_{i+1}=D(C_{i+1})⊕C_i）。
• CFB：有有限错误传播，约 s+1 个单元；可自同步。
• OFB：密文单比特错误只影响对应明文比特，不传播。
• CTR：密文单比特错误只影响对应明文比特；nonce 重用会泄露密钥流。

8.5 RSA 计算

步骤：

1. n = p×q
2. φ(n) = (p-1)(q-1)
3. 选 e，满足 gcd(e, φ)=1
4. 求 d = e⁻¹ mod φ
5. 加密 c = m^e mod n
6. 解密 m = c^d mod n

例：p=11, q=13, e=7, m=5

• n = 143，φ = 120
• d = 7⁻¹ mod 120 = 103
• c = 5⁷ mod 143 = 47
• m = 47¹⁰³ mod 143 = 5

8.6 ElGamal 计算

• 密钥：p, g, x；y = g^x mod p
• 加密：选 r；C1 = g^r mod p；C2 = y^r·m mod p
• 解密：m = C2·(C1^x)⁻¹ mod p

注意：题目若给两个使用相同 r 的密文，优先想 C2₁/C2₂ = m₁/m₂。

8.7 Diffie-Hellman 计算

• A = g^a mod p，B = g^b mod p
• 共享密钥 K = B^a = A^b = g^{ab} mod p
• 例：p=97, g=5, a=36, b=58：
  • A = 50，B = 44
  • K = 44³⁶ mod 97 = 75
• 注意：DH 只做密钥交换，不提供认证，不能抵抗中间人攻击。

8.8 Shamir 门限计算

• 构造：f(x) = S + a1x + a2x² + ... + a_{t-1}x^{t-1} mod p
• 份额：(x_i, f(x_i))
• 恢复：S = f(0) = Σ y_i · λ_i mod p
• λ_i = ∏_{j≠i} (0 - x_j)/(x_i - x_j) mod p
• 例：p=17, f(x)=5+3x，份额 (1,8),(2,11),(3,14)。
  • 用 (1,8),(2,11)：λ1=2, λ2=-1，S=2×8-1×11=5。

8.9 生日攻击计算

• 找一个与指定摘要相同的输入：约 0.69 × 2^m 次（PPT 简化用 2^{m-1}）。
• 找任意一对碰撞：约 1.18 × 2^{m/2} 次。
• 例：64 位哈希找碰撞约 1.18 × 2³² 次；128 位找碰撞约 2⁶⁴ 次。
• 结论：哈希值越长，抗碰撞越强；但输出长度翻倍，工作量大约平方级增加。

8.10 综合设计题：双向认证 + 会话密钥

目标：A、B 双向认证，并建立共享会话密钥。

方案（基于公钥/证书）：

1. A 发送 ID_A 和随机数 N_A。
2. B 发送 ID_B、随机数 N_B、Cert_B。
3. A 验证 Cert_B，生成会话密钥 K，用 B 的公钥加密 K，并用自己的私钥签名 (N_A || N_B || K)，发送给 B。
4. B 验证 A 的证书和签名，解密得到 K。
5. B 用 K 加密 N_B 或发送确认消息，完成密钥确认。
6. 双方用 K 保护后续通信。

安全分析：

• 双向认证：双方用证书/签名验证身份。
• 抗重放：随机数 N_A、N_B 保证新鲜性。
• 机密性：会话密钥用 B 公钥加密。
• 完整性/不可否认：签名保护关键消息。
• 前向保密：若使用 DH 协商而非直接加密传输密钥，可进一步增强。

---

9. 对比表汇总

9.1 对称密码 vs 公钥密码

对比项	对称密码	公钥密码
密钥	双方共享同一密钥	每人一对公私钥
密钥分配	困难，需安全信道	公钥可公开，解决分配问题
速度	快	慢
用途	大数据加密	密钥管理、数字签名、短数据加密
不可否认性	不支持	支持
典型算法	DES、AES、SM4	RSA、ElGamal、ECC、SM2

9.2 流密码 vs 分组密码

对比项	流密码	分组密码
处理单位	比特/字符	固定长度分组
记忆性	有	无
速度	快	较慢
错误传播	同步流密码基本不传播	与模式有关
扩散	弱/无	强
典型算法	LFSR 流密码、RC4	DES、AES、SM4

9.3 Feistel 网络 vs SPN

对比项	Feistel	SPN
加解密结构	相同，子密钥逆序	通常不同
轮函数	不需要可逆	每层需可逆
扩散速度	较慢，通常多轮	较快
典型算法	DES、SM4	AES

9.4 DES / AES / SM4

算法	分组长度	密钥长度	轮数	结构	安全性
DES	64 位	有效 56 位	16	Feistel	已不安全，可穷举
3DES	64 位	112/168 位	48	Feistel	仍可用，但慢
AES	128 位	128/192/256 位	10/12/14	SPN	目前安全
SM4	128 位	128 位	32	类 Feistel	国密标准，安全

9.5 RSA / ElGamal / ECC / SM2

算法	数学难题	加密特点	签名	密钥长度感受
RSA	大整数分解	c=m^e mod n	支持	2048 位以上
ElGamal	离散对数	密文两倍长，随机化	支持	1024/2048 位以上
ECC	椭圆曲线离散对数	短密钥、高效率	支持	256 位左右
SM2	ECC + SM3	国密标准	支持	256 位

9.6 数字签名算法对比

算法	基础	签名长度	特点
RSA 签名	大整数分解	与模数同长	简单，需填充
ElGamal 签名	离散对数	较长	随机化，k 不能重复
DSA	离散对数	较短	美国标准
Schnorr	离散对数	短	效率高，可证明安全
SM2 签名	ECC	短	国密标准，配合 SM3

9.7 运行模式对比（速记）

模式	相同明文分组	IV/Nonce	可并行	错误传播	完整性
ECB	密文相同	不需要	加密/解密	仅当前块	不提供
CBC	密文不同	随机 IV	解密可并行	当前+下一块	需额外 MAC
CFB	密文不同	随机 IV	解密可并行	有限 s+1	需额外 MAC
OFB	密文不同	唯一 IV	密钥流可预计算	无	不提供
CTR	密文不同	唯一 nonce	加密/解密	无	不提供

---

10. 高频易混点

1. Hash 不是加密：Hash 用于完整性，不可逆；加密用于保密性，可逆。
2. MAC 不能防否认：因为双方共享密钥；数字签名可以。
3. 公钥加密慢：实际系统用混合加密：对称密钥加密数据，公钥加密会话密钥。
4. RSA 不要直接签名原始消息：要先哈希并填充，否则可伪造。
5. ElGamal / DSA 的随机数 k 绝对不能重复：重复会泄露私钥或明文。
6. CBC 的 IV 不需要保密，但必须随机、不可预测。
7. CTR 的 nonce 不能重复：重复会导致密钥流复用。
8. DES 有效密钥 56 位，不是 64 位。
9. m 序列周期为 2ⁿ-1，不是 2ⁿ。
10. 生日攻击复杂度是 2^{m/2}，不是 2^m。
11. Feistel 的轮函数不需要可逆，SPN 需要。
12. 数字签名不提供保密性，需要配合加密。
13. KDC 是对称密钥分配中心；CA 是公钥证书认证中心，二者不同。
14. Shamir 门限方案中，少于 t 个份额得不到任何秘密信息。
15. 认证和保密是两回事：认证保证来源和完整性，保密保证不被看懂。

---

11. 考前最后 24 小时速记

必背定义

• CIA 三要素、被动/主动攻击、Kerckhoffs 原则。
• 扩散、混淆、Feistel、SPN。
• Hash 的单向性、弱抗碰撞、强抗碰撞。
• 数字签名的认证、完整性、不可否认性。
• 陷门单向函数。
• KDC、CA、PKI、证书、CRL/OCSP。
• Shamir 门限方案。

必背公式

• 移位密码：c = (m+k) mod q，m = (c-k) mod q
• 仿射密码：c = (k1m+k2) mod q，m = k1⁻¹(c-k2) mod q
• RSA：n=pq，φ=(p-1)(q-1)，ed ≡ 1 mod φ，c=m^e mod n，m=c^d mod n
• ElGamal：y=g^x mod p，C1=g^r mod p，C2=y^r·m mod p，m=C2·(C1^x)⁻¹ mod p
• DH：K=B^a=A^b=g^{ab} mod p
• 生日攻击：碰撞约 1.18×2^{m/2} 次
• HMAC：H((K⊕opad)||H((K⊕ipad)||M))
• Shamir：f(x)=S+a1x+...+a_{t-1}x^{t-1} mod p，S=f(0)

---

12. 复习打卡清单

• [ ] 第 1 章：三要素、攻击类型、Kerckhoffs、古典密码公式
• [ ] 第 2 章：流密码分类、LFSR、m 序列、Golomb 三假设
• [ ] 第 3 章：DES、AES、SM4、ECB/CBC/CFB/OFB/CTR
• [ ] 第 4 章：Hash 性质、生日攻击、MD5/SHA、HMAC
• [ ] 第 5 章：RSA、ElGamal、DH、ECC、SM2
• [ ] 第 6 章：RSA 签名、ElGamal 签名、DSA、Schnorr
• [ ] 第 7 章：KDC、PKI、Shamir 门限、双向认证
• [ ] 手算：RSA、ElGamal、DH、Shamir、生日攻击各 2 题
• [ ] 过一遍总复习 123 章 PPT
• [ ] 过一遍总复习 4567 章 PPT
• [ ] 做一套往年题/模拟题并订正

本文件仅供个人复习使用。