Lecture 4：公开密钥加密¶
学习目标¶
完成本讲后，应当能够：
- 解释对称密钥分发的扩展性问题，以及公开密钥加密的基本模型；
- 根据模运算完成小规模 RSA 和 ElGamal 加解密；
- 区分 RSA 因数分解问题、离散对数问题与 Diffie–Hellman 问题；
- 说明 Diffie–Hellman 密钥交换为何无法单独抵御中间人攻击；
- 比较对称密码与公开密钥密码的用途和性能。
1. 为什么需要公开密钥密码¶
\(n\) 个参与者若彼此两两共享密钥，需要 \(n(n-1)/2\) 把长期密钥，每人要管理 \(n-1\) 把。在线密钥分发服务器可把长期密钥数量降到 \(n\)，再分发会话密钥，但服务器会成为性能瓶颈和单点故障。
公开密钥密码（public-key cryptography，也称 asymmetric cryptography）为每个用户生成一对密钥：公开密钥可以发布，私有密钥由持有人保密。发送方用接收方的公开密钥加密，只有对应私有密钥持有人能解密。它可简化密钥分发，但速度通常比对称加密慢，因此常用公开密钥机制保护短小的会话密钥，再由对称密码保护大量数据。
其安全性依赖单向函数（one-way function）背后的计算困难问题：正向计算容易，反向求解在计算上不可行。课件聚焦因数分解与离散对数相关问题。
2. RSA¶
RSA（Rivest–Shamir–Adleman）基于大整数因数分解相关的困难性。密钥生成步骤如下：
- 随机选择两个大素数 \(p,q\)，计算 \(n=pq\)；
- 计算 \(\varphi(n)=(p-1)(q-1)\)；
- 选择 \(e\)，使 \(\gcd(e,\varphi(n))=1\)；
- 求 \(d=e^{-1}\bmod\varphi(n)\)，即 \(ed\equiv1\pmod{\varphi(n)}\)。
公开密钥为 \((n,e)\)，私有密钥包含 \(d\)（真实实现还会保存 \(p,q\) 等参数以加速运算）。对消息数值 \(M\)：
小例子¶
取 \(p=13,q=11\)，则 \(n=143\)、\(\varphi(n)=120\)。取 \(e=7\)，扩展欧几里得算法得到 \(d=103\)，因为 \(7\cdot103\equiv1\pmod{120}\)。加密 \(M=10\)：
解密 \(10^{103}\bmod143=10\)。这类小参数只用于演算，不具备实际安全性。
安全性理解¶
若攻击者能分解 \(n\) 得到 \(p,q\)，就能计算 \(\varphi(n)\) 并求出 \(d\)。RSA 问题（RSA problem）与因数分解问题密切相关，但课件指出二者并未被证明等价。实际 RSA 需要足够大的参数，并使用标准填充方案；直接对原始消息套用幂运算不适合作为实际加密实现。课件中的密钥长度建议属于课件编写时的历史背景，现实系统应遵循当前标准和实现规范。
3. ElGamal 加密¶
ElGamal 加密建立在有限域上的离散对数困难性之上。选取大素数 \(p\) 和生成元 \(g\)，私钥 \(x\) 随机选取，公开值为 \(y=g^x\bmod p\)。公钥是 \((p,g,y)\)，私钥是 \(x\)。
加密消息 \(M\) 时，每条消息都随机选择新的 \(r\)：
密文为 \((A,B)\)。解密时先计算共享值 \(K=A^x\bmod p=g^{rx}\bmod p\)，再计算：
新随机数使同一明文重复加密通常会得到不同密文。参数和随机数必须按密码规范生成；示例中的小素数仅用于手算。
4. 离散对数与 Diffie–Hellman 密钥交换¶
离散对数问题（Discrete Logarithm Problem，DLP）：给定素数 \(p\)、底数 \(g\) 和 \(y=g^a\bmod p\)，求指数 \(a\)。正向模幂容易，反向求离散对数在合适参数下困难。
Diffie–Hellman 问题（Diffie–Hellman Problem，DHP）：给定 \(A=g^a\bmod p\) 与 \(B=g^b\bmod p\)，求 \(g^{ab}\bmod p\)。DLP 可解时便可解 DHP；反向是否成立并非课件所作假设。
Diffie–Hellman 密钥交换中，Alice 和 Bob 分别发送 \(g^a\) 与 \(g^b\)，随后各自计算：
双方得到相同的共享秘密，可将其派生为对称会话密钥。这个过程本身只建立共享秘密，不提供身份认证。主动攻击者 Trudy 可以分别与 Alice、Bob 建立不同秘密并转发消息，实施中间人攻击（man-in-the-middle attack，MITM）。因此需配合认证机制，例如经认证的公钥或数字签名。
5. 三种困难问题的关系¶
| 问题 | 已知内容 | 要求结果 | 关联方案 |
|---|---|---|---|
| 因数分解 | \(n=pq\) | 求 \(p,q\) | RSA 的安全基础之一 |
| DLP | \(g^a\bmod p\) | 求 \(a\) | ElGamal、Diffie–Hellman |
| DHP | \(g^a,g^b\bmod p\) | 求 \(g^{ab}\bmod p\) | Diffie–Hellman 密钥交换 |
不要把 Diffie–Hellman 误称为加密算法：它用于协商共享密钥，本身不加密任意消息。
6. 对称密码与公开密钥密码¶
| 对称密钥密码 | 公开密钥密码 |
|---|---|
| 双方共享秘密密钥 | 每人有公开密钥与私有密钥 |
| 速度快，适合大量数据 | 速度较慢，适合密钥建立、签名等用途 |
| 难点是安全分发共享密钥 | 可公开分发公钥，但需确认公钥身份真实 |
| 例：AES | 例：RSA、ElGamal |
复习重点¶
- RSA 中 \(e\) 与 \(\varphi(n)\) 互素，\(d\) 是 \(e\) 模 \(\varphi(n)\) 的逆元；
- ElGamal 每次加密都需要新的随机数 \(r\)；
- DH 是密钥交换，未经身份认证时容易受到 MITM；
- 非对称密码与对称密码通常协同工作，而非相互替代。