L03b-2 公钥体系:三种用法、三易两难与分解难题
加密、签名、先签后加密各用谁的钥匙,公钥算法要满足哪三易两难,陷门单向函数是什么,以及攻破 RSA 为什么要先分解 n。
一句话版
公钥体系一对钥匙能干三件事:加密、签名、交换密钥。钥匙用哪一把,取决于你要保密还是要证明身份。它凭什么安全?因为正着算容易、倒着推很难,只有握着「陷门」的主人能倒推。对 RSA 来说,陷门就藏在 n 的两个素因子里。
RSA 和 DH 的算法本身见前两页 L03a-3 和 L03b。这一页退一步看整个体系。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| PU / PR | public key / private key | 公钥 / 私钥,下标写是谁的,如 PU_b 是 B 的公钥 |
| 保密性 | confidentiality | 只有该看的人能看到内容 |
| 数字签名 | digital signature | 用私钥生成、公钥验证,证明消息是谁发的、没被改过 |
| 单向函数 | one-way function | 正算容易、倒推不可行 |
| 陷门单向函数 | trap-door one-way function | 正算容易、倒推很难,但握有秘密就能倒推 |
| 分解 | factorization | 把 n 拆回两个素数 p、q |
一个类比:挂锁和印章
公钥加密像门口挂着一排开着的锁。谁都能取一把扣上箱子,只有锁的主人有钥匙。想给 B 寄机密,就取 B 的锁。
签名像一枚只有你有的印章,印文却人人都能比对。盖章用你的私钥,比对用你的公钥。它证明「这是你盖的」,不负责把内容藏起来。
两件事一起要,就先盖章、再上锁。收件人先开锁、再比对印章,顺序正好倒过来。
类比在哪里失效:
- 真实系统里签名是另一种算法,不能理解成「把挂锁倒过来用」,也不能把签名叫作「用私钥加密」。
- 印章比对靠的是你手里那份公钥真的属于对方。公钥被人调包,比对就失去意义。
从零讲起
1. 加密与签名:先分清目标,再记钥匙归谁
它解决什么问题
对称加密有两个最难的问题:钥匙怎么送,以及怎么证明一条消息确实是某人发的、内容没被改过。公钥密码要同时回答这两个问题。用错了钥匙,要么人人都能读,要么谁都能冒充。
直觉
记一条规则就够:谁的钥匙,看谁要被保护。
保密是保护收件人:只有收件人能打开,所以用收件人的公钥锁、收件人的私钥开。签名是保护发件人的身份:只有发件人能盖,所以用发件人的私钥签、发件人的公钥验。
一步一步看
目标:分保密、认证、两样都要三种情形看钥匙怎么用,看出加密用对方的公钥,签名用自己的私钥。
-
只要保密:A 用 B 的公钥 PU_b 加密,B 用自己的私钥 PR_b 解密。攻击者没有 PR_b,读不到。
-
只要认证:A 用自己的私钥 PR_a 签,B 用 A 的公钥 PU_a 验。谁都有 PU_a,谁都能验,所以内容不保密;但能验过,就证明是 A 签的。
-
两样都要:A 先用 PR_a 签(里层),再用 PU_b 加密(外层)。
-
B 收到后从外往里剥:先用 PR_b 解密拆掉外层,再用 PU_a 验签确认是 A 发的,最后拿到消息。
-
再看不同算法能做几件事。三类用途是加密/解密、数字签名、密钥交换,课件的应用表列了四个算法:
图片来源:COMP5521 Lecture 3 Cryptography, p.40
怎么判断
拿到一个场景,按两步判断:
- 目标是保密、认证,还是两样都要?
- 保密用收件人的钥匙对(公钥锁、私钥开);认证用发件人的钥匙对(私钥签、公钥验);两样都要就两对都用,先签后加密。
意思是:钥匙对的主人,就是这一层要保护的那个人。
再判断算法能不能用:查应用表。DH 只能做密钥交换,DSS 只能做签名,RSA 和椭圆曲线三样都行。
常见误解
以为签名就是「用私钥加密」
教材图里画成用私钥「加密」,只是借 RSA 的代数性质帮你理解钥匙归属。真实 RSA 加密和签名使用不同的编码方式,例如 OAEP 与 PSS;签名的目标是可验证,不是把内容藏起来。
以为接收方也先验签、后解密
外层是加密,必须先拆外层才能看到里层的签名。发送方先签后加密,接收方就先解密后验签,顺序相反。
以为对称加密也提供认证
按课件口径,共享密钥两边都有,密文分不清是哪一方生成的,所以对称加密不算提供认证,更谈不上不可否认。课件把教材原图里的 authentication 划掉了。
试一下
B 想让全班都能确认一条公告是自己发的,不在乎别人看到内容。他用哪把钥匙?别人用哪把验?
B 用自己的私钥 PR_b 签,别人用 B 的公钥 PU_b 验。不需要加密。
2. 三易两难与陷门单向函数
它解决什么问题
公钥公开了,私钥怎么还推不出来?一个公钥算法要合格,得把「什么必须容易、什么必须困难」说清楚。陷门单向函数就是满足这些要求的那种数学工具。
从哪来(补充)
「陷门函数」这个名字由 Diffie 和 Hellman 在 1976 年的论文《New Directions in Cryptography》里提出。RSA 是典型的陷门函数,它的陷门是私钥 d,可以从 n 的分解算出来。
出处:Wikipedia: Trapdoor function
直觉
单向函数像把鸡蛋打散:打散一秒钟,还原做不到。
陷门单向函数多了一个后门。不知道后门,它和单向函数一样,倒推不可行;知道后门,倒推也很轻松。公钥密码就是把后门交给私钥主人,把正着算的那一面交给所有人。
一步一步看
目标:把三件易事和两件难事放到陷门单向函数上看,看出正着算谁都容易,倒推却只有握着陷门的人做得到。
-
三件必须容易的事:B 生成一对钥匙;A 知道 B 的公钥和消息,能算出密文;B 用私钥能把密文解回明文。
-
两件必须困难的事:知道公钥,推不出私钥;知道公钥和密文,推不出明文。
-
用一个函数来看:Y = f(X) 正着算容易,谁都能算。
-
没有陷门的人想从 Y 倒推 X:计算上不可行。
-
握着陷门 k 的人倒推 X:容易。RSA 里 f 是 C = Mᵉ mod n,陷门是 d。
怎么判断
陷门单向函数要同时满足三条:
- 知道 k,正算 Y = f_k(X) 容易;
- 知道 k,倒推 X = f_k⁻¹(Y) 容易;
- 不知道 k,倒推不可行。
意思是:同一个函数,对普通人是单向的,对握着陷门的人是双向的。只满足第 1、3 条,那是普通单向函数,比如课件举的哈希函数。
常见误解
以为单向函数就是一一对应
单向只要求倒推困难,不要求逆唯一。课件拿哈希函数举例,但哈希存在碰撞,并不是一一对应。额外要求一一对应的叫单向置换(one-way permutation)。
以为「计算上不可行」就是数学上不可能
它指的是用已知最好的方法、在现实的时间和资源内算不完。数字取小了照样能算,参数大小要随计算能力不断提高。
试一下
DH 里窃听者从 A = gᵃ mod p 求 a,属于三易两难里的哪一类?
属于「困难」那一类:从公开的信息推私密的值。正着算 gᵃ mod p 容易,倒推 a 就是离散对数,不可行。
3. 分解难题:攻破 RSA 的正面路径
它解决什么问题
RSA 的安全到底压在哪一步上?把攻击 RSA 的数学路径拆开,看清楚哪几步容易、哪一步难,就知道 n 要取多大,以及历史上的分解纪录为什么值得关注。
直觉
攻击者手里有 n 和 e。他想要 d。上一讲已经会了:有了 φ(n) 就能用扩展欧几里得求 d;有了 p、q 就能算 φ(n)。
所以只差一步:把 n 拆成 p × q。n 小的时候,试除几下就拆开了;n 有几百位时,目前没有已知的快办法。
一步一步看
目标:拿公开的 n = 187 和 e = 7 一路推出私钥,看出整条攻击路径里只有分解 n 是难的。
-
公开的 n = 187,e = 7。
-
分解 n:187 = 17 × 11。这是唯一难的一步。
-
算 φ(n) = 16 × 10 = 160。
-
算 d = 7⁻¹ mod 160 = 23。私钥到手。
-
课件附的分解纪录表:从 100 位十进制、332 bit 开始,一路推进到 RSA-768;后来又有 RSA-240(795 bit)和 RSA-250(829 bit)。
纪录 位数 时间 RSA-768 768 bit 2009 年 12 月 RSA-240 795 bit 2019 年 12 月 RSA-250 829 bit 2020 年 2 月
怎么判断
判断一组 RSA 参数是否危险,问:n 能不能被分解?
意思是:只要分解得了 n,后面两步是作业题,私钥立刻到手。课件举例用的 n 是 1024 bit,约 309 位十进制;公开分解纪录约 830 bit,余量正在收窄,这是业界转向 2048 bit 的原因。
同时记住方向:分解 n 能攻破 RSA,但反过来不能说「攻破 RSA 只有分解这一条路」。私钥泄漏、实现错误、不加填充,都会出事。
常见误解
以为 RSA-250 就是现在最新的分解纪录
它是课件列出的 2020 年纪录,只能当历史事实记。考试问课件表里的纪录就答 RSA-250、829 bit。
以为求 d 很难,所以 RSA 安全
求 d 不难,有了 φ(n) 用扩展欧几里得几行就出来。难的是没有 p、q 就算不出 φ(n)。安全压在分解上。
试一下
公开 n = 55、e = 3。按三步攻击求 d。
55 = 5 × 11;φ(n) = 4 × 10 = 40;40 = 13 × 3 + 1,1 = 40 − 13 × 3,d = −13 + 40 = 27。验算 3 × 27 = 81 = 2 × 40 + 1。
把它们串起来
公钥体系想解决对称加密的两个难题:送钥匙和签名。DH 解决前一个,RSA 两个都能解决。
用法上,一对钥匙的主人就是这一层要保护的人。保密用收件人那一对,认证用发件人那一对;两样都要就先签后加密,收件人先解密后验签。不同算法能做的事不同,应用表要记住。
安全上,合格的公钥算法要三易两难:生成、加密、解密都容易,从公钥推私钥、从密文推明文都难。陷门单向函数正好提供这种不对称,握着陷门的人才能倒推。
落到 RSA 上,陷门是 d,等价于 p、q。正面攻击要先分解 n,后两步是作业题。所以 n 要大到分解不了,课件附的分解纪录就是在提醒这个余量。
加密和签名解决不同目标,下一讲专门讲数字签名。
课件里的坑
- [两把钥匙任意顺序] p.41 说两把钥匙可以任意顺序使用,这是 RSA 的代数性质,不是所有公钥体系都满足;也不要推广到带填充的真实加密与签名(p.41)
- [划掉的 authentication] p.46 的教材原图写对称加密提供 confidentiality and authentication,课件把 and authentication 划掉了,考试按划掉后的版本答(p.46)
- [哈希不是一一对应] p.42 用哈希举单向函数的例子,但哈希有碰撞,不满足「每个函数值有唯一逆」,答题按课件口径举例即可(p.42)
- [板书笔误] p.41 课堂上讲师在解密那一条旁手写了「C^e mod n = M」→ 解密要用私钥指数,应为 M = C^d mod n;用 e 再算一次只是把密文又加密一遍(p.41)
- [历史参数] p.17 的 1024 bit 与 p.45 的纪录表都是历史数据,不应用作新部署参数;参考 NIST SP 800-131A Rev.2(p.17、p.45)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写应用表的四行三列;再画出先签后加密的两层,写出接收方的处理顺序;最后说出三易两难和攻击 RSA 的三步。
必背
- 加密用收件人公钥、解密用其私钥;签名用发件人私钥、验签用其公钥;签名不等于私钥加密,组合可先签后加密
- 先签后加密:A 先用自己私钥签、再用 B 的公钥加密;B 先用自己私钥解密、再用 A 的公钥验签
- 公钥密码想解决对称加密的两个难题:密钥分发与数字签名;DH 解决密钥分发,RSA 两个都能解决
- 应用表:RSA 与椭圆曲线三项都是 Yes,DH 只有密钥交换,DSS 只有数字签名
- 公钥加密要求三易两难;分解 n → 算 φ → 算 d 是 RSA 的攻击路径,不是唯一风险;课件列出的 RSA-250 为 2020 年 829 bit 历史纪录
- 陷门单向函数:知道陷门 k 时逆算容易,不知道时逆算不可行;RSA 的陷门是 d,等价于知道 p、q
课件例题
本讲课件没有例题落在这一页。p.34–46 都是原理图和表,手算练习见前几页:RSA 在 L03a-3,DH 在 L03b。下面的完整例题和变式题按 p.38、p.40、p.44 的内容编写。
完整例题
题面(改编自课件 p.38、p.40、p.44):Alice 要给 Bob 发一份合同,要求只有 Bob 能读,而且 Bob 能确认是 Alice 发的。(a) 写出双方各用哪把钥匙、按什么顺序;(b) 如果只能从 DH 和 DSS 里各挑一个算法,各负责哪一部分;(c) 攻击者截获了 Bob 的 RSA 公钥 n = 187、e = 7,写出他攻击的三步。
约定:PU、PR 表示公钥、私钥,下标 a、b 表示 Alice、Bob。
解法:
- 目标两样都要:保密和认证。所以两对钥匙都用,先签后加密。
- Alice:先用 PR_a 签合同,再用 PU_b 加密签好的合同。
- Bob:先用 PR_b 解密,再用 PU_a 验签,确认是 Alice 发的、没被改过。
- (b) 查应用表:DH 只能做密钥交换,DSS 只能做签名。DSS 负责签名;DH 负责和 Bob 换出一把共享密钥,正文交给对称算法加密。
- (c) 第一步分解 187 = 17 × 11;第二步 φ(n) = 16 × 10 = 160;第三步 d = 7⁻¹ mod 160 = 23。
- 第一步在 n 有几百位时不可行,这是 RSA 安全的依据。
要点:保密靠收件人的钥匙对,认证靠发件人的钥匙对;接收顺序与发送顺序相反。
答题格式:先写目标(保密/认证/两者),再按时间顺序写双方的每一步,每步写清「谁的哪把钥匙」。
变式题(先自己做)
(1) 改编自课件 p.37:Alice 用自己的私钥 PR_a 处理一条消息后发出,Bob 用 PU_a 处理。这提供保密吗?提供什么? (2) 改编自课件 p.40:判断对错。① DH 可以直接加密一段消息;② DSS 可以做密钥交换;③ RSA 能同时做加密、签名、密钥交换。 (3) 改编自课件 p.44:公开 n = 91、e = 5。按三步攻击求 d。
提示
(1) 谁手里有 PU_a?(2) 对照应用表四行。(3) 91 能被 7 整除。
判分点与答案(非官方评分标准)
判分点:① (1) 要说清「不保密」并给出原因;② (2) 三问各给对错;③ (3) 三步都写出并验算。
(1) 不提供保密:PU_a 人人都有,谁都能处理开。提供认证:只有 Alice 有 PR_a,能用 PU_a 验过就说明是 Alice 发的。
(2) ① 错,DH 只能换密钥;② 错,DSS 只能签名;③ 对。
(3) 91 = 7 × 13;φ(n) = 6 × 12 = 72;72 = 14 × 5 + 2,5 = 2 × 2 + 1,回代 1 = 5 − 2 × (72 − 14 × 5) = 29 × 5 − 2 × 72,d = 29。验算 5 × 29 = 145 = 2 × 72 + 1 ✓。
闪卡自测
1. 公钥密码想解决对称加密的哪两个难题?DH 和 RSA 各解决了哪个?
密钥分发和数字签名。DH 解决密钥分发,RSA 两个都能解决(p.35)。
2. 加密和签名各用谁的哪把钥匙?
加密用收件人公钥、收件人私钥解;签名用发件人私钥、发件人公钥验(p.36–37)。
3. 先签后加密时,接收方按什么顺序处理?
先用自己的私钥解密,再用发送方的公钥验签,和发送方的顺序正好倒过来(p.38)。
4. 应用表的四行各是什么?
RSA 三项 Yes;椭圆曲线三项 Yes;DH 只有密钥交换;DSS 只有数字签名(p.40)。
5. 三易两难各是什么?
易:生成密钥对、用公钥加密、用私钥解密。难:从公钥推私钥、从公钥和密文推明文(p.41)。
6. 陷门单向函数和单向函数差在哪?RSA 的陷门是什么?
陷门单向函数多了一个陷门 k,知道 k 就能轻松倒推。RSA 的陷门是 d,等价于知道 p、q(p.42)。
7. 分解 n 怎样攻破 RSA?课件列到哪一年的纪录?
分解 n 得 p、q → 算 φ(n) → 算 d。课件记录到 2020 年的 RSA-250、829 bit(p.44–45)。
下一讲
这一讲最后区分了加密和签名。下一讲从签名接着讲:签的到底是什么、怎么验,见 L04a。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。