← COMP5565 全部讲次
C01b-3 · 第 2 周

C01b-3 数字签名:私钥签,公钥验

先补一块公钥与私钥,再看 Sign 和 Verify 两个算法、签名为什么必须依赖整条消息、实践中为什么先哈希再签,以及签名为什么不保密。

一句话版

数字签名补上哈希证明不了的那一块:这条消息确实是某个人发的。私钥签,公钥验,签的是整条消息算出的哈希,可消息本身照样谁都能读。

C01a-4 留下一个洞:哈希谁都能算,证明不了来源。这一页用签名把它补上,这一讲也到此收尾。

先认识这几个词

词 全称 / 读法 一句人话
私钥 sk secret key 只有自己有,用来签名
公钥 pk public key 公开给所有人,用来验签
签名 σ signature,σ 读「sigma」 用私钥对消息算出的一串比特
Sign 签名算法 输入私钥和消息,输出签名
Verify 验证算法 输入公钥、消息、签名,输出 True 或 False
不可否认性 non-repudiation 签了就赖不掉

一个类比:私章与印模

送材料的人有一枚只有他有的私章。他在材料上盖章,任何人都能拿一份公开的印模来核对:章对得上,就是他盖的。

私章只在他手里,所以别人伪造不了。印模人人都有,所以谁都能核。

类比在哪里失效:

  1. 真私章盖在哪张纸上都一样,可以剪下来贴到别的纸上。数字签名由整条消息算出来,消息改一个字,签名就对不上。
  2. 盖了章的材料照样谁都能读,这一点类比和数字签名一致,签名不把内容藏起来。

从零讲起

1. 先补一块:公钥与私钥(补充)

它解决什么问题

签名要用到一对钥匙。不先分清两把钥匙各干什么,后面「用哪把签、用哪把验」一定会混。

直觉

一对钥匙成对生成。私钥只在主人手里,公钥发给所有人。

记一句话:私钥做「只有我能做」的事,公钥做「谁都能做」的事。

一步一步看

目标:看 Alice 的私钥和公钥各给谁用,分清签名和加密时各用哪把钥匙。

  1. Alice 生成一对钥匙:私钥 sk 和公钥 pk。

  2. 私钥只有 Alice 有。

  3. 公钥公开,Bob、Carol 和任何人都能拿到一份。

    一对钥匙:私钥 sk 只在 Alice 手里,公钥 pk 公开,Bob、Carol 和任何人都拿到一份;下方表格列出签名用签名者自己的私钥只有签名者能做,验签用签名者的公钥任何人能做,加密用接收方的公钥任何人能做,解密用接收方的私钥只有接收方能做

  4. 签名只有 Alice 能做,所以用私钥。验签谁都能做,所以用公钥。

  5. 加密是反过来:谁都能给 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 各要哪几样输入、输出什么。

  1. Alice 手上有私钥 sk 和消息 m。

  2. 她把两样放进 Sign,得到签名 σ。

  3. 她把 m 和 σ 一起发出去。

  4. 任何人收到后,把 Alice 的公钥 pk、消息 m、签名 σ 三样放进 Verify。

    签名生成和签名验证:左边 Alice 把私钥 sk 和消息 m 放进 Sign,得到 σ;右边任何人把消息 m、签名 σ、公钥 pk 放进 Verify,输出 True 或 False;两把钥匙用青绿标出,判断题常把它们对调

  5. 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. 依赖整条消息:先哈希再签

它解决什么问题

手写签名和文件内容是分开的:名字长什么样,和文件写了什么无关。所以才有换页这种伪造手法。

数字签名必须避开这个漏洞。课件的反例是:在邮件末尾粘上你的名字,证明不了是你发的。

直觉

数字签名由整条消息算出来,消息改一个字节,原来的签名立刻失效。

实践中不会直接对长消息做签名运算,那样太慢。先把消息哈希成定长的摘要,再签这个摘要。这也是哈希和签名放在同一讲的原因。

一步一步看

目标:看签名为什么先对整条消息算哈希再签,以及哈希一旦被找到碰撞,签名就能挪给另一条消息用。

  1. 长消息 m 先过哈希函数 H,得到定长的 H(m)。

  2. 用私钥对 H(m) 签名,得到 σ。

  3. 验证方拿到 (m, σ),自己算 H(m),再用公钥验 σ 是不是这个哈希的签名。

    实践中先哈希再签:长消息 m 经过 H 得到定长的 H(m),再用 Sign(sk, ·) 得到 σ;下方说明如果有人找到碰撞 H(m₁) = H(m₂),m₁ 和 m₂ 得到同一个 H 值,m₁ 的 σ 也能当 m₂ 的签名;所以抗碰撞是签名安全的前提

  4. 要是有人找到碰撞 H(m₁) = H(m₂),两条消息的摘要相同。

  5. 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,看签名能证明消息有效,却挡不住半路的人读到内容。

  1. 签名者 S 持有消息 m,算出签名 σ。

  2. S 把 (m, σ) 发给验证者 V。

  3. V 问:(m, σ) 有效吗?用公钥一验就知道。

  4. 半路截获的人直接就能读到 m。

    传的是 (m, σ):Signer S 持有消息 m,把 (m, σ) 发给 Verifier V,V 问 (m, σ) 是否有效;中途截获的人直接读到 m,用青绿标出;签名保证没被改、确实是他签的,不保证别人看不到,要保密得另外加密

  5. 要保密,得另外加密。签名和加密是两件事,分开做。

怎么判断

问「这一讲哪个工具提供机密性」,答案是哪个都没有。

保证 哈希 数字签名
完整性 要有可信参照摘要 要有可信公钥关联
来源真实性 没有 有
不可否认性 没有 有
机密性 没有 没有

意思是:这一讲覆盖了完整性、真实性、不可否认性,机密性要靠加密,不在这一讲范围内。

常见误解

以为验证通过就说明传输中没人看过 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 要三个输入,签名不保密。

必背

  1. 私钥签、公钥验;和加密的公钥加、私钥解方向相反
  2. σ = Sign(sk; m),Verify(pk; m, σ) → True/False,三个输入缺一不可
  3. 数字签名由 Diffie–Hellman 于 1976 年提出,同时保证消息完整性和发送方真实性
  4. 数字签名必须依赖整条消息;在邮件末尾粘上名字证明不了是你发的
  5. 实践中先哈希再签:σ = Sign(sk, H(m)),抗碰撞因此成为签名安全的前提
  6. 签名不提供机密性,(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. (1) 签名只有 Alice 能做,用她的私钥 sk。实践中先哈希再签:σ = Sign(sk, H(m))。
  2. Alice 把 (m, σ) 一起发给 Bob。
  3. (2) Bob 用 Alice 的公钥 pk 验:Verify(pk; m, σ) → True / False,三个输入 pk、m、σ 缺一不可。
  4. 他会先自己算 H(m),再用 pk 验 σ 是不是这个哈希的签名。输出 True 就接受。
  5. (3) Eve 把 m 改成 m’。Bob 算出的 H(m’) 和 Alice 签的 H(m) 不同,Verify 输出 False,Bob 拒绝。
  6. Eve 想重签,就得有 Alice 的私钥,她没有。
  7. (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 账户与世界状态:把这一讲的哈希和签名装进一个真实平台。带着一个问题去听:地址怎么从公钥哈希出来,每笔交易的签名落在哪个字段上。

下一讲 →
L02a-1 L02a-1 以太坊账户与地址:一把私钥怎么变成一串 0x

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。