Module 04 · 对应课件 sld4
密码学、数字签名与证书：全课最重要的一章
Cryptography, Digital Signature and Digital Certificates
样题里这一章有 35 题，是所有章节里最多的；期末的计算题（RSA、Diffie-Hellman）也全在这里。别被“密码学”吓到：你只需要会小学的乘法和除法余数，就能手算 RSA。我们从两千年前的凯撒密码开始，一步一步走到你每天上网都在用的 HTTPS 背后的数学。
学完这一章，你应该能：
- 说清明文、密文、密钥、加密、解密；对称、非对称、哈希三类密码的区别；
- 记住 DES 和 AES 的分组长度、密钥长度、轮数，知道 DES 为什么被淘汰；
- 判断“谁用谁的哪把钥匙”：保密用接收方公钥，签名用发送方私钥；
- 手算 Diffie-Hellman 和 RSA，包括选 e、求 d、按 4 位一块加密字母；
- 解释哈希的性质，以及它和加密的区别；
- 画出数字签名的签名和验证流程；说出验证数字证书要检查的三件事。
- Quiz 里 P4 的题最多。期末 Diffie-Hellman 和 RSA 各至少 15 分，老师说是“really easy 15 marks”。
- 考试数字都小于 20，最大素数是 19。计算器没有 mod 键，用除法法算余数：320 ÷ 9 = 35.55… → 320 − 35 × 9 = 5。
- 公式考试不给，必须自己背；每一步都写“公式 → 代入 → 结果”，最后验算。
按考试规格练题：刷题本 · 期末专项 DH/RSA（附满分答题模板）。
1密码学要解决什么问题
密码学的故事里永远有三个人：Alice 要给 Bob 发消息，Eve（eavesdropper，窃听者）在中间偷听。互联网就是一个“人人都能偷听”的地方：你的消息要经过路由器、Wi-Fi、运营商……任何一环都可能有 Eve。
密码学（cryptography，来自希腊语 kryptós“隐藏的” + gráphein“书写”）就是用数学把消息变成别人看不懂的样子，只有拥有正确钥匙的人才能还原。
基本术语（P4-5）
- Plaintext 明文
- 原始的、能读懂的消息，例如 HELLO
- Ciphertext 密文
- 加密后的输出，看起来像乱码，例如 XJ#94@K
- Cipher 密码算法
- 加密和解密用的数学步骤（算法）
- Key 密钥
- 一串字符或比特，和算法配合使用。算法可以公开，密钥必须保密
- Encryption 加密
- 明文 → 密文，记作 E(M) = C
- Decryption 解密
- 密文 → 明文，记作 D(C) = M
- Cryptanalysis 密码分析
- 试图破解密码系统，例如暴力破解、字典攻击、彩虹表攻击
样题 Q4-1：“The process of converting from plaintext to cipher text is known as deciphering or decryption.” 答案是 No。明文 → 密文是加密，说反了。
密码学能提供什么（P4-16）
- Confidentiality 机密性：只有授权的人能读（靠加密）；
- Integrity 完整性：收到的就是发出的（靠哈希）；
- Authentication 认证：确认消息来自谁（靠数字签名）；
- Non-repudiation 不可否认：发送者不能抵赖（靠数字签名）。
密码学能提供保密性、完整性、认证和不可否认，但不能提供可用性和隐私。机密性不等于隐私。对称加密适合加密你自己的硬盘，公钥加密适合和别人通信，TLS 是两者混合。
三大类密码（P4-11），本章的路线图
| 类别 | 钥匙数量 | 代表 | 主要用途 | 本章位置 |
|---|---|---|---|---|
| Symmetric 对称 | 1 把（双方共享） | DES、3DES、AES、RC4 | 大量数据加密 | 第 4 节 |
| Asymmetric 非对称（公钥） | 2 把（公钥 + 私钥） | RSA、Diffie-Hellman、ElGamal、ECC | 密钥交换、数字签名 | 第 5–9 节 |
| Hashing 哈希 | 不用钥匙 | SHA-2、SHA-3、MD5（已淘汰） | 完整性、存储密码 | 第 10 节 |
2从凯撒密码开始：替换、置换与“钥匙”的意义
最古老的密码学用在军事和政治上（Q&A Q21：最早用于在传递途中隐藏军事和政治机密）。凯撒大帝用过一个简单的办法：每个字母往后移 3 位，A→D、B→E……这就是替换密码（substitution）：把每个字母换成另一个。
凯撒密码机
“算法”是“字母往后移 k 位”，“密钥”就是 k。改改密钥看看效果，再想想：如果 Eve 知道算法，她最多要试几次就能破解？
答案是只需试 25 次，因为只有 25 种有意义的移位。这说明了密码学的第一条原理：
安全不能靠“算法保密”，要靠“密钥空间足够大”。DES 的设计要求里就写着：“The security of the algorithm must depend on the key”，并且算法细节必须公开（P4-21）。算法不变，换一把钥匙，结果就完全不同（P4-13）。
另外两类古典思路：置换密码（transposition），字母不变、打乱顺序（比如把 HELLO 写成 OLLEH）；乘积密码（product），把替换、置换、模运算组合起来反复做。现代的 DES 和 AES 本质上就是“多轮替换 + 置换”的乘积密码。
密钥长度：每多 1 位，难度翻倍
钥匙是一串比特（0 和 1），n 位的钥匙就有 2n 种可能（P4-14）：
- 8 位：28 = 256 种，平均试 128 次就能猜中，不用电脑都能破；
- 56 位（DES）：256 种。每秒试 100 万个，需要约 2285 年；
- 64 位：约 58.5 万年；128 位：约 1025 年。
但现实比理论危险：电脑远比每秒 100 万次快，黑客还能用几百万台僵尸机并行计算。1998 年 EFF 造了一台专用机器，56 小时就破解了 DES。所以：安全 = 算法强度 + 密钥长度。
密钥从 56 位增加到 58 位，暴力破解的时间大约变成原来的多少倍？
每多 1 位翻一倍，多 2 位就是 2 × 2 = 4 倍。这就是“指数”。
3对称加密：一把钥匙锁门也开门
Symmetric（secret-key）cryptography：加密和解密用同一把钥匙（样题 Q4-2）。记作 EK(M) = C，DK(C) = M。
一个带密码锁的箱子：你锁上寄出去，对方用同一个密码打开。问题是，你怎么把密码安全地告诉对方？打电话可能被窃听，写信可能被拆开。这就是对称加密最大的难题。
优点与缺点（P4-19）
| 优点 | 缺点 |
|---|---|
| 快：计算效率高，适合加密大量数据；实现简单；应用广泛（SSL/TLS、磁盘加密、文件加密） | 密钥分发难（最大缺点，样题 Q4-7）；扩展性差：n 个人两两通信需要 n(n−1)/2 把钥匙，100 人就要 4950 把 |
分组密码 vs 流密码（P4-15）
- Block cipher 分组密码：把消息切成固定大小的块，每块用算法和密钥加密（样题 Q4-3）。例子：DES、AES；
- Stream cipher 流密码：一次加密一位（或一个字节），例子：RC4。
分组密码还有不同的工作模式：
4DES、3DES、AES：三代对称加密标准
DES：第一个商用标准（P4-21～P4-26）
1973 年，美国国家标准局（NBS，现在的 NIST）公开征集国家加密标准。IBM 的 Lucifer 方案经过修改后被采纳，1976–77 年成为 DES（Data Encryption Standard）。
分组 64 位，密钥 56 位，16 轮。每个 64 位的块要做 16 轮代换和置换，前后各有一次置换（初始置换和最终置换）。
样题 Q4-5：DES 的密钥多长？答案是 56 位，不是 64 位。64 是分组长度。（输入的密钥其实也是 64 位，但其中 8 位是校验位，有效的只有 56 位。）
争议：IBM 原设计的分组和密钥都是 128 位，被改成了 64 和 56；S 盒是在保密条件下设计的，又不给理由，于是有人怀疑 NSA 留了“后门”（trapdoor）。很多专家在 DES 被采纳之前就认为 56 位太短。
结局：1998 年 EFF 用 56 小时破解了 DES。如今 DES 已经过时，只在老系统和教学里使用。
“DES 是 Data Encryption Standard，quiz 里有题，有学生选错。”“密钥是 56 位。有的资料写 64 位，那是完全错的：虽然输入 64 位，但 8 位是冗余的，攻击者只需要找 56 位。”
DES 被破了怎么办：加密两次、三次？
- 2DES：用两把钥匙加密两次（2 × 56 = 112 位）。听起来更强，但有中间相遇攻击（meet-in-the-middle）：从明文一端加密、从密文一端解密，在中间对上答案，工作量和破解一次 DES 差不多。所以 2DES 基本没用；
- 3DES：用 DES 做三次，慢三倍，但用得当时安全性高得多。它是过渡到 AES 之前的临时方案。
- 2DES 是两把 56 位密钥，不是一把 112 位，可以分开破，再加上中间相遇攻击，所以被放弃。
- 3DES 是 E-D-E 结构：用户给 168 位密钥，系统切成三把 56 位子密钥。如果 K1 = K2，第一步加密和第二步解密互相抵消，结果和单 DES 一样，还慢 3 倍。这种情况偶尔会发生，所以 3DES 只是临时方案。
AES：现在的金标准（P4-32～P4-40）
美国政府公开征集 DES 的替代者，经过 5 年严格评选（候选包括 MARS、RC6、Serpent、Twofish 等），最终选中两位比利时密码学家 Daemen 和 Rijmen 设计的 Rijndael，2001 年成为 AES（Advanced Encryption Standard）。2003 年起美国政府认可它保护机密信息，NSA 也用它加密绝密信息。
| 算法 | 分组长度 | 密钥长度 | 轮数 | 现状 |
|---|---|---|---|---|
| DES | 64 | 56 | 16 | 已被破解，淘汰 |
| 3DES | 64 | 112 / 168 | 48 | 过渡方案，已淘汰 |
| AES-128 | 128 | 128 | 10 | 安全，全球标准 |
| AES-192 | 192 | 12 | ||
| AES-256 | 256 | 14 |
AES 每轮做四步：SubBytes 替换、ShiftRows 行移位、MixColumns 列混合、AddRoundKey 加轮密钥（最后一轮没有列混合）。AES-128 有 2128 ≈ 3.4 × 1038 种密钥，现有计算机不可能穷举，目前也没有能破解完整 AES 的实用攻击。它被用在银行、Wi-Fi（WPA2/WPA3）、SSL/TLS、VPN 和加密货币里。
AES：块固定 128；钥匙 128/192/256；轮数 10/12/14（钥匙每多 64 位，轮数加 2）。
下面哪个是使用 64 位分组的对称密码？（样题 Q4-4）
DES 分组 64 位。RSA 是非对称算法；PGP 是邮件加密软件；AES 的分组是 128 位。
AES-256 有多少轮？
128 → 10，192 → 12，256 → 14。16 轮是 DES。
- “从 quiz 角度要知道”：AES 分组固定 128 位；密钥 128/192/256 位，分别对应 10/12/14 轮。不考 AES 结构图。
- AES 和 Rijndael 唯一的区别：Rijndael 的分组和密钥长度可以是任意 32 的倍数，AES 把它们固定了。原因是国际标准要统一参数，通信双方不用协商，也没有兼容问题。
选算法时该信什么（样题 Q4-8～Q4-11 连环题）
- 最该看重：算法已经存在多久，是否经过多年公开检验（Q&A Q23：算法要被工业界、学术界、数学和密码专家测试很多年）；
- 宣传“牢不可破”的：多半是夸大；
- “认证过的加密”：课件的观点是没有这种东西（There is no such thing as certified encryption）；
- 新算法：可以用，但要谨慎。
- 算法复杂不等于安全；厂商的数据来自理想条件，不能信；用得越久还没被破越可靠（AES 从 2001 年用到现在，RSA 从 1978 年用到现在）。
- 没有 “unbreakable”，只要算力够总能破；也没有 “certified encryption”，那只是营销说法。
- 新算法：课上大多数人选“可以用，但要谨慎”，这就是答案；“永远不用”就永远无法证明它好不好。
5公钥加密：一对钥匙，彻底解决“钥匙怎么送”
1976 年，斯坦福的两位博士生 Diffie 和 Hellman 提出了一个革命性的想法：用两把不同但数学上相关的钥匙（P4-47）。
- 公钥（public key）：公开给全世界，用来加密和验证签名；
- 私钥（private key）：只有主人自己知道，用来解密和生成签名。
规则只有一条：用其中一把加密的东西，只有另一把能解开。而且从公钥推不出私钥（Q&A Q23）。
Bob 买了很多把打开着的挂锁，发给所有人（这就是公钥），钥匙只有他自己有（私钥）。Alice 想给 Bob 寄东西，就把东西放进箱子，咔嚓锁上 Bob 的挂锁寄出。路上谁拿到箱子都打不开，连 Alice 自己也打不开了，只有 Bob 能开。钥匙从来不需要寄送，对称加密“钥匙怎么送”的难题就这样解决了。
两种用法：方向正好相反
| 目的 | 发送方用 | 接收方用 |
|---|---|---|
| 保密（只让对方看） | 接收方的公钥加密 | 自己的私钥解密 |
| 签名（证明是我发的） | 自己的私钥签名 | 发送方的公钥验证 |
- 样题 Q4-12：“非对称加密只用公钥加密和解密”是 False，它用一对钥匙。
- 样题 Q4-13：“非对称加密能用于保密但不能用于认证”是 False，两者都能。
- 样题 Q4-14：“公钥加密比对称加密更安全，因为用两把钥匙”是 False。安全取决于算法强度和密钥长度：128 位 AES 和 3072 位 RSA 强度相当。公钥解决的是分发问题，不是强度问题。
Carol 要给 Bob 发一条机密消息，她用哪把钥匙加密？（样题 Q4-21）
保密 → 用接收方的公钥。A 太含糊（是谁的公钥？）；C 是签名的用法。接着样题 Q4-22：Bob 用自己的私钥解密；Q4-24：私钥由接收方用来解密。
班上 30 个学生都要把加密作业交给教授，需要多少把公钥和私钥？（样题 Q4-23）
官方答案是 D。如果只要保密，大家都用教授的公钥加密，只需教授的 1 对钥匙；如果还要证明作业是哪个学生交的（签名），每个学生还要有自己的一对钥匙。数量取决于需求，这题考的就是这一点。
6数学准备：模运算（只要会除法就行）
RSA 和 Diffie-Hellman 都建立在模运算上。别怕，a mod n 就是 a 除以 n 的余数。
现在 10 点，再过 5 小时是几点？10 + 5 = 15，钟表上是 3 点。这就是 15 mod 12 = 3。模运算就是“绕圈计数”。
课件的例子（P4-50）：
- 15 mod 20 = 15（15 比 20 小，余数就是它自己）；
- 320 mod 9：计算器上 320 ÷ 9 = 35.5555…，取整数部分 35，再算 320 − 35 × 9 = 320 − 315 = 5。课件的方法是用小数部分 0.5555… × 9 = 5，结果一样，但小数误差容易出错，推荐“减去整数倍”的方法。
模幂：xe mod n 怎么手算
RSA 要算 181913 mod 2537 这种东西，181913 有 43 位，计算器装不下。诀窍是：每乘一次，就取一次余数，数字永远不会变大。最快的方法叫平方-乘法：
第一步：把指数写成 2 的幂之和。13 = 8 + 4 + 1（二进制 1101）。所以 513 = 58 × 54 × 51。
第二步：反复平方，每步取余。
第三步：把需要的几项乘起来，每步取余。
答案：513 mod 23 = 21。全程最大的数只有 90。
模幂计算器（带平方-乘法表）
7Diffie-Hellman：在大庭广众下约定一个秘密
问题（Q&A Q30）：Alice 和 Bob 想共用一把对称密钥，但他们只能通过 Eve 能看到一切的信道说话。怎么才能约定一把 Eve 不知道的钥匙？
- 两人公开约定一种公共颜色：黄色（Eve 也知道）；
- 各自偷偷选一种秘密颜色：Alice 红，Bob 蓝；
- 各自把秘密色混进黄色，把混合色公开发给对方：Alice 发橙色，Bob 发绿色（Eve 看得到）；
- 各自把自己的秘密色加进对方发来的混合色：Alice 得到黄 + 蓝 + 红，Bob 得到黄 + 红 + 蓝，完全相同；
- Eve 只有黄、橙、绿三种颜色。混合容易，拆分极难，她调不出最终颜色。
在数学里，“混合”就是模幂运算，“拆不开”就是离散对数难题。
算法步骤（P4-53～P4-55）
| 步骤 | A（Alice） | B（Bob） | Eve 能看到吗 |
|---|---|---|---|
| 1. 公开参数 | 选一个素数 q 和它的原根 a（课件也写作 p 和 g） | 能 | |
| 2. 选私钥 | 随机选 XA < q | 随机选 XB < q | 不能 |
| 3. 算公开值 | YA = aXA mod q | YB = aXB mod q | — |
| 4. 交换 | 把 YA 发给 B | 把 YB 发给 A | 能 |
| 5. 算共享密钥 | K = (YB)XA mod q | K = (YA)XB mod q | 不能 |
为什么两边相等？(aXB)XA = aXAXB = (aXA)XB，指数相乘的顺序无所谓。
原根是什么？课件定义：素数 p 的原根，是它的各次幂能生成 1 到 p−1 所有整数的那个数。考试题会直接给出，你不用自己找。
- 期末可能这样问：① 简述 DH 怎样工作；② 给素数、生成元和双方私密数，算双方公钥和共享密钥（15 分）；③ 追问：私密数泄露会怎样（完全不安全）、数字太小会怎样（会被试出来，实际至少 2048 位）。
- 六步：公开选 p、g → 各选私密数 → A 算 YA = ga mod p → B 算 YB → 交换公钥 → 各自算 K = Y对方自己私密数 mod p。
- DH 只交换密钥，不能加密；交换完用 AES 加密数据。
手算一个完整例子（课件 P4-62）
p = 23，g = 5；Alice 选 a = 6，Bob 选 b = 15。
Diffie-Hellman 计算器
默认是 Q&A Q30 的例子（q = 353，g = 3，Alice 97，Bob 233，结果 40 / 248 / 160）。可以换成课件其他例题验证。
P4-63 例 8（p = 29，g = 2，a = 5，b = 13）：课件写 B = 213 mod 29 = 27，K = 26，这是错的。正确值是 B = 14，K = 19。用上面的计算器输入就能验证。考试遇到要自己算，别照抄课件。
- DH 只用于交换密钥，不能加密或解密消息（P4-51）；
- 安全性基于离散对数难题：已知 g、x、p，求 y = gx mod p 很容易；已知 y、g、p，反求 x 极难（样题 Q4-16：True）；
- 用于 SSL 的密钥交换；TLS 1.3 只保留了 ephemeral DH（模块 5）；
- 弱点：DH 本身不验证对方身份，可能被中间人攻击，所以 TLS 会用签名保护它。
Diffie-Hellman 能直接用来加密一封邮件吗？
课件原话：“only for Key Exchange and does NOT Encrypt or Decrypt the message.”
8RSA：最常用的公钥系统，手算全流程
RSA 以三位 MIT 教授 Rivest、Shamir、Adleman 的姓氏命名，1978 年发表（英国 GCHQ 在 1973 年就秘密发现过），是最广泛使用的公钥系统（样题 Q4-15、Q4-17）。和 DH 不同，它是完整的系统：密钥生成 + 加密 + 解密 + 签名都能做。安全性来自大数分解难题：两个大素数相乘很容易，把乘积分解回去几乎不可能（样题 Q4-20）。
密钥生成五步（P4-67、P4-68）
① 选两个素数 p = 5，q = 11（真实系统里是几百位的大素数）。
② 算模数 n = p × q = 5 × 11 = 55。n 是公开的。
③ 算 φ(n) = (p−1)(q−1) = 4 × 10 = 40。φ 必须保密。
样题 Q4-18 问 p = 5、q = 11 时的 φ，选项里有 55（那是 n），正确答案 40 不在选项里，选 None of the above。Q4-19 问 n，答 55。
④ 选公钥 e：要求 1 < e < φ，且 e 和 φ 没有公因子（互素）。课件的做法：e 取素数，检查它和 p−1 = 4、q−1 = 10 有没有公因子：
- e = 2：和 4、10 都有公因子 2，✗
- e = 3：没有公因子，✓
- e = 5：和 10 有公因子 5，✗
- e = 7：没有公因子，✓
选 e = 3。
⑤ 求私钥 d：要满足 e × d ≡ 1 (mod φ)，也就是 e × d = k × φ + 1。课件的方法：d = (k × φ + 1) ÷ e，k 从 1 开始试，直到能整除：
所以 d = 27。验证：3 × 27 = 81 = 2 × 40 + 1 ✓。
公钥 = (n, e) = (55, 3)，公开给所有人；私钥 = d = 27，自己保管。
- 选 e 的三个条件（期末要写）：① 1 < e < φ；② e 是素数；③ e 与 p−1、q−1 没有公因子。标准说法只要求 gcd(e, φ) = 1，考试按老师的三条写。
- 往年原题：为什么 2 永远不能当公钥？除 2 以外的素数都是奇数，减 1 后是偶数，所以 2 一定是 p−1、q−1 的公因子，不满足第 ③ 条。
- 求 d 用 k 法：d = (kφ + 1)/e，k = 1, 2, 3… 直到整除。老师建议考试就用这个方法，省时间。
- 典型 15 分题：为什么 e ≠ 2 → 求 n、φ → 选 e、求 d → 给 M，加密再解密验证。课上的练习：p=5, q=11 自选密钥；p=17, q=19, e=5, M=25；p=13, q=23, e=7。
加密和解密
加密（用接收方公钥）：C = Me mod n 解密（用自己的私钥）：M = Cd mod n
要求：明文 M 必须小于 n。
例（P4-72）：加密 “DC”。按 A = 0, B = 1, C = 2, D = 3… 编码，DC → 32。
Q&A 大题：用 4 位一块加密 STOP（Q25）
p = 43，q = 59，e = 13。
- n = 43 × 59 = 2537；
- 字母编码（A = 00 … Z = 25）：S = 18，T = 19，O = 14，P = 15。每两个字母拼成 4 位一块：1819 1415（为什么能 4 位一块？最大的块 2525 也小于 n = 2537）；
- 逐块加密：181913 mod 2537 = 2081；141513 mod 2537 = 2182；
- 密文：2081 2182。
解密 0981 0461（Q26）
- φ = 42 × 58 = 2436；
- 求 d：d = (k × 2436 + 1) ÷ 13。一个个试太慢，有个技巧：2436 mod 13 = 5，所以需要 5k + 1 能被 13 整除，k = 5 时 26 ÷ 13 = 2 ✓。于是 d = (5 × 2436 + 1) ÷ 13 = 12181 ÷ 13 = 937；
- 0981937 mod 2537 = 0704 → 07 = h，04 = e；0461937 mod 2537 = 1115 → 11 = l，15 = p；
- 明文：“help”。
RSA 全流程计算器
输入 p、q、e（e 留空时按课件方法自动选），再输入明文（字母或数字）或密文。默认是 Q25。可以再试：p=43 q=59 e=13，密文填 0981 0461（Q26）；或者 p=13 q=17 e=5（Q27a）。
p = 19，q = 23，e = 3：n = 437，φ = 18 × 22 = 396 = 4 × 9 × 11。e = 3 和 396 有公因子 3，所以这组参数下私钥 d 根本不存在。题目只问 n 和 φ，大概正是这个原因。在计算器里输入试试，会看到提示。
RSA 的概念题（Q&A Q24、Q29）
- 单向函数：C = Me mod n，已知 M 和 e 算 C 很容易；已知 C 和 e，n 很大时反推 M 很难；
- 陷门（trapdoor）：私钥 d，掌握它就能轻松反推，M = Cd mod n；
- 公钥 e（连同 n），私钥 d；
- 安全性主要取决于分解 n 的难度；n 很大、e 选得合适，系统就是安全的；
- p 和 q 能公开吗？不能。知道 p、q 就能算出 φ，有了 φ 就能由 e 算出 d。反过来，知道 n 和 φ 也能解出 p、q。所以 p、q、φ、d 都要保密，只公开 n 和 e。
RSA 中 p = 3，q = 11，e = 7，私钥 d 是多少？
φ = 2 × 10 = 20。k = 1：(20 + 1) ÷ 7 = 3 ✓，所以 d = 3（课件 P4-76）。验证：7 × 3 = 21 = 20 + 1。
RSA 的安全性依赖于？
RSA 依赖分解；DH 和 ElGamal 依赖离散对数。这一对常被拿来对比出题。
9ElGamal、ECC 与混合系统
- ElGamal（1985）：基于 DH 的思想，安全性也基于离散对数；能加密也能签名；但密文是明文的两倍长，速度慢；
- ECC 椭圆曲线密码（1985 年提出，2005 年后才广泛使用）：用更短的密钥达到同样的安全性，在加密货币里很流行。
| 对称密钥 | ECC | RSA |
|---|---|---|
| 80 | 160 | 1024 |
| 112 | 224 | 2048 |
| 128 | 256 | 3072 |
| 256 | 512 | 15360 |
等效安全强度对照（P4-97）
混合系统：两全其美
公钥强大但慢，对称快但钥匙难送。混合系统把两者结合起来（P4-98、P4-99）：
混合系统中，公钥密码用来做什么？会话数据用什么加密？（样题 Q4-34、Q4-35）
公钥送钥匙，对称加数据。会话数据量大，需要对称算法的速度。
- 同等安全强度下速度：AES > ECC > RSA（AES-128 ≈ ECC-256；AES-256 ≈ ECC-512 ≈ RSA-15360）。老师个人认为 ECC 不会取代 RSA。ElGamal 的密文是明文的两倍，太慢，所以不用。
- 混合系统：客户端不需要任何密钥，服务器必须有 SSL 证书（证书里嵌着公钥）。会话密钥只用一次会话，下次登录换新的。
10哈希：给数据按一个“指纹”
Hash function 把任意长度的数据压缩成一串固定长度的“摘要”（digest）。它是单向的：从摘要无法还原原文。课件称它为“a special mathematical function that performs one-way encryption”（样题 Q4-33）。
就像人的指纹：从一个人很容易得到他的指纹，但只看指纹没法“复原”出这个人；两个人指纹相同几乎不可能。Q&A Q31 用的类比是软件包装盒上的防拆封条：盒子被打开过（文件被改过），一眼就能看出来。
哈希的性质（P4-108）
- 可以处理任意大小的数据，输出固定长度，计算很快；
- 单向（抗原像）：给定摘要 h，找不到 x 使 H(x) = h；
- 弱抗碰撞：给定 x，找不到另一个 y ≠ x 使 H(y) = H(x)；
- 强抗碰撞：找不到任意一对 x、y 使 H(x) = H(y)；
- 雪崩效应：输入改一个字母，输出完全变样（P4-111）。
雪崩效应实验（真实的 SHA-256）
两段只差一个字母的文字，看看它们的 SHA-256 摘要有多少位不同。红色标出两者不同的十六进制字符。
常见算法
| 算法 | 摘要长度 | 状态 |
|---|---|---|
| MD5 | 128 位 | ✗ 不安全，不要再用 |
| SHA-1 | 160 位 | ✗ 已发现碰撞攻击，不要再用 |
| SHA-2（SHA-224/256/384/512） | 名字里的数字就是长度 | ✓ 安全，最广泛使用（样题 Q4-27），比特币用 SHA-256 |
| SHA-3 | — | ✓ 安全 |
- MD5、SHA-1 不安全，不应再用；SHA-256 用于比特币。
- 网站存的是密码的哈希。如果网站说能把原密码“找回”给你，说明它没用哈希，不应该用；正常只能重置（NTU 也一样）。
哈希 ≠ 加密（Q&A Q31）
| 加密 | 哈希 | |
|---|---|---|
| 输出长度 | 和明文差不多，或更长 | 固定且短，与输入长度无关 |
| 能还原吗 | 能（解密） | 不能（不能 de-hash） |
| 需要密钥吗 | 需要 | 不需要 |
| 目的 | 机密性 | 完整性（样题 Q4-26） |
哈希函数的主要目的是？（样题 Q4-26）
哈希本身没有密钥，单独使用证明不了是谁发的，所以主要用于完整性。和私钥签名结合后才能提供认证，那是下一节的内容。
样题 Q4-26：哈希的主要目的？只有 data integrity，不提供 authentication，认证要靠数字签名。Q4-27：SHA 是算法，hash value 和 digest 都是输出。
11数字签名：证明“这是我发的，而且没被改过”
手写签名容易伪造，靠和真迹比对来验证；数字签名很难伪造，用公开的算法验证（P4-103）。它就是把公钥加密“反过来用”：发送方用自己的私钥处理消息的哈希（样题 Q4-28、Q4-31）。
签名提供什么、不提供什么
- ✓ 完整性：消息改一个字，哈希就对不上；
- ✓ 认证：只有 Bob 有私钥，能用他的公钥解开，就证明是他签的；
- ✓ 不可否认：Bob 事后不能说“不是我”；
- ✗ 不提供机密性：消息本身是明文发送的。如果还需要保密，就再用 Alice 的公钥加密整条消息，这就是课件 P4-113 的“with message protection”。
样题 Q4-29：签名能保证 integrity 和 source，选 Both；Q4-30：哈希值相等说明没有被篡改。
RSA 签名小例子（P4-117）
沿用 n = 55，e = 3，d = 27。签名 M = 51：S = 5127 mod 55 = 6（用私钥 d）。验证：63 mod 55 = 216 mod 55 = 51 = M ✓（用公钥 e）。和加密正好反过来。
发送方给哈希做数字签名，用的是哪把钥匙？
签名用自己的私钥，验签用对方的公钥。
期末手算签名不用哈希（哈希需要电脑）：签名 S = Md mod n（用私钥），验证 Se mod n = M（用公钥），和 RSA 加密正好相反。课上的例子：p=5, q=11, e=3, d=27, M=51 → S = 6，验证 63 mod 55 = 51 ✓。
12数字证书与 CA：怎么确定这把公钥真是 Bob 的
还有一个漏洞：Alice 怎么知道手里的“Bob 公钥”真的是 Bob 的？如果 Eve 冒充 Bob 发来她自己的公钥，Alice 用它去验证 Eve 伪造的签名，当然“验证通过”（P4-118：不能用发送方自己提供的公钥）。这正是公钥密码的核心难题：证明一把公钥确实属于某人（P4-47）。
陌生人说“我是张三”，你不信；他拿出政府签发的身份证，你就信了，因为你信任政府。数字证书就是公钥的“身份证”，CA（证书颁发机构）就是“发证的政府”。
Digital certificate：由 CA 签发并数字签名的电子文件，把用户名字和他的公钥绑定在一起（样题 Q4-25）。它的作用是认证公钥（样题 Q4-32），私钥永远不会出现在证书里。
X.509 证书里有什么（P4-120、P4-121）
| 字段 | 含义 |
|---|---|
| Version | X.509 版本（大多是 v3） |
| Issuer | 签发的 CA 的名字 |
| Serial number | 唯一序列号，用来查询是否被吊销 |
| Subject | 证书属于谁（真实主体，true party） |
| Public key | 主体的公钥 |
| Public key algorithm | 主体签名用的算法 |
| Digital signature | CA 用自己的私钥对证书的签名，用来检查证书是否被篡改 |
| Signature algorithm | CA 签名用的算法 |
验证证书的三件事（P4-122；Q&A Q33，必背）
- 签名：用 CA 众所周知的公钥验证证书上的签名，通过说明证书是真的、没被改过；
- 有效期：当前时间在证书的有效期内吗？过期的要拒绝；
- 吊销：有效期内 CA 也可能吊销证书。看证书字段是看不出来的，必须向 CA 查询，例如用 OCSP：把序列号发给 CA，CA 回答 good、revoked 或 unknown。
很多国家的 CA 没有监管，用户也能自己生成证书，所以公钥仍然可能被冒充（Q&A Q28）。只接受有信誉的 CA 签发的证书。新加坡常见的 CA：Verisign、GlobalSign、Netrust。模块 6 的 Equifax 案例里，一张过期 10 个月的证书导致数据外泄没被发现。
验证数字证书时，不需要检查哪一项？
私钥从不出现在证书里，也无从检查。三件事：签名、期限、吊销。
“这道题以前考过”：怎样验证证书有效？① 用 CA 的公钥验证 CA 签名，确认是可信的 CA；② 是否在有效期内；③ 是否被吊销。三项都通过，浏览器才接受。证书已经在客户手里，CA 收不回来，只能把它的序列号作废，这就是吊销（revocation）。
13未来挑战与本章小结
课件 P4-125 列出的挑战：密钥管理（生成、存储、分发）；量子计算（Shor 算法能破解 RSA 和 ECC）；同态加密（直接在密文上计算）；为 IoT 设计的轻量级密码；安全与性能的权衡；淘汰过时算法（DES、MD5、SHA-1）。
- 明文 → 密文是加密；安全靠密钥而不是靠算法保密；每多 1 位密钥，难度翻倍。
- 对称：一把钥匙，快，难在密钥分发。Block（DES、AES）vs Stream（RC4）；ECB 各块独立，CBC 链式。
- DES 64 / 56 / 16，1998 年 56 小时被破；2DES 有中间相遇攻击；3DES 是过渡；AES 128 / (128, 192, 256) / (10, 12, 14)。
- 公钥：保密用接收方公钥，签名用发送方私钥；更安全是错误说法，它解决的是分发问题。
- DH：只交换密钥，基于离散对数；Y = aX mod q，K = Y对方X自己 mod q。
- RSA：n = pq，φ = (p−1)(q−1)，e 与 φ 互素，d = (kφ + 1) / e；C = Me mod n，M = Cd mod n；基于大数分解；p、q、φ 必须保密。
- ECC 用更短的钥匙；等效强度：AES-128 ≈ ECC-256 ≈ RSA-3072。混合系统：公钥送钥匙，对称加数据。
- 哈希：固定长度、单向、抗碰撞、雪崩效应；用于完整性；MD5 和 SHA-1 已淘汰。
- 签名 = 私钥处理哈希 → 完整性 + 认证 + 不可否认，没有机密性；验签：比较两个摘要。
- 证书把名字和公钥绑定，由 CA 的私钥签名；验证三件事：签名、期限、吊销（OCSP）。
本章对应 Sample Quiz Part 4（35 题）、刷题本 P4 的 26 道自编题，以及 Q&A Q21–Q33。刷题本的期末专项按考试规格（素数 ≤ 19）出 DH、RSA、签名大题，能核对答案，附满分答题模板；期末前每种至少做 5 道。