L03 密码学：一把谁都能扣上、只有你能打开的挂锁

一句话版

这一讲把上一讲造好的数论零件装成三台机器——对称加密、RSA、Diffie-Hellman——并回答一个问题：钥匙怎么送到对方手里。

一个类比：一把谁都能扣上、只有你能打开的挂锁

对称加密是一把普通挂锁配两把一模一样的钥匙。你和对方各拿一把，锁上的箱子只有你俩能开。课件 p.4 说它安全要满足两个前提：锁本身够结实，钥匙只在你俩手里。麻烦出在第二条——两把钥匙得先见一面才能分到手，p.5 模型图里那条 Secure Channel 画的就是这次见面。锁再结实，见面这一步解决不了。

凯撒密码是一把只有 25 个刻度的密码锁。p.8 的公式 E(k, p) = (p + k) mod 26 里 k 只能取 1 到 25，一个个拨过去必然打开；p.9 那句《模仿游戏》里的密文位移是 4，破出来是 SEE YOU IN TWO LONG WEEKS DEAREST FRIEND。p.7 列了暴力枚举成功的三个条件：算法已知、密钥空间小、明文认得出来。

一次一密是每次都换一把跟箱子一样大的新锁。密钥随机、至少与明文等长、用一次就扔（p.10–11），于是拨到任何一个刻度都能开出一句通顺的话，你分不清哪句才是真的。p.14 那张 Cluedo 例子就在演这件事：同一段密文用两把不同的钥匙解出两句都说得通的明文。p.13 在 XOR、AND、OR 中选 XOR，因为另外两个逐位运算不能保证可逆；不是说所有加密构造只能用 XOR。

公钥密码是把打开的挂锁免费发给所有人。谁都能拿一把扣上箱子，但只有锁的主人有钥匙。p.34 画的 public-key ring 就是那一排挂在门口的开着的锁。这一下把「先见面」这步删掉了：想给我寄东西，取我的锁扣上就行。

类比在哪里失效：DH 更像「混颜料」：交换混合色，再各加自己的秘密成分，两边得到同色。但类比不提供身份认证，攻击者可能在中间分别和双方交换。公钥挂锁还隐含一个前提：确认拿到的确实是对方的公钥。签名是另一种算法，不能理解成把挂锁倒过来用。大整数分解困难是 RSA 的重要安全依据，但小参数、不当填充或密钥泄漏仍会让系统失守（补充）。

概念卡

1. 对称密码模型与它的死结

人话定义：收发双方共用一把密钥 K，加密 Y = E(K, X)、解密 X = D(K, Y)；攻击者看得到密文 Y，目标是估出 X̂ 或 K̂。

例子：p.5 模型图里密钥从 Key Source 出发走一条单独的 Secure Channel 到接收方。这条通道在图上是一根线，在现实里是快递员、外交邮袋或者两个人见面——每一种都比算法本身贵得多。DES、AES 解决的是「锁够不够结实」，不解决「钥匙怎么送」。

常见误解

以为一次一密只能停留在理论 → 它可实现 perfect secrecy（完美保密），但要求密钥独立、均匀随机、等长且绝不重用，分发与存储代价很高。不要把「经典的完美保密构造」背成「唯一体系」（p.15，补充校订）。

2. RSA：两把钥匙各走一边

人话定义：教材的裸 RSA 从两个不同大素数造出 n，公钥 {e, n} 公开，私钥 {d, n} 自留，e 与 d 满足 ed ≡ 1 (mod φ(n))。加密 C = Mᵉ mod n，解密 M = Cᵈ mod n。

例子：p.21 的标准例子 p = 17、q = 11，n = 187，φ = 160，e = 7，d = 23。88 加密：88² = 77，88⁴ = 132，88⁷ = 132 × 77 × 88 → 11。解密 11²³：11² = 121，11⁴ = 55，11⁸ = 33，11¹⁶ = 154，23 = 16 + 4 + 2 + 1，154 × 55 × 121 × 11 → 88。d 是怎么来的在 p.22：扩展欧几里得得到 1 = 23 × 7 − 160，所以 7⁻¹ ≡ 23 (mod 160)。

常见误解

把 n 当成秘密 → n 印在公钥上，人人可见（p.19）。秘密只有 d，以及任何能推出 d 的东西：p、q、φ(n)。这解释了 p.44 的一种攻击路径：分解 n——拿到 p、q 之后剩下两步是上一讲的作业题。另一处高发错误是 p.23 的分块：每块的数值必须小于 n，否则取模之后信息就丢了（p.19、p.23）。

3. Diffie-Hellman：不寄钥匙，各自算出同一把

人话定义：公开一个大素数 p 和它的原根 g；双方各自保留私值 a、b，交换公开值 gᵃ mod p 与 gᵇ mod p，然后各自算出 K = g^(ab) mod p。

例子：p.32 的 Exercise-3 用 p = 23、g = 5，a = 4、b = 3。

两边一致靠 (gᵃ)ᵇ = g^(ab) = (gᵇ)ᵃ（p.29）。解出 a 的离散对数能攻破 DH，但直接求共享秘密是 CDH 问题，不能声称必须先求 a。补充：512-bit 有限域 DH 已不安全；RFC 7919 的标准 FFDHE 组从 2048-bit 起。实际使用还需认证对方、公钥检查和 KDF（密钥派生），不直接把群元素当 AES 密钥。

常见误解

以为 DH 是一种加密算法 → 它先产出共享秘密 K，之后的加密还是要交给 Part 1 的对称算法（p.28）。p.40 的应用表里 DH 那一行只有「密钥交换」是 Yes，加密和签名都是 No。另一处是把四类量混在一起：公开参数（p、g）、私值（a、b）、公开值（gᵃ、gᵇ）、共享密钥（g^(ab)），考试常问「攻击者手里有哪几样」（p.27–28、p.40）。

4. 加密与签名：先分清目标，再记钥匙归谁

人话定义：encryption（加密）保护 confidentiality（保密性）；signature（签名）用私钥生成、公钥验证，支持验证消息来源与完整性。补充：真实 RSA 加密和签名使用不同编码，例如 OAEP 与 PSS，不能把签名叫作「私钥加密」。

例子：p.36 到 p.38 三张图正好是三行。

p.38 那张两层套用的图，顺序是考点：发送方先签（私钥）后加密（收件人公钥），接收方就先解密（自己私钥）后验签（发件人公钥），剥洋葱式对称。p.40 的表把每种算法能做几件事列清楚了：

常见误解

以为「公钥能解开」就证明是真签名 → 裸 RSA 的可逆算术不是安全签名方案。课件反向钥匙图只用于理解钥匙归属；工程上应使用标准签名算法，并验证公钥身份。椭圆曲线是一类数学工具，不是单个可同时完成三种功能的算法（补充，参见 RFC 8017）。

5. 陷门单向函数与分解难题

人话定义：单向函数是正算容易、逆算不可行；陷门单向函数多一把钥匙 k，知道 k 逆算就变容易。RSA 的陷门就是 d，等价地说是 p、q。

例子：p.41 的三易两难是：生成密钥对、用公钥加密、用私钥解密容易；从公钥推私钥、从公钥和密文还原明文困难。分解 n 后能求 φ 与 d，是一种攻击路径。p.45 列到 2020 年 RSA-250（829 bit），这里只记历史事实；p.17 的 1024-bit 不能当作今天的安全部署建议。

常见误解

把「单向」误记成「一一对应」 → one-way function（单向函数）要求求原像困难，不要求逆唯一；额外要求双射的是 one-way permutation（单向置换）。哈希有碰撞不等于容易求原像，碰撞抗性和原像抗性也是不同性质；MD5 不宜用作安全哈希推荐（p.42，补充校订）。

把它们串起来

四个 Part 是一条因果链。对称加密快、成熟，但钥匙送不出去（Part 1）。RSA 用「谁都能锁、只有我能开」拆掉了送钥匙这一步，代价是慢，所以实际系统里它不加密正文，只加密那把对称密钥（Part 2）。DH 走另一条路，不寄任何钥匙，双方各自算出同一把，同样只负责产出对称密钥（Part 3）。Part 4 退一步问：一个公钥体系要满足什么，RSA 为什么满足，攻它的正面路径为什么走不通。

上一讲的零件各归各位：φ(pq) 用在密钥生成，扩展欧几里得由 e 求 d。互素明文可用欧拉定理证明；88 与 187 不互素，需分别模 p、q 证明后用 CRT 合并，不能直接代入 M^φ(n) ≡ 1。课件只展示裸 RSA 算术，安全应用还需要规范填充、足够参数和正确实现（补充）。

p.46 为下一讲铺垫：加密与签名解决不同目标。普通加密不自动认证，但认证加密（AEAD）和 MAC 可提供基于共享密钥的消息认证；这与向第三方证明签名者身份不同，不能把「对称密码不能认证」当普遍结论（补充）。

课件里的坑

• [课件已订正] p.20 密钥生成流程图取自 Stallings，原图把 d 那一行写成 “Public Key”，课件用红字改成了 Private → 记订正后的版本：{d, n} 是私钥（p.20）
• [补充校订] p.30 的 g = 9 在模 23 下阶为 11，不是全群原根，却可生成子群；不能因此断言 DH 不能用。它不符合该页「全群原根」的描述。真实 DH 常使用大素数阶子群，这些小数只适合演算。
• [口径差异] p.46 划掉 authentication：可按该图讨论普通加密，但应区分消息认证和不可否认性，不推广到全部对称密码。
• [补充校订] 两把钥匙可任意交换方向不是所有公钥体系的必需条件；不要把裸 RSA 的代数性质推广到带填充的加密与签名。
• [补充] p.9 那句密文的位移是 4，而 p.8 的示例公式写的是加 3 → 两页用的 k 不同，别把 3 当默认值；猜 k 的方法是先找最短的单词（p.8–9）
• [补充] 历史长度不等于安全建议：512-bit DH 与 1024-bit RSA 不应用作新部署参数；参考 RFC 7919 与 NIST SP 800-131A Rev.2。

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——RSA 密钥生成六步、DH 里窃听者能拿到哪四个量、p.40 那张表的四行；再把下面的「变式题」算一遍；最后回查两处最容易错的地方——n 到底是不是秘密、signature 与 encryption 分别解决什么。三步做完再往下看答案。

必背

1. 对称加密安全的两个前提：算法够强、密钥事先在收发双方之间安全共享；第二条是它自己解不掉的死结，密钥要走 Secure Channel。
2. 凯撒密码密钥只有 25 种，暴力枚举可行的三条件是算法已知、密钥空间小、明文可识别；一次一密使用独立均匀随机、等长且不重用的密钥，可实现完美保密。
3. 在 XOR、AND、OR 三种逐位运算中选 XOR，已知密钥可逆；AND、OR 不能保证可逆；11011011 ⊕ 01101001 = 10110010。
4. RSA 密钥生成六步：选 p、q → n = pq → φ(n) = (p−1)(q−1) → 选 e 与 φ 互素 → d = e⁻¹ mod φ → 发布 {e, n}；私钥是 {d, n}，n 从来不是秘密。
5. 教材 RSA 用 C = Mᵉ mod n、M = Cᵈ mod n；互素时可用欧拉定理证明，一般情形用 CRT；手算用平方-乘法并逐步取模。
6. DH 做密钥协商：交换 gᵃ 与 gᵇ，得到共享秘密 g^(ab) mod p；解离散对数是一条攻击路径，裸 DH 不认证对方身份。
7. 加密用收件人公钥、解密用其私钥；签名用发件人私钥、验签用其公钥；签名不等于私钥加密，组合可先签后加密。
8. 公钥加密要求三易两难；分解 n → 算 φ → 算 d 是 RSA 的攻击路径，不是唯一风险；课件列出的 RSA-250 为 2020 年 829 bit 历史纪录。

完整例题

下面两道 take-home 适合练习手算，不代表官方承诺考试题型：给一组小参数，当场把 RSA 或 DH 跑一遍。

(1) p = 11、q = 5、e = 7、M = 6，求密钥、密文，并把密文解回去（p.49 Exercise-4）

1. n = 55，φ(n) = 10 × 4 = 40。
2. 求 d：40 = 5 × 7 + 5，7 = 1 × 5 + 2，5 = 2 × 2 + 1。回代 1 = 5 − 2 × 2 = 5 − 2 × (7 − 5) = 3 × 5 − 2 × 7 = 3 × (40 − 5 × 7) − 2 × 7 = 3 × 40 − 17 × 7，故 d ≡ −17 ≡ 23 (mod 40)。验算 7 × 23 = 161 = 4 × 40 + 1 ✓。
3. 加密 C = 6⁷ mod 55：6² = 36，6⁴ = 1296 mod 55 = 31，6⁷ = 31 × 36 × 6 → 31 × 36 = 1116 mod 55 = 16，16 × 6 = 96 mod 55 = 41。
4. 解密 41²³ mod 55，23 = 16 + 4 + 2 + 1：41² = 31，41⁴ = 26，41⁸ = 16，41¹⁶ = 36。乘起来 36 × 26 = 936 mod 55 = 1，再 × 31 = 31，× 41 = 1271 mod 55 = 6 = M ✓。
5. 答题要写全四段：n 与 φ、d 的求法（回代必须展示）、加密的平方-乘链、解密回到 M。第 4 步里 36 × 26 ≡ 1 是个可以借力的地方，遇到 ≡ 1 立刻把它划掉。

(2) p = 353、g = 3、私值 X_A = 97、X_B = 233，走一遍密钥交换并说明暴力攻击怎么做（p.50 Exercise-5）

1. A 算 Y_A = 3⁹⁷ mod 353。平方链：3² = 9，3⁴ = 81，3⁸ = 207，3¹⁶ = 136，3³² = 140，3⁶⁴ = 185。97 = 64 + 32 + 1 → 185 × 140 = 25900 mod 353 = 131，131 × 3 = 393 mod 353 = 40。
2. B 算 Y_B = 3²³³ mod 353。再算 3¹²⁸ = 185² mod 353 = 337。233 = 128 + 64 + 32 + 8 + 1 → 337 × 185 → 217，× 140 → 22，× 207 → 318，× 3 → 248。
3. 交换：A 发 40，B 发 248。
4. A 算 K = 248⁹⁷ mod 353：248² = 82，248⁴ = 17，248⁸ = 289，248¹⁶ = 213，248³² = 185，248⁶⁴ = 337 → 337 × 185 = 217，217 × 248 = 53816 mod 353 = 160。B 算 40²³³ mod 353 同样得 160。
5. 暴力枚举：已知 p = 353、g = 3、Y_A = 40、Y_B = 248，逐个算 3ᵏ mod 353，找到 k = 97 或 233 后便可算出 160。这只是解离散对数的一种办法；存在远快于逐个枚举的算法，不能用「512-bit 要试 2⁵¹² 次」证明安全。

变式题（先自己做）

同样两道，数字换掉：

(1) p = 13、q = 7、e = 5、M = 9。求 n、φ(n)、d、密文 C，并把 C 解回 M。 (2) p = 23、g = 5，A 的私值 a = 6，B 的私值 b = 15。求两个公开值和共享密钥 K，并说出窃听者手里有哪四个数。

提示

第一题算 9 的幂时注意 9⁴ mod 91 会回到一个很眼熟的数，抓住它整条链都短了。第二题 5 在模 23 下的幂可以用 5² ≡ 2 一路翻倍，19 可以写成 −4 再算。

参考答案与自检（非官方评分标准）

自检要点：① RSA 题 d 必须给出回代过程并验算 ed ≡ 1；② 加解密要写平方-乘链，避免直接展开大整数；③ DH 题要分清私值、公开值、共享密钥三类量，窃听者手里是 p、g 和两个公开值，没有 a、b。

(1) n = 91，φ(n) = 12 × 6 = 72。求 d：72 = 14 × 5 + 2，5 = 2 × 2 + 1，回代 1 = 5 − 2 × 2 = 5 − 2 × (72 − 14 × 5) = 29 × 5 − 2 × 72，故 d = 29，验算 5 × 29 = 145 = 2 × 72 + 1 ✓。加密：9² = 81，9⁴ = 81² = 6561 mod 91 = 9，于是 9⁵ = 9 × 9 = 81 = C。解密 81²⁹：81² ≡ 9，81⁴ ≡ 81，81⁸ ≡ 9，81¹⁶ ≡ 81；29 = 16 + 8 + 4 + 1 → 81 × 9 × 81 × 81，其中 81 × 9 = 729 mod 91 = 1，剩下 81 × 81 ≡ 9 = M ✓。

(2) 5² = 25 ≡ 2，5⁴ ≡ 4，5⁶ = 5⁴ × 5² ≡ 8，所以 A = 8。5⁸ ≡ 16，5¹⁵ = 5⁸ × 5⁴ × 5² × 5 ≡ 16 × 4 × 2 × 5 = 640 mod 23 = 19 = B。A 算 K = 19⁶ ≡ (−4)⁶ = 4096 mod 23 = 2；B 算 8¹⁵：8² ≡ 18，8⁴ ≡ 2，8⁸ ≡ 4，8¹⁵ = 4 × 2 × 18 × 8 = 1152 mod 23 = 2 ✓。窃听者手里是 23、5、8、19。

闪卡自测

1. 对称加密安全的两个前提是什么？哪一条是这一讲要解决的？

算法够强、密钥只在收发双方手里。第二条：密钥要事先通过 Secure Channel 送达，公钥密码和 DH 都是为了绕开这一步（p.4–5）。

2. 暴力枚举能破凯撒密码的三个条件是什么？一次一密打破了哪几条？

算法已知、密钥空间小（25 种）、明文认得出来。一次一密用与明文等长的随机密钥把密钥空间撑到和明文空间一样大，并让每个候选明文都说得通，打破后两条（p.7、p.14）。

3. 在 XOR、AND、OR 中，为什么一次一密选择 XOR？

因为这三个候选中只有 XOR 对任意固定密钥均可逆：已知结果和密钥能唯一推回输入。AND 的结果是 0 时推不出输入，OR 的结果是 1 时同样推不出（p.13）。

4. RSA 密钥生成六步各是什么？哪些量是秘密？

选 p、q → n = pq → φ = (p−1)(q−1) → 选 e 与 φ 互素 → d = e⁻¹ mod φ → 发布 {e, n}。秘密是 d，以及能推出 d 的 p、q、φ；n 和 e 公开（p.19–20）。

5. 为什么 Cᵈ mod n 一定回得到 M？

互素时 ed = kφ(n) + 1，欧拉定理给 M^(ed) ≡ M。非互素时分别在素数 p、q 下证明：M 为 0 时直接成立，否则用费马小定理；再由 CRT 合并。这覆盖包括 M = 88、n = 187 在内的全部 0 ≤ M < n（补充）。

6. p = 17、q = 11、e = 7，d 是多少？怎么来的？

d = 23。扩展欧几里得得到 1 = 23 × 7 − 160，所以 7 × 23 ≡ 1 (mod 160)（p.22）。

7. DH 里的四类量分别是什么？攻击者能拿到哪几类？

公开参数 p、g；私值 a、b；公开值 gᵃ、gᵇ；共享密钥 g^(ab)。攻击者拿到前面的公开参数和公开值，拿不到私值和共享密钥（p.27–28）。

8. DH 能不能用来加密一段消息？

不能。它先产出共享秘密 K，经 KDF 派生密钥后，再交给对称算法加密。p.40 的表里 DH 只有密钥交换是 Yes（p.28、p.40）。

9. 签名提供保密吗？为什么不能叫作私钥加密？

不提供保密。签名用私钥生成、公钥验证消息是否匹配，不是公钥把原文「解密出来」。真实 RSA 签名含标准编码，如 PSS；裸 RSA 反向运算不能单独保证抗伪造（补充）。

10. 分解 n 怎样攻破 RSA？课件列到哪一年的纪录？

分解 n 得 p、q → 算 φ(n) → 算 d；这是充分的攻击路径，不表示所有攻破 RSA 的办法都等价于分解。课件记录到 2020 年 RSA-250、829 bit，不把它称为实时最新纪录（p.44–45，补充）。

下一讲

下一讲 Digital Signature 从 p.46 那张四行小图接着讲：签的是消息的哈希而非消息本身，验签用签名者的公钥，p.40 表里的 DSS 会在那里登场。