公钥密码学的发明是密码学史上最重要的突破之一，它解决了传统对称密码学中密钥分发的根本问题。通过引入陷门函数的概念，公钥密码学使得两个从未谋面的通信方能够建立安全通信信道。本章将深入探讨公钥密码学的数学基础，重点分析RSA、椭圆曲线密码学以及离散对数问题，并讨论在量子计算威胁下的安全性挑战。
学习目标：
公钥密码学的核心是陷门函数（Trapdoor Function）的概念，它是现代密码学最重要的理论工具之一。陷门函数的存在性与P vs NP问题密切相关，虽然我们无法证明陷门函数的存在，但基于特定数学假设可以构造候选函数族。
形式化地，一个陷门函数族是一个四元组$(G, F, F^{-1}, D)$，其中：
严格的安全性定义：
对于安全参数$k$和函数族$(G, F, F^{-1}, D)$，定义以下实验：
实验 Invert_A,F(k):
1. (i, pk, td) ← G(1^k)
2. x ← D_i (均匀随机选择)
3. y ← F_i(x)
4. x' ← A(i, pk, y)
5. 如果 F_i(x') = y 则输出 1，否则输出 0
如果对所有概率多项式时间算法$A$，都有$\Pr[\text{Invert}_{A,F}(k) = 1] \leq \text{negl}(k)$，则称$F$是单向的。
陷门特性：存在概率多项式时间算法$I$，对于$(i, pk, td) \leftarrow G(1^k)$和$x \in D_i$，有： \(\Pr[I(i, td, F_i(x)) = x] = 1\)
几何直观：陷门函数可视为一个”单向门”，公开信息允许任何人进入（正向计算），但只有持有特殊钥匙（陷门）的人才能出来（逆向计算）。
公钥密码学的安全性建立在计算复杂性理论的基础之上。我们区分以下几类计算问题：
1. 单向性（One-wayness）
2. 强单向性（Strong One-wayness）
3. hardcore谓词
非均匀计算模型：考虑具有多项式大小建议字符串的算法，这更准确地刻画了实际攻击者的能力。
Rule of thumb：陷门函数的安全性通常基于平均情况困难性假设，而非最坏情况，这与传统算法分析不同。
公钥加密方案的安全性通过多层次的攻击模型来定义，从最基本的语义安全性到最强的自适应选择密文攻击安全性。
语义安全性（Semantic Security）是最基础的安全概念。直观上，它要求攻击者从密文中无法获得关于明文的任何信息。形式化定义通过不可区分性实验给出：
IND-CPA实验：
实验 IND-CPA_A,Π(k):
1. (pk, sk) ← Gen(1^k)
2. (m_0, m_1, state) ← A_1(pk)，其中 |m_0| = |m_1|
3. b ← {0,1}，c ← Enc_pk(m_b)
4. b' ← A_2(state, c)
5. 如果 b' = b 则输出 1，否则输出 0
如果对所有概率多项式时间算法$A$，都有： \(\left|\Pr[\text{IND-CPA}_{A,\Pi}(k) = 1] - \frac{1}{2}\right| \leq \text{negl}(k)\)
则称加密方案$\Pi$满足IND-CPA安全性。
更强的安全性概念：
1. 选择密文攻击（CCA1）
2. 自适应选择密文攻击（CCA2）
安全性层次关系： \(\text{IND-CCA2} \Rightarrow \text{IND-CCA1} \Rightarrow \text{IND-CPA}\)
实际意义：CCA2安全性防御恶意选择的密文攻击，这在实际系统中很常见，如选择密文填充攻击。
标准的公钥加密方案是一个三元组$\Pi = (Gen, Enc, Dec)$：
1. 密钥生成算法 $Gen: {0,1}^* \rightarrow \mathcal{K} \times \mathcal{K}$
2. 加密算法 $Enc: \mathcal{PK} \times \mathcal{M} \rightarrow \mathcal{C}$
| 效率：运行时间为$k$和$ | m | $的多项式 |
3. 解密算法 $Dec: \mathcal{SK} \times \mathcal{C} \rightarrow \mathcal{M} \cup {\perp}$
| 效率：运行时间为$k$和$ | c | $的多项式 |
正确性要求： 对于所有$k \in \mathbb{N}$，所有$(pk, sk) \leftarrow Gen(1^k)$，所有$m \in \mathcal{M}_k$： \(\Pr[Dec_{sk}(Enc_{pk}(m)) = m] = 1\)
扩展性质：
Rule of thumb：实际的公钥加密方案往往需要在安全性、效率和密文长度之间进行权衡。
RSA算法是第一个实用的公钥密码系统，由Rivest、Shamir和Adleman于1978年提出。其安全性基于大整数分解问题的困难性，建立在数论中的几个重要定理之上。
核心数学原理：
1. 欧拉函数与欧拉定理
2. 费马小定理的推广
RSA密钥生成算法详解：
算法 RSA-KeyGen(1^k):
1. 重复以下步骤直到找到合适的素数：
- p ← RandomPrime(k/2)
- q ← RandomPrime(k/2)
- 确保 |p-q| > 2^(k/2-100) (防止Fermat分解)
2. n ← p × q
3. φ(n) ← (p-1) × (q-1)
4. 选择 e ∈ {3, 5, 17, 257, 65537} 使得 gcd(e, φ(n)) = 1
5. d ← e^(-1) mod φ(n) (使用扩展欧几里得算法)
6. 返回 pk = (n, e), sk = (n, d, p, q)
加密与解密的数学描述：
完整的正确性证明：
情况1：$\gcd(m, n) = 1$（最常见情况） 由于$ed \equiv 1 \pmod{\phi(n)}$，存在整数$k$使得$ed = 1 + k\phi(n)$。 \(c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{1+k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \stackrel{\text{欧拉定理}}{\equiv} m \cdot 1^k \equiv m \pmod{n}\)
情况2：$\gcd(m, n) \neq 1$（非常罕见） 如果$p | m$但$q \nmid m$，则：
现代实现的优化技术：
1. 中国剩余定理加速（CRT）
2. 蒙哥马利阶梯算法
3. 蒙哥马利模乘算法
4. 多精度算术库的选择
密钥生成的安全考虑：
1. 强随机数生成
2. 素数生成与测试
3. 密钥质量验证
验证清单：
✓ |p - q| > 2^(k/2-100) (防Fermat分解)
✓ p, q > 2^(k/2-1) (保证足够长度)
✓ gcd(p-1, q-1) < 2^(k/4) (防common factor攻击)
✓ gcd(e, (p-1)(q-1)) = 1 (保证d存在)
✓ d > 2^(k/4) (防Wiener攻击)
现代应用中的RSA变种：
1. Multi-Prime RSA
2. Batch RSA
3. RSA-FDH（Full Domain Hash）
Rule of thumb：现代RSA实现必须使用CRT加速和侧信道防护，裸RSA运算几乎从不直接使用。密钥生成阶段的安全性往往决定整个系统的安全水平。
RSA的安全性建立在一系列相互关联但不等价的数学困难性假设之上。理解这些假设之间的关系对于正确评估RSA的安全性至关重要。
核心困难性假设层次：
1. 整数分解假设（Factoring Assumption）
2. RSA假设（RSA Assumption）
3. 强RSA假设（Strong RSA Assumption）
安全性参数与攻击复杂度：
| 密钥长度 | 安全级别 | GNFS复杂度 | 量子攻击 | 推荐状态 |
|---|---|---|---|---|
| 1024位 | 80位 | $2^{80}$ | $2^{20}$ | 已弃用 |
| 2048位 | 112位 | $2^{112}$ | $2^{21}$ | 最低要求 |
| 3072位 | 128位 | $2^{128}$ | $2^{22}$ | 推荐 |
| 4096位 | 140位 | $2^{140}$ | $2^{23}$ | 高安全 |
具体攻击算法分析：
1. 试除法（Trial Division）
2. Pollard’s rho算法
3. 二次筛法（Quadratic Sieve）
4. 通用数域筛法（GNFS）
量子攻击威胁：
Shor算法的详细分析：
侧信道攻击与实现安全性：
1. 时序攻击（Timing Attacks）
2. 功耗分析（Power Analysis）
3. 故障攻击（Fault Attacks）
量子后安全性评估：
1. 量子计算机发展时间线
2. 错误校正开销
3. Shor算法的实际限制
密码学敏捷性（Crypto-Agility）：
1. 算法无关设计
2. 混合安全方案
3. 密钥管理策略
实际攻击案例分析：
1. RSA挑战赛历史
2. 实际系统的RSA破解
3. 学术界的理论突破
前瞻性安全评估：
1. 密钥长度建议时间线
年份 | 最低要求 | 推荐长度 | 高安全级别
----------|----------|----------|------------
2025 | 2048位 | 3072位 | 4096位
2030 | 3072位 | 4096位 | 弃用RSA
2035 | 弃用 | 弃用 | 弃用
2. 迁移策略建议
Rule of thumb：RSA的实用安全性不仅依赖于数学困难性，更需要考虑实现层面的侧信道防护和量子威胁的时间线。现在就应开始规划后量子密码学的迁移路径。
裸RSA加密在实际应用中存在致命的安全漏洞，必须结合适当的填充方案才能实现语义安全性。理解这些漏洞和相应的防护措施对于安全实现至关重要。
裸RSA的根本缺陷：
1. 确定性导致的信息泄露
| 数学描述：$\Pr[m_0 = m_1 | c_0 = c_1] = 1$ |
2. 乘法同态性
3. 小指数攻击家族
PKCS #1 v1.5填充：
早期的填充标准，结构为：
0x00 || 0x02 || PS || 0x00 || M
其中$PS$是长度为$k - |M| - 3$的随机非零字节序列。
已知攻击：
OAEP填充方案详解：
结构设计：
+----------+---------+-------+
| lHash | PS | 0x01 |
+----------+---------+-------+
DB
|
+----------+
| seed |
+----------+
| |
| +-----|
| | |
+----|--+ |
| | |
MGF |
| |
+---+ |
| |
| +----+
| |
| MGF
| |
+-------+---+
| X |Y |
+-------+---+
算法步骤：
| 掩码生成：$\text{dbMask} = \text{MGF}(\text{seed}, | \text{DB} | )$ |
| 种子掩码：$\text{seedMask} = \text{MGF}(\text{maskedDB}, | \text{seed} | )$ |
安全性理论：
定理（OAEP安全性）：如果$f$是$(t’, \epsilon’)$-单向陷门置换，$G, H$是随机预言机，则OAEP-$f$是$(t, q_D, q_G, q_H, \epsilon)$-IND-CCA2安全的，其中：
实践中的考虑：
1. 掩码生成函数（MGF）
2. 参数选择
3. 随机预言模型的限制
现代替代方案：
OAEP+（PKCS #1 v2.1）：
PSS（Probabilistic Signature Scheme）填充：
虽然主要用于数字签名，PSS的设计理念对理解安全填充方案很有价值。PSS使用以下结构：
+----------+----------+----------+
| salt | M | BC |
+----------+----------+----------+
|<-- sLen -->|<-- mLen -->|<- 1 ->|
| |
+---------+ |
| H | |
+---------+ |
| | |
| +----+ |
| | |
| XOR <----- MGF <----------+ |
| | | |
| | | |
+----+ | |
| | |
|<------------ emLen ------------>|
PSS的关键特性：
实际实现的安全考虑：
1. 常量时间实现
// 错误的实现（存在时序攻击）
if (padding_check(ciphertext) == VALID) {
return decrypt(ciphertext);
} else {
return ERROR;
}
// 正确的实现（常量时间）
int valid = padding_check(ciphertext);
uint8_t result[MAX_SIZE];
conditional_decrypt(ciphertext, result, valid);
constant_time_select(output, result, error_msg, valid);
2. 侧信道防护
3. 故障注入防护
填充方案的安全性比较：
| 方案 | 安全模型 | CCA安全性 | 开销 | 实现复杂度 | 标准化 |
|---|---|---|---|---|---|
| Raw RSA | 无 | 否 | 0% | 低 | N/A |
| PKCS#1 v1.5 | 启发式 | 否 | ~1% | 低 | 广泛 |
| OAEP | ROM | 是 | ~2% | 中 | 推荐 |
| OAEP+ | ROM | 是 | ~2% | 中 | 有限 |
| PSS | ROM | N/A | ~2% | 中 | 推荐 |
现代替代技术：
1. 密钥封装机制（KEM）
2. 混合加密系统
3. 前向安全性
实施建议清单：
✓ 密码学库选择
✓ 参数配置
✓ 安全实现
✓ 运维安全
Rule of thumb：现代系统应使用OAEP填充，避免PKCS #1 v1.5，并考虑迁移到后量子安全的加密方案。更重要的是，密码学的安全性很大程度上取决于正确的实现和部署。
椭圆曲线密码学（ECC）基于椭圆曲线群的代数结构。在有限域$\mathbb{F}_p$上，椭圆曲线定义为：
\[E: y^2 \equiv x^3 + ax + b \pmod{p}\]其中$4a^3 + 27b^2 \not\equiv 0 \pmod{p}$（保证曲线非奇异）。
椭圆曲线上的点形成一个阿贝尔群，群运算定义如下：
点加法：设$P = (x_1, y_1)$，$Q = (x_2, y_2)$是曲线上两点
无穷远点$\mathcal{O}$作为群的单位元，满足$P + \mathcal{O} = P$。
椭圆曲线密码学的安全性基于椭圆曲线离散对数问题（ECDLP）：
ECDLP：给定椭圆曲线$E$上的点$P$和$Q = kP$（$k$为正整数），计算$k$在计算上不可行。
相比于普通的离散对数问题，ECDLP具有以下优势：
Rule of thumb：选择椭圆曲线时，确保群的阶$n$是大素数，避免anomalous曲线和supersingular曲线。
椭圆曲线密码学的主要优势：
标准曲线：
点乘算法：计算$kP$通常使用二进制方法或滑动窗口技术，时间复杂度为$O(\log k)$。
离散对数问题是公钥密码学的另一重要基础。在循环群$G$中：
离散对数问题（DLP）：给定生成元$g$和$y = g^x$，计算$x$。
相关的困难性假设包括：
计算Diffie-Hellman（CDH）：给定$(g, g^a, g^b)$，计算$g^{ab}$。
判定Diffie-Hellman（DDH）：给定$(g, g^a, g^b, g^c)$，判断$c = ab$是否成立。
Gap Diffie-Hellman（GDH）：CDH困难但存在DDH预言机。
这些假设之间的关系：$DLP \Rightarrow CDH \Rightarrow DDH$
计算假设关注计算特定值的困难性，而判定假设关注区分两个分布的困难性。
例如，在某些群中（如某些椭圆曲线群），DDH可能是容易的（存在有效的双线性配对），但CDH仍然困难。这种性质被用于构造基于配对的密码学协议。
Shor算法对传统公钥密码学构成致命威胁：
Shor算法复杂度：
这意味着足够大的量子计算机可以在多项式时间内破解RSA和ECC。
Post-quantum安全性：当前研究集中在量子计算机难以解决的问题：
Rule of thumb：考虑到量子计算发展，建议从现在开始规划向后量子密码学的迁移。