公钥密码与密钥交换

对称密码（→ 对称密码）的死结是密钥分发：通信双方如何在不安全信道上约定同一把密钥？公钥密码的解法是数学上难以逆转的单向函数。本章讲 Diffie–Hellman 密钥交换、RSA 与椭圆曲线、数字签名、以及后量子迁移（→ TLS 与 HTTPS）。

单向函数与陷门

公钥密码的原料是单向函数：正向容易、逆向极难；加上陷门（密钥让逆向变容易）：

离散对数： $g^x \bmod p$ 容易算，从 $g^x$ 求 $x$ 极难（大素数域）；
大整数分解：两个大素数相乘容易，乘积分解回素数极难；
椭圆曲线：曲线上点的数乘容易，逆运算（离散对数）极难——用更短的密钥达到同等安全（256 位 ECC ≈ 3072 位 RSA）。

单向函数的存在性未证（它蕴含 P ≠ NP，→ P、NP 与归约）——现代密码学建立在"这些函数是单向的"这一经验假设上。

Diffie–Hellman 密钥交换

在不安全信道上协商共享密钥：

\begin{aligned} &\text{公开：} p \text{（大素数）与 } g \\ &\text{Alice：} a \text{ 随机} \to A = g^a \bmod p \\ &\text{Bob：} b \text{ 随机} \to B = g^b \bmod p \\ &\text{共享密钥：} K = g^{ab} = A^b = B^a \end{aligned}

窃听者看到 $g, p, A, B$ ，求 $g^{ab}$ 需要解离散对数——计算性 Diffie–Hellman 假设。DH 解决密钥分发问题；中间人攻击（MITM 转发双方的密钥材料）靠认证解决——认证版 DH（签名 + DH）就是 TLS 握手的 ECDHE。

RSA 与椭圆曲线

RSA

密钥生成：大素数 $p, q$ → $N = pq$ ；欧拉函数 $\varphi(N) = (p-1)(q-1)$ ；选 $e$ 与 $\varphi(N)$ 互素， $d = e^{-1} \bmod \varphi(N)$ ；
公钥 $(N, e)$ ，私钥 $d$ ；
加密/解密： $c = m^e \bmod N$ ， $m = c^d \bmod N$ ——分解 $N$ 求 $d$ 的困难性是安全根。

RSA 的工程教训：

公钥加密慢，实践中只用来交换对称密钥或签名（数据全走 AES）；
填充必须随机（OAEP）：教科书式 RSA 是确定性的（同明文同密文）且可被选择密文攻击；
密钥 3072 位起步（2048 勉强、1024 已破）。

椭圆曲线（ECC）

曲线 $y^2 = x^3 + ax + b$ 上的点构成群：数乘 $xP$ 容易、从 $xP$ 求 $x$ （椭圆曲线离散对数）极难——没有亚指数算法（有限域 DH 有 index calculus），椭圆曲线用更短的密钥达到同等安全：

256 位（P-256、Curve25519）≈ 3072 位 RSA；
Curve25519（X25519 密钥交换、Ed25519 签名）是现代默认：常数时间、易实现、不易出错。

数字签名

签名的三重承诺：认证（确实是持有者）、完整性（未篡改）、不可否认（事后无法抵赖）：

RSA 签名：私钥"加密"哈希，公钥验证；
ECDSA / Ed25519：椭圆曲线签名，短签名快验证。

签名签的是哈希（先哈希后签），配合哈希的抗碰撞性质（→ 哈希函数与消息认证）。与 MAC 的区别：MAC 对称（双方同钥，不能给第三方证明），签名非对称（任何人可验证，不可否认）。

公钥基础设施（PKI）

信任的根：证书把"公钥 ↔ 身份"绑定，CA 签名作保（→ TLS 与 HTTPS）。证书透明度（CT）公开日志约束 CA；密钥的生命周期管理（轮换、吊销 CRL/OCSP）是工程难点——吊销在实践中几乎不工作（软失败策略让 OCSP 查询失败时放行），前向保密（临时密钥）因此更重要。

量子威胁与后量子

Shor 算法把离散对数与因数分解放进多项式时间（→ 复杂度类全景）：Shor 算法威胁 RSA 与 ECC——足够大的量子计算机一旦存在，全部现有公钥体系崩塌。

对称密码（AES）与哈希只受 Grover 平方加速——加倍密钥长度即可，威胁小；
后量子密码（PQC）：基于格（lattice）、哈希、编码的方案——NIST 标准化中（Kyber/ML-KEM 密钥封装、Dilithium/ML-DSA 签名）；
迁移的最大问题："先存后解"（harvest now, decrypt later）——今天录下的 TLS 流量，未来用量子机解——前向保密 + PQC 混合（X25519 + Kyber）正在部署（Chrome、Signal）。

本章要点

公钥密码解决密钥分发：单向函数 + 陷门；存在性未证（蕴含 P ≠ NP）
DH 在不安全信道协商密钥；中间人靠认证（签名 + DH = TLS 的 ECDHE）解决
公钥加密慢，实践中只用来交换对称密钥；RSA 填充必须随机（OAEP）
椭圆曲线用更短的密钥达到同等安全；Curve25519 是现代默认
签名三承诺：认证、完整性、不可否认；与 MAC 的区别在对称性
Shor 算法威胁 RSA 与 ECC，后量子方案正在标准化；"先存后解"让迁移今天就开始