C01b-3 数字签名:私钥签,公钥验
先补一块公钥与私钥,再看 Sign 和 Verify 两个算法、签名为什么必须依赖整条消息、实践中为什么先哈希再签,以及签名为什么不保密。
一句话版
数字签名补上哈希证明不了的那一块:这条消息确实是某个人发的。私钥签,公钥验,签的是整条消息算出的哈希,可消息本身照样谁都能读。
C01a-4 留下一个洞:哈希谁都能算,证明不了来源。这一页用签名把它补上,这一讲也到此收尾。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 私钥 sk | secret key | 只有自己有,用来签名 |
| 公钥 pk | public key | 公开给所有人,用来验签 |
| 签名 σ | signature,σ 读「sigma」 | 用私钥对消息算出的一串比特 |
| Sign | 签名算法 | 输入私钥和消息,输出签名 |
| Verify | 验证算法 | 输入公钥、消息、签名,输出 True 或 False |
| 不可否认性 | non-repudiation | 签了就赖不掉 |
一个类比:私章与印模
送材料的人有一枚只有他有的私章。他在材料上盖章,任何人都能拿一份公开的印模来核对:章对得上,就是他盖的。
私章只在他手里,所以别人伪造不了。印模人人都有,所以谁都能核。
类比在哪里失效:
- 真私章盖在哪张纸上都一样,可以剪下来贴到别的纸上。数字签名由整条消息算出来,消息改一个字,签名就对不上。
- 盖了章的材料照样谁都能读,这一点类比和数字签名一致,签名不把内容藏起来。
从零讲起
1. 先补一块:公钥与私钥(补充)
它解决什么问题
签名要用到一对钥匙。不先分清两把钥匙各干什么,后面「用哪把签、用哪把验」一定会混。
直觉
一对钥匙成对生成。私钥只在主人手里,公钥发给所有人。
记一句话:私钥做「只有我能做」的事,公钥做「谁都能做」的事。
一步一步看
目标:看 Alice 的私钥和公钥各给谁用,分清签名和加密时各用哪把钥匙。
-
Alice 生成一对钥匙:私钥 sk 和公钥 pk。
-
私钥只有 Alice 有。
-
公钥公开,Bob、Carol 和任何人都能拿到一份。
-
签名只有 Alice 能做,所以用私钥。验签谁都能做,所以用公钥。
-
加密是反过来:谁都能给 Bob 发密信,所以用 Bob 的公钥加密;只有 Bob 能读,所以用 Bob 的私钥解密。
怎么判断
遇到「这一步用哪把钥匙」的题,先问:这件事是只有一个人能做,还是谁都能做?
| 操作 | 用哪把钥匙 | 谁能做 |
|---|---|---|
| 签名 | 私钥(签名者自己的) | 只有签名者 |
| 验签 | 公钥(签名者的) | 任何人 |
| 加密 | 公钥(接收方的) | 任何人 |
| 解密 | 私钥(接收方的) | 只有接收方 |
意思是:只有一个人能做的事用私钥,谁都能做的事用公钥。签名和加密的方向正好相反。
常见误解
以为签名就是「用私钥加密」
这样记会和加密的方向搅在一起。课件把签名写成独立的 Sign 和 Verify 两个算法,答题按这个写,别说成加密解密。
以为公钥公开了,私钥就能被推出来
这对钥匙的设计就是:从公钥推不出私钥。公钥可以放心公开。
试一下
Bob 想验证一条声称来自 Alice 的消息,他要用谁的哪把钥匙?
Alice 的公钥。验签用签名者的公钥。
Carol 想给 Bob 发一条只有 Bob 能读的消息,她用谁的哪把钥匙?
Bob 的公钥加密,Bob 用自己的私钥解密。
2. Sign 与 Verify
它解决什么问题
Bob 从互联网上收到一条声称来自 Alice 的消息,凭什么相信它没被改、确实是 Alice 发的?
签名要满足三条:Alice 容易签,别人难以伪造,任何人容易验证。
从哪来(补充)
Whitfield Diffie 和 Martin Hellman 在 1976 年最早提出数字签名的概念,当时只猜想这样的方案存在。不久 Rivest、Shamir、Adleman 发明 RSA,能做出早期的数字签名,论文 1978 年发表。
出处:Wikipedia: Digital signature
直觉
签名方案就是两个算法。签的人把私钥和消息放进 Sign,得到签名。验的人把公钥、消息、签名三样放进 Verify,得到对或错。
一步一步看
目标:走一遍 Alice 签名、任何人验签的流程,看 Sign 和 Verify 各要哪几样输入、输出什么。
-
Alice 手上有私钥 sk 和消息 m。
-
她把两样放进 Sign,得到签名 σ。
-
她把 m 和 σ 一起发出去。
-
任何人收到后,把 Alice 的公钥 pk、消息 m、签名 σ 三样放进 Verify。
-
Verify 输出 True,表示消息应当被接受;输出 False,表示应当被拒绝。
怎么算
两个式子:
σ = Sign(sk; m)
Verify(pk; m, σ) → True / False
意思是:用私钥 sk 给消息 m 算出签名 σ;验证时把公钥、消息、签名三样都交给 Verify,它回答对或错。
Verify 的三个输入缺一不可。只有签名没有消息验不了,只有消息没有签名也验不了。
常见误解
以为验证只要消息和公钥
还要签名 σ。Verify 三个输入:pk、m、σ,这个细节在填空题里出现过。
以为 Verify 输出 True 就证明了发送者的真实身份
它证明的是「这条消息由这把公钥对应的私钥签过」。这把公钥是不是真属于 Alice,签名本身不管,要另外建立可信的关联。
试一下
Eve 截获了 (m, σ),把 m 改成 m',原样附上 σ 转发给 Bob。Bob 验证会得到什么?
False。σ 是对 m 算的,Verify(pk; m’, σ) 对不上,Bob 拒绝。
Eve 想替 Alice 签一条新消息,她缺什么?
缺 Alice 的私钥。没有私钥,她造不出能通过 Alice 公钥验证的签名。
3. 依赖整条消息:先哈希再签
它解决什么问题
手写签名和文件内容是分开的:名字长什么样,和文件写了什么无关。所以才有换页这种伪造手法。
数字签名必须避开这个漏洞。课件的反例是:在邮件末尾粘上你的名字,证明不了是你发的。
直觉
数字签名由整条消息算出来,消息改一个字节,原来的签名立刻失效。
实践中不会直接对长消息做签名运算,那样太慢。先把消息哈希成定长的摘要,再签这个摘要。这也是哈希和签名放在同一讲的原因。
一步一步看
目标:看签名为什么先对整条消息算哈希再签,以及哈希一旦被找到碰撞,签名就能挪给另一条消息用。
-
长消息 m 先过哈希函数 H,得到定长的 H(m)。
-
用私钥对 H(m) 签名,得到 σ。
-
验证方拿到 (m, σ),自己算 H(m),再用公钥验 σ 是不是这个哈希的签名。
-
要是有人找到碰撞 H(m₁) = H(m₂),两条消息的摘要相同。
-
m₁ 的签名就能直接当 m₂ 的签名用,签名体系整个塌掉。
怎么算
实践中的签名:
σ = Sign(sk, H(m))
意思是:签的是消息的哈希,不是消息本身。哈希提供依赖整条消息的定长摘要,签名提供「只有我能生成」。
后果是哈希的抗碰撞性质变成签名安全的前提。这也说明了 C01a-2 里 MD5 和 SHA-1 为什么要淘汰:碰撞被攻破,签在它们上面的签名就不可靠了。
常见误解
以为先哈希再签只是为了省时间,不影响安全
它把签名的安全绑在哈希的抗碰撞上。哈希这一半塌了,签名跟着塌。
以为数字签名和手写签名只是换了载体
课件讲了两条差别。一条是数字签名必须依赖整条消息;另一条是手写签名由签字人亲手完成,数字签名是签字人把私钥交给计算机去算。
试一下
Alice 签了一份合同 m₁。攻击者找到一份内容不同的 m₂,使 H(m₁) = H(m₂)。他能做什么?
把 Alice 对 m₁ 的签名原样贴到 m₂ 上。验证方算出的 H(m₂) 和 H(m₁) 相同,Verify 会通过,看起来 Alice 签了 m₂。
为什么在邮件末尾打上名字不算签名?
名字和邮件内容无关,谁都能复制粘贴到别的邮件上。数字签名由整条消息算出,内容一变签名就对不上。
4. 签名不保密
它解决什么问题
签名保证了完整性和来源,很容易让人以为消息也顺便藏起来了。课件那张 S 和 V 的交互图专门提醒这一点。
直觉
签名者发出去的是 (m, σ):消息本身加上签名。m 是明文,谁截获都能读。
签名只回答「没被改、确实是他签的」,不回答「别人看不到」。
一步一步看
目标:跟着 (m, σ) 从 S 发到 V,看签名能证明消息有效,却挡不住半路的人读到内容。
-
签名者 S 持有消息 m,算出签名 σ。
-
S 把 (m, σ) 发给验证者 V。
-
V 问:(m, σ) 有效吗?用公钥一验就知道。
-
半路截获的人直接就能读到 m。
-
要保密,得另外加密。签名和加密是两件事,分开做。
怎么判断
问「这一讲哪个工具提供机密性」,答案是哪个都没有。
| 保证 | 哈希 | 数字签名 |
|---|---|---|
| 完整性 | 要有可信参照摘要 | 要有可信公钥关联 |
| 来源真实性 | 没有 | 有 |
| 不可否认性 | 没有 | 有 |
| 机密性 | 没有 | 没有 |
意思是:这一讲覆盖了完整性、真实性、不可否认性,机密性要靠加密,不在这一讲范围内。
常见误解
以为验证通过就说明传输中没人看过 m
验证通过只说明 m 没被改、确实是持私钥的人签的。m 一路是明文,看过的人改不了它,但看得到。
以为签名和加密可以随便合成一步
两件事要分开做。真实协议里先签后加密还是先加密后签,顺序还有讲究,这一讲不展开。
试一下
Bob 收到 (m, σ) 并验证通过。他能确定哪几件事?
能确定消息没被改、确实是 Alice 的私钥签的,前提是他手里的公钥确实属于 Alice。不能确定传输中没人读到 m。
区块链上的交易都带签名。别人能看到交易内容吗?
能。签名证明交易是这个地址签的、内容没被改,但交易本身是明文,所有节点都能读。
把它们串起来
一对钥匙,私钥只在签名者手里,公钥人人都有。只有一个人能做的事用私钥,所以私钥签、公钥验,和加密方向相反。
签名方案就是 Sign 和 Verify 两个算法,Verify 要公钥、消息、签名三样。签名必须依赖整条消息,实践中签的是 H(m),于是哈希的抗碰撞成了签名安全的前提。
签名补上了来源真实性和不可否认性,消息却仍是明文。这一讲的工具没有一个提供机密性。
课件里的坑
- [页码缺失] p.40、p.41、p.42 三页没有页脚页码,本页按 PDF 页序数(p.40、p.41、p.42)
- [补充内容] 先哈希再签、抗碰撞是签名的前提,这两条课件 p.41 没写,属于把哈希和签名两半合起来的补充(p.41)
- [钥匙对调] p.43 两个方块用的钥匙不同:Sign 用 Private key,Verify 用 Public key,判断题常把它们对调(p.43)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写签名、验签、加密、解密四行各用哪把钥匙;再写出 Sign 和 Verify 两个式子;然后做一遍完整例题;最后回查两个最容易错的地方:Verify 要三个输入,签名不保密。
必背
- 私钥签、公钥验;和加密的公钥加、私钥解方向相反
- σ = Sign(sk; m),Verify(pk; m, σ) → True/False,三个输入缺一不可
- 数字签名由 Diffie–Hellman 于 1976 年提出,同时保证消息完整性和发送方真实性
- 数字签名必须依赖整条消息;在邮件末尾粘上名字证明不了是你发的
- 实践中先哈希再签:σ = Sign(sk, H(m)),抗碰撞因此成为签名安全的前提
- 签名不提供机密性,(m, σ) 里的 m 是明文
课件例题
本讲课件没有例题针对这一页的内容,签名部分只有定义、流程图和交互图。下面的完整例题按课件 p.38–44 自编。
完整例题
题面(自编,依据课件 p.38–44):Alice 要给 Bob 发一条消息 m:「转给 Bob 5 元」。(1) Alice 怎么签?写出式子,说明用哪把钥匙。(2) Bob 怎么验?需要哪几样输入?(3) Eve 截获后把金额改了,再原样转发,会怎样?(4) 这条消息在传输中保密吗?
约定:Alice 的钥匙对是 (sk, pk),Bob 手里的 pk 确实属于 Alice。
解法:
- (1) 签名只有 Alice 能做,用她的私钥 sk。实践中先哈希再签:σ = Sign(sk, H(m))。
- Alice 把 (m, σ) 一起发给 Bob。
- (2) Bob 用 Alice 的公钥 pk 验:Verify(pk; m, σ) → True / False,三个输入 pk、m、σ 缺一不可。
- 他会先自己算 H(m),再用 pk 验 σ 是不是这个哈希的签名。输出 True 就接受。
- (3) Eve 把 m 改成 m’。Bob 算出的 H(m’) 和 Alice 签的 H(m) 不同,Verify 输出 False,Bob 拒绝。
- Eve 想重签,就得有 Alice 的私钥,她没有。
- (4) 不保密。传的是 (m, σ),m 是明文,Eve 截获时就读到了金额。要保密得另外加密。
要点:钥匙方向看「谁能做」;Verify 三个输入写全;最后一问别被「签名」两个字带着答成保密。
答题格式:四问分开答,前两问各给一个式子并标出钥匙;第 (3) 问写清「为什么失败」和「为什么不能重签」。
变式题(先自己做)
(1) 判断对错:「Alice 用 Bob 的公钥签名,Bob 用自己的私钥验证。」 (2) 某系统用 MD5 做签名前的哈希。为什么这不安全? (3) Alice 和 Bob 改用共享密钥算 MAC 代替签名。之后 Alice 否认发过这条消息,Bob 能向第三方证明吗?
提示
(1) 签名这件事是谁能做?(2) MD5 被攻破的是哪条性质?先哈希再签时这条性质有什么用?(3) 共享密钥在谁手里?
判分点与答案(非官方评分标准)
判分点:① 第 (1) 问判错并给出正确方向;② 第 (2) 问把 MD5 的碰撞和先哈希再签联系起来;③ 第 (3) 问指出 MAC 没有不可否认性。
(1) 错。签名用签名者自己的私钥,即 Alice 的私钥;验证用 Alice 的公钥。题目说的是加密的方向。
(2) MD5 的碰撞早已被找到。签名签的是 H(m),攻击者造出 H(m₁) = H(m₂) 的两份消息,让 Alice 签 m₁,就能把这个签名当 m₂ 的签名用。
(3) 不能。密钥两人都有,Bob 自己也能算出同样的 MAC,第三方分不清是谁算的。要让 Alice 赖不掉,必须用她的私钥签名。
闪卡自测
1. 签名和加密,公私钥的方向有什么不同?
签名是私钥签、公钥验;加密是公钥加、私钥解,方向相反(p.38、p.40)。
2. 数字签名是谁、哪一年提出的?保证哪两件事?
Diffie–Hellman,1976 年。保证消息没被改(完整性)和发送方确实是他(真实性)(p.40)。
3. Verify 算法需要哪三个输入?只给消息和公钥能验吗?
公钥 pk、消息 m、签名 σ,三个缺一不可。不给签名就验不了(p.42、p.43)。
4. 为什么在邮件末尾打上自己的名字不算数字签名?
名字和邮件内容无关,谁都能复制粘贴到别的邮件上。数字签名必须依赖整条消息(p.41)。
5. 为什么实践中签的是 H(m)?这带来什么前提?
非对称运算慢、消息可能很长,所以先哈希成定长摘要再签。代价是抗碰撞成为签名安全的前提:能找到 H(m₁) = H(m₂),m₁ 的签名就能当 m₂ 的签名用(p.41 补充)。
6. Bob 收到 (m, σ) 并验证通过,传输中有没有人读到 m?
不能确定。m 是明文,签名不提供机密性(p.44)。
下一讲
L02a-1 Ethereum 账户与世界状态:把这一讲的哈希和签名装进一个真实平台。带着一个问题去听:地址怎么从公钥哈希出来,每笔交易的签名落在哪个字段上。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。