COMP3357 第 1 讲：私钥密码学导论（Private-Key Cryptography）

符号约定：在以下内容中，$\Pr[A]$ 表示事件 A 发生的概率，$\Pr[A \mid B]$ 表示在事件 B 已经发生的条件下，事件 A 发生的概率。

开场

现代密码学（modern cryptography）研究如何在存在攻击者的环境中保护信息。日常生活里的网上交易、邮件加密、生物识别认证（biometric authentication）、社交聊天、数字合同签名（digital contract signature）都离不开密码学机制。

密码学最基本的目标可以先概括成三类。

围绕这些目标，现代密码学会研究一组基础原语（cryptographic primitives），例如：

• 对称密钥加密（symmetric-key encryption）
• 公钥加密（public-key encryption）
• 消息认证码（message authentication code, MAC）
• 哈希函数（hash function）
• 数字签名（digital signature）
• 零知识证明（zero-knowledge proof）
• 秘密共享（secret sharing）
• 承诺方案（commitment scheme）

量子密码学（quantum cryptography）还会讨论量子密钥分发（quantum key distribution, QKD）和量子随机数生成（quantum random number generation, QRNG）等主题。

私钥密码学的基本问题

私钥密码学（private-key cryptography） 也叫对称密钥密码学（symmetric-key cryptography）、单钥密码学（single-key cryptography）或共享密钥密码学（shared-key cryptography）。

基本通信模型里有三类角色。

• Alice 和 Bob 是诚实通信方，希望通过不安全信道（insecure channel）私密通信。

这里，诚实通信方（honest user） 指的是通信双方遵守协议、诚实地执行算法。Alice 和 Bob 事先共享同一个秘密密钥（secret key）。

• Eve 是攻击者，可以窃听信道中的信息。
• Alice 和 Bob 事先共享同一个秘密密钥（secret key）。

安全目标是：即使 Eve 能看到信道里的密文（ciphertext），也不能理解原始明文（plaintext）。

私钥加密框架

私钥加密的通信过程可以分成三步。

1. Alice 和 Bob 先通过安全信道（secure channel）建立随机秘密密钥 $k$。
2. Alice 用密钥 $k$ 把明文 $m$ 加密成密文 $c$，再把 $c$ 通过不安全信道发给 Bob。
3. Bob 用同一个密钥 $k$ 解密 $c$，恢复出明文 $m$。

攻击者在不安全信道上只能看到密文。理想情况下，密文对攻击者应当看起来像随机比特，不能暴露明文的有效信息。

形式化地，一个定义在消息空间 $\mathcal{M}$ 上的私钥加密方案由三个算法组成。

这里的 $\leftarrow$ 表示算法可能使用随机性。也就是说，同一个明文 $m$ 和同一个密钥 $k$ 多次加密，可能得到不同密文。符号 $:=$ 通常表示确定性赋值，解密算法一般被视为确定性算法。

随机算法

很多算法都会用到随机性，但这里的“随机”通常不是凭空生成的，而是由伪随机数生成器（PRNG, Pseudorandom Number Generator）模拟出来的。PRNG 依赖一个初始输入参数，叫作随机种子（Random Seed）。由于计算机底层由确定性的逻辑门构成，它本身不能直接创造真正的随机，只能通过一套固定的数学规则去模拟随机效果；种子就是这套规则的起点。

PRNG 的运行方式可以理解成一个状态转移过程：

1. 初始化：系统接收种子，例如整数 $S_0$，并据此设定内部状态。
2. 迭代计算：通过确定性的转换函数得到下一个状态 $S_1 = f(S_0)$，再从中提取输出的随机数 $R_1$。
3. 确定性输出：只要初始种子相同，不管在什么设备上运行，生成出来的数列都会完全一致。

这也是为什么随机算法既可以服务于“每次都不一样”的业务需求，也可以服务于“每次都完全复现”的调试需求。前者常见于题目抽取、列表打乱、动态采样等场景，通常直接让系统从时间戳或环境状态中自动取种子；后者常见于随机地图、复杂结算和问题复现，开发者会手动固定种子，让同样的输入始终得到同样的输出。

import random

questions = ["Chapter1_Q1", "Chapter2_Q3", "Chapter3_Q1"]
random.shuffle(questions)  # 不显式设置种子时，每次打乱顺序都可能不同

using System;

Random mapRng = new Random(9527);
int nextNodeX = mapRng.Next(0, 100);
// 只要种子是 9527，第一个结果就会保持一致

在密码学里，这一层就不能随便用了。普通随机库的状态转移往往过于简单，攻击者如果拿到几个连续输出，可能就能反推出种子，进而预测后续结果。真正需要安全性的场景必须使用密码学安全的伪随机数生成器（CSPRNG, Cryptographically Secure Pseudorandom Number Generator）。

CSPRNG 的几个关键点是：

• 高熵种子（Entropy）：种子不能只是时间戳，而应来自操作系统维护的高质量熵源。
• 不可预测性（Unpredictability）：即便攻击者截获大量输出，也不应能反推出内部状态或预测下一个比特串。
• 安全接口：工程上应使用安全随机接口，例如 Python 的 secrets，或依赖操作系统提供的安全随机源，如 /dev/urandom 和系统安全 API。

正确性

加密方案首先要满足正确性（correctness）。对所有明文 $m \in \mathcal{M}$，以及所有由 $\mathrm{Gen}$ 生成的密钥 $k \in \mathcal{K}$，应当有：

这句话的意思很直接：如果加密和解密使用同一个密钥，那么解密应当恢复原始明文。私钥密码学被称为“对称”的原因，也正是通信双方使用同一个秘密密钥。

Kerckhoffs 原则

Kerckhoffs 原则（Kerckhoffs’s principle）是现代密码学的基本原则之一。一个密码系统即使所有设计细节都被攻击者知道，只要密钥仍然保密，也应当保持安全。

因此，安全性不应依赖算法保密。加密方案、算法细节和实现思路都可以公开，真正需要保密的是随机选择并妥善保存的密钥 $k$。

这个原则把安全通信问题收束为密钥问题：密钥如何随机生成、如何安全传输、如何安全存储。

以前大家是怎么做的？

古典密码可以帮助理解“密钥空间够大”为什么只是必要条件，而不是充分条件。

Scytale 密码

Scytale 是一种很早的换位类密码（transposition cipher）。发送方把皮条绕在固定直径的木棒上写字，展开后文字顺序被打乱；接收方用相同直径的木棒重新绕回去，就能读出原文。

这种方法的安全性很弱，因为结构简单，攻击者只要尝试不同直径或排列方式，就可能恢复明文。

移位密码

移位密码（shift cipher）也叫 Caesar cipher。它把每个英文字母整体向后移动固定位置。若把大写英文字母表示为 $0$ 到 $25$，密钥为 $k \in \{0,\dots,25\}$，则：

解密时反向移动：

例如明文 $\mathrm{GOOD}$ 使用密钥 $k = 2$ 时，密文为 $\mathrm{IQQF}$。

移位密码的问题在于密钥空间太小，只有 26 种可能。攻击者拿到密文后可以直接枚举所有密钥，这叫穷举搜索攻击（exhaustive-search attack）或暴力破解（brute-force attack）。如果密文足够长，通常只有一个解读结果像自然语言。

这引出密钥空间充分性原则（sufficient key-space principle）：安全加密方案的密钥空间必须足够大，使穷举搜索在现实中不可行。

单表代换密码

单表代换密码（mono-alphabetic substitution cipher）比移位密码更一般。它不只做整体平移，而是用一个字母表置换（permutation）替换每个字符。

密钥是字母表上的双射：

加密和解密为：

它的密钥空间大小是 $26!$，约为 $2^{88}$。从暴力破解角度看，这已经很大。但它仍然不安全，因为固定替换会保留自然语言的统计结构。

频率分析（frequency analysis）可以统计密文中字符、双字母组合（bigram）和三字母组合（trigram）的出现频率，再和英语文本的常见频率比较。长密文中最常见的密文字母很可能对应英语里高频的 E。这说明大密钥空间不能自动保证安全。

多表代换密码

多表代换密码（poly-alphabetic substitution cipher）允许同一个明文字母在不同位置对应多个密文字母。二战中的 Enigma 转子机（Enigma rotor machine）可以放在这条思路下理解。

如果可用代换表数量有限，并且在长明文中周期性重复，攻击者仍然可能利用统计规律进行密码分析（cryptanalysis）。

攻击模型

讨论密码系统安全性时，必须先说明攻击者能做什么。常见攻击模型包括以下几类。

攻击模型越强，对安全定义的要求通常越高。例如某些密码系统可以抵抗 CPA，但无法抵抗 CCA。后续更严格的安全定义会围绕这些模型展开。

私钥加密的概率视角

现代密码学会把密钥、明文和密文看成随机变量（random variables）。通常记作：

• $K$ 表示密钥随机变量
• $M$ 表示消息随机变量
• $C$ 表示密文随机变量
• $k,m,c$ 表示它们的具体取值

密钥分布由 $\mathrm{Gen}$ 决定：

消息分布 $\Pr[M=m]$ 则描述攻击者在看到密文之前，对 Alice 可能发送什么消息的先验认知。通常假设 $K$ 和 $M$ 相互独立，并且 $\mathrm{Gen}$ 从密钥空间中均匀随机选取密钥。

给定明文 $m$ 时，密文 $c$ 的条件概率为：

密文 $c$ 的总体概率由全概率公式（law of total probability）得到：

观察到密文 $c$ 后，明文为 $m$ 的后验概率可以用贝叶斯定理（Bayes’ theorem）计算：

这些公式的意义在于，安全性可以不只用“能不能破解”这种直觉语言描述，还可以用观察密文前后的概率变化来描述。

一个移位密码的概率例子

考虑移位密码，并令密钥在 $\{0,\dots,25\}$ 上均匀分布，即对所有 $k$ 都有 $\Pr[K=k]=1/26$。

如果消息只可能是单个字符 a 或 r，且：

那么 $\Pr[C=\mathrm{b}] = 1/26$。原因是无论明文是 a 还是 r，都各自存在唯一密钥能把它加密成 b。

再看字符串例子。设：

密文 sri 可以由 one 在某个特定移位下得到，但不能由 two 在任何移位下得到。因此：

这个例子展示了消息分布、密钥分布和加密函数如何共同决定密文分布。

完美保密

完美保密（perfect secrecy）是 Shannon 提出的信息论安全概念。它先考虑一个较弱但清晰的威胁模型：攻击者进行单次唯密文攻击，知道 $\mathrm{Gen}$、$\mathrm{Enc}$、$\mathrm{Dec}$，也知道消息空间上的概率分布，但不知道 Alice 和 Bob 共享的秘密密钥。

一个定义在消息空间 $\mathcal{M}$ 上的加密方案 $(\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ 是完美保密的，当且仅当对任意消息分布、任意 $m \in \mathcal{M}$，以及任意满足 $\Pr[C=c]>0$ 的密文 $c \in \mathcal{C}$，都有：

也就是说，攻击者看到密文以后，对任何明文 $m$ 的后验概率（posterior probability）与先验概率（prior probability）完全相同。密文没有给攻击者提供关于明文的额外信息。

这个定义不限制攻击者的计算能力，因此它比“攻击者算不动”更强。它要求密文本身在信息论意义上不泄露明文信息。

小结

私钥密码学的第一层结构可以这样理解：通信双方共享秘密密钥，用加密和解密算法在不安全信道上保护明文。

首先，我们需要保证加密方式是正确的，即正确性（Correctness） ，这样我们才能保证 Bob 能恢复消息；

Kerckhoffs 原则要求算法公开后仍然安全，因为我们永远无法保证加密方式不被泄露，所以必须假设攻击者知道所有的加密细节。因此，我们要妥善保管密钥 $k$；

攻击模型规定 Eve 的能力边界，概率语言则让安全定义可以被严格表述。移位密码和代换密码说明，密钥空间足够大只是最基础要求，真正的安全还要抵抗语言统计、已知明文、选择明文和选择密文等更强攻击。

返回目录

• 回到 COMP3357 课程笔记目录