← COMP5521 全部讲次
L04b · 第 5 周

L04b 盲签名:隔着信封盖章

Chaum 盲签名从零讲:先补模逆和 k 的 ed 次方为什么等于 k,再一帧一帧走完盲化、签名、去盲三步,最后看签名者为什么事后认不出自己签过哪一张。

一句话版

盲签名让签名者签了字,却看不到签的是什么。它不是新算法,就是在上一页的 RSA 签名前后各乘一个随机数:签之前乘上去,签完再除掉,留下的正好是普通 RSA 签名。

这一页要用到 RSA 签名的公式,见上一页 L04a。

先认识这几个词

词 全称 / 读法 一句人话
盲签名 blind signature 签名者签了字,却看不到签的是什么
盲化因子 k blinding factor 请求者自己挑的随机数,用来把消息藏起来
盲化 / 去盲 blinding / unblinding 签之前把消息藏起来 / 签完把遮挡去掉
k⁻¹ 读「k 的逆」 和 k 相乘后取模等于 1 的数
gcd greatest common divisor,最大公约数 gcd = 1 就是两个数没有公共因子,叫互素
电子现金 e-cash 银行盖章发行、花的时候银行认不出是谁的电子钞票

一个类比:隔着复写纸信封盖章

Alice 把一张文件塞进信封,信封夹层垫了一张复写纸。她把信封交给 Bob。

Bob 在信封外面盖章,章透过复写纸印到里面的文件上。Bob 盖了章,却没看见文件写了什么。

Alice 拿回信封,拆开,取出文件。文件上有 Bob 的真章,谁拿来对都对得上。

数学上,信封就是请求者挑的随机数 k。套信封是乘上 kᵉ,拆信封是乘上 k⁻¹。

类比在哪里失效:

  • 真信封拆开后会留下来,Bob 有可能凭信封的样子认出是哪一封。数学信封拆完就没了,Bob 手上那个数和最后的签名之间没有任何痕迹相连。
  • 复写纸印出的章会有点模糊。数学去盲后的签名和 Bob 直接签出的那一个分毫不差。

从零讲起

1. 先补一块:模逆与 k 的 ed 次方(补充)

它解决什么问题

盲签名最后要把 k「除掉」。模运算里没有除法,除以 k 要换成乘以 k⁻¹ mod n。这一节补两件事:k⁻¹ 怎么求;为什么签名者的 d 次方能把 kᵉ 变回 k。

直觉

k⁻¹ 是「和 k 相乘后模 n 等于 1」的那个数。比如在模 119 下,29 × 78 = 2262,2262 除以 119 余 1,所以 78 就是 29 的逆。

只有 k 和 n 没有公共因子时,这个数才存在。所以盲化因子必须和 n 互素。

一步一步看

目标:用扩展欧几里得求 29⁻¹ mod 119,看出余数走到 1 就说明逆存在,倒着回代就能把逆读出来。

用扩展欧几里得求 29⁻¹ mod 119:

  1. 辗转相除,记下每一步的商和余数:

    步 式子 余数
    ① 119 = 4 × 29 + 3 3
    ② 29 = 9 × 3 + 2 2
    ③ 3 = 1 × 2 + 1 1
  2. 余数走到 1,说明 gcd(29, 119) = 1,逆存在。

  3. 从第 ③ 步倒着代:1 = 3 − 2。

  4. 把第 ② 步的 2 = 29 − 9 × 3 代进去:1 = 3 − (29 − 9 × 3) = 10 × 3 − 29。

  5. 把第 ① 步的 3 = 119 − 4 × 29 代进去:1 = 10 × 119 − 41 × 29。

  6. 两边模 119,得 −41 × 29 ≡ 1,所以 29⁻¹ ≡ −41 ≡ 78。验算 29 × 78 = 2262 = 19 × 119 + 1 ✓。

怎么算

RSA 的 e 和 d 满足 ed ≡ 1 (mod φ(n)),写成 ed = 1 + t·φ(n)。

k^(ed) = k^(1 + t·φ(n)) ≡ k (mod n)

意思是:任何数先升 e 次方、再升 d 次方,模 n 之后回到它自己。这正是 RSA 能解密的原因,上一讲证过。

盲签名要用的就是这一行:请求者先把 k 升成 kᵉ,签名者签名时顺手把它升了 d 次方,kᵉ 就回到 k。

常见误解

以为任何 k 都能当盲化因子

k 必须和 n 互素。比如 n = 119 = 7 × 17,选 k = 7 时 gcd(7, 119) = 7,7⁻¹ mod 119 不存在,最后一步去盲做不了。

把 k⁻¹ 求成 mod φ(n) 下的逆

去盲在 mod n 下做,所以 k⁻¹ 是 mod n 的逆。求 d 才用 mod φ(n)。两个模数别混:d 是 e 在 mod φ(n) 下的逆,k⁻¹ 是 k 在 mod n 下的逆。

试一下

求 10⁻¹ mod 119。

119 = 11 × 10 + 9,10 = 1 × 9 + 1。倒代 1 = 10 − 9 = 10 − (119 − 11 × 10) = 12 × 10 − 119,所以 10⁻¹ ≡ 12。验算 10 × 12 = 120 = 119 + 1 ✓。

2. Chaum 盲签名三步

它解决什么问题

银行要发行电子钞票。每张钞票得有银行的签名,否则谁都能自己印。可要是银行签名时看到了钞票编号,你花这张钞票时银行就知道是你花的。

盲签名让银行签得出、看不见。课件的说法是:this is needed in e-commerce,意思是电子商务需要它。

从哪来(补充)

盲签名由 David Chaum 提出,论文是 1983 年的《Blind Signatures for Untraceable Payments》。它常用在注重隐私的协议里,比如电子投票和电子现金。

复写纸信封这个类比也来自同一条目:选民把匿名选票放进内衬复写纸的信封,官员核对信封外的身份后在信封上签字,签名透过复写纸印到选票上。出处:Wikipedia: Blind signature

直觉

请求者 Alice 想让 Bob 签消息 m。她先挑一个随机数 k,把 m 乘上 kᵉ 发给 Bob。在 Bob 看来,这是一个和 m 无关的随机数。

Bob 照常签名,把结果发回。签名的 d 次方把 kᵉ 变回了 k,所以 Alice 收到的是「m 的签名乘以 k」。她再乘上 k⁻¹,就只剩 m 的签名。

一步一步看

目标:用课件的小数字走完盲化、签名、去盲三步,看出 Bob 只签过 9,Alice 却拿到对 37 有效的签名。

用课件 Exercise-2 的数:Bob 的公钥 e = 5、n = 119,私钥 d = 77。Alice 要签 m = 37,挑 k = 29。

  1. 盲化:Alice 算 m′ = 37 × 29⁵ mod 119。29⁵ mod 119 = 71,37 × 71 = 2627 ≡ 9。她只发 9。

    盲签名第 1 帧:五个格子依次是 Alice 的消息 m = 37、套信封盲化 m′ = 9、Bob 盖章、拆信封去盲、谁都能验;套信封格子被青绿框标出;下方说明 Alice 选 k = 29 算出 9 只把 9 发给 Bob

  2. 签名:Bob 用私钥签 9,s′ = 9⁷⁷ mod 119 = 25,发回。

    盲签名第 2 帧:Bob 盖章格子被青绿框标出,写着 s′ = 25;下方说明 Bob 用私钥 77 签 9,他只看见 9,不知道背后是 37

  3. 去盲:Alice 乘上 29⁻¹ mod 119 = 78,s = 78 × 25 mod 119 = 46。

    盲签名第 3 帧:拆信封去盲格子被青绿框标出,写着 s = 46;下方说明 Alice 乘上 k 的逆 78 得到 46,正好等于 Bob 直接签 37 的结果

  4. 验证:任何人用 Bob 的公钥算 46⁵ mod 119 = 37,等于 m,有效。

    盲签名第 4 帧:谁都能验格子被青绿框标出,写着 46⁵ → 37;下方说明验签和普通 RSA 签名一模一样,看不出这张签名是盲签出来的

怎么算

三步公式(都 mod n):

  • 盲化:m′ = m · kᵉ mod n
  • 签名:s′ = (m′)ᵈ mod n
  • 去盲:s = k⁻¹ · s′ mod n

为什么 s 就是 m 的签名,逐行推:

s′ = (m · kᵉ)ᵈ = mᵈ · k^(ed) (mod n)

k^(ed) ≡ k (mod n),所以 s′ ≡ mᵈ · k

s = k⁻¹ · s′ ≡ k⁻¹ · mᵈ · k = mᵈ (mod n)

意思是:签名者的 d 次方同时作用在 m 和 kᵉ 上。作用在 m 上的部分就是正常签名,作用在 kᵉ 上的部分变回 k,请求者乘 k⁻¹ 把它消掉。

课件推导框里写的「/ k」就是乘 k⁻¹。

常见误解

以为盲签名是一种新的签名算法

它是套在 RSA 签名外面的两方协议。签名者用的还是普通的 RSA 私钥,得到的 s 也用普通方式验。拿到 s 的人看不出它经历过盲化。

把示意图和课件公式的记号对不上

课件引用的 Wikipedia 示意图把模数写成 p、盲化因子叫 r。课件自己的公式用 n 和 k。两页讲的是同一个协议,答题用 n 和 k。

试一下

同一组公钥 e = 5、n = 119,Alice 想用 k = 7 当盲化因子,可以吗?

不行。119 = 7 × 17,gcd(7, 119) = 7,7 在 mod 119 下没有逆,第三步去盲做不了。

只看第 2 步,Bob 收到的 9 能告诉他 m 是多少吗?

不能。9 = 37 × 29⁵ mod 119,可 Bob 不知道 29。对任意一个候选 m,都能找到某个 k 让 m · kᵉ ≡ 9,所以 9 和哪条消息都对得上。

3. 签完认不出:盲签名换来的匿名性

它解决什么问题

只做到「签名时看不到」还不够。电子现金要的是:钞票花出去时,银行验得出章是自己盖的,却查不出这张钞票当初是给谁盖的。这一节说明盲签名为什么做得到。

直觉

Bob 的签名记录里只有 m′ 和 s′。市面上流通的是 m 和 s。两组数之间唯一的桥是 k,而 k 只在 Alice 手里,用完就可以扔掉。

所以 Bob 拿到 (m, s),能验证章是真的,却连不回自己签过的任何一条记录。

一步一步看

目标:站在 Bob 这边对照签过的记录和拿来兑现的签名,看出不知道 k 就连不上是哪一次签的。

  1. Bob 签名时记下:签过 m′ = 9,回了 s′ = 25。

  2. 过了一阵,有人拿着 (m, s) = (37, 46) 来找 Bob 兑现。

  3. Bob 用自己的公钥验:46⁵ mod 119 = 37,章是真的。

  4. Bob 想查这是哪次签的:9 和 37 之间差一个 29⁵,46 和 25 之间差一个 29,他不知道 29,连不上。

    不可关联性示意:左框 Bob 的签名记录写着签过 m′ = 9、回了 s′ = 25,在他看来是随机数;右框后来有人拿来报销,消息 37、签名 46,46 的 5 次方 mod 119 等于 37 章是真的;中间青绿虚线标着 9 和 37 连不上,因为连接它们的 k = 29 只在 Alice 手里

  5. Bob 签过的记录越多,他就越不可能知道眼前这张是给谁签的。

怎么判断

判断一个签名方案有没有「签完认不出」的性质,问一句:签名者看到的东西,和最后流通的消息、签名之间,有没有他能算出来的联系?

Chaum 盲签名里,签名者看到的是 m′ 和 s′,流通的是 m 和 s。

  • m′ = m · kᵉ:k 均匀随机,kᵉ mod n 也均匀随机,m′ 对签名者来说就是个随机数。
  • s = k⁻¹ · s′:没有 k 就算不出这层关系。

两条联系都要用到 k,签名者手里没有 k,所以认不出。

常见误解

以为盲签名能防止签名者乱签

它防的方向相反:保护的是请求者的隐私。签名者既然看不到内容,就可能被骗着签下不该签的东西。实际的电子现金系统要另加机制约束这一点,课件没有展开。

以为签名者事后完全不知道自己签过

签名者知道自己签过、签了几次,也能验出章是真的。他不知道的是:眼前这张签名对应当初哪一次。

试一下

Bob 一天签了两次,记录是 (9, 25) 和 (4, 72)。后来有人拿来 (37, 46) 和 (12, 31)。Bob 能把它们配对吗?

不能。两张签名都能用公钥验过(46⁵ ≡ 37,31⁵ ≡ 12,都 mod 119),可连接记录和签名的盲化因子只在请求者手里。在 Bob 看来,哪张对哪条记录都说得通。

把它们串起来

盲签名是在 RSA 签名外面包了一层,整个协议靠一行等式撑着:k^(ed) ≡ k。

请求者先用公钥把 k 升成 kᵉ,乘在消息上,这是套信封。签名者用私钥签,d 次方同时作用在消息和 kᵉ 上,kᵉ 变回 k。请求者乘 k⁻¹ 去掉 k,这是拆信封。剩下的就是普通 RSA 签名,谁都能用公钥验。

Chaum 盲签名三步总览:左列 Alice 握有公钥 (5, 119)、消息 37、盲化因子 29,第一步盲化 37 × 29⁵ = 37 × 71 mod 119 得 9 发给右列 Bob;Bob 用私钥 77 签 9 的 77 次方 mod 119 得 25 发回;Alice 去盲 78 × 25 mod 119 得 46,46 正好等于 37 的 77 次方 mod 119,谁都能验 46⁵ mod 119 = 37;Bob 只记得签过 9,对不上 37

用到的零件都是前面的:扩展欧几里得求 k⁻¹ mod n,平方-乘算 (m′)ᵈ。k 必须和 n 互素,否则逆不存在。

签名者看到的只有 m′ 和 s′,它们和 m、s 之间隔着 k。这让盲签名成了电子现金的基础:银行签得出、验得出,却查不出钞票是谁的。

下一页换一个难题:离散对数。Elgamal 签名压在它上面,签名从一个数变成一对数。

课件里的坑

  • [读图] p.33 的 Wikipedia 示意图用 p 当模数、r 当盲化因子,p.35 课件自己的记号是 n 和 k;两页是同一个协议,答题按 p.35(p.33、35)
  • [读图] p.35 推导方框最后一行写着 D’s signature on m,D 指前文的签名者 Bob,是引用外部材料残留的记号(p.35)
  • [记号] p.36 和 p.43 两道题用 r 记盲化因子,和 p.35 的 k 是同一个东西(p.36、p.43)
  • [写法] p.35 方框里的「/ k」是乘 k⁻¹ mod n,不是整数除法(p.35)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写盲化、签名、去盲三步公式;再把 p.36 那道题不看解答重算一遍,每一步先写「谁算、用哪把钥匙、mod 什么」;最后用一行等式说清 k 为什么能剥掉。三步做完再往下看答案。

必背

  1. 盲签名的目的:签名者签 m 却不知道 m 是什么;课件说电子商务需要它,典型场景是电子现金。
  2. Chaum 盲签名 m′ = m·kᵉ → s′ = (m′)ᵈ → s = k⁻¹s′ = mᵈ,签名者看不到 m 但结果与普通 RSA 签名相同。
  3. 盲化因子 k 要满足 0 < k < n 且 gcd(k, n) = 1,因为去盲要用 k⁻¹ mod n。
  4. 推导核心:(m·kᵉ)ᵈ = mᵈ·k^(ed) ≡ mᵈ·k,乘 k⁻¹ 得 mᵈ;kᵉ 被签名者的 d 次方剥回 k。
  5. Exercise-2:e = 5、n = 119、m = 37、k = 29 → d = 77、m′ = 9、s′ = 25、s = 46,验签 46⁵ mod 119 = 37。
  6. Exercise-7:e = 5、n = 391、m = 89、k = 48 → d = 141、m′ = 65、s′ = 56、s = 327。

课件例题

例 1(课件 p.36):Exercise-2,Chaum 盲签名走一遍

题面:签名者公钥 e = 5、n = 119。请求者要签 m = 37,盲化因子 r = 29。求签名者私钥、盲化值 m′、盲签名 s′ 和去盲后的签名 s。

提示

先分解 119 求 φ 和 d。29⁵ 用平方算:29² 先模 119。签名那步 77 拆成 64 + 8 + 4 + 1。去盲要 29⁻¹ mod 119。

解答

私钥:119 = 7 × 17,φ = 6 × 16 = 96。96 = 19 × 5 + 1,所以 d ≡ −19 ≡ 77。验算 5 × 77 = 385 = 4 × 96 + 1。

盲化:29² = 841 mod 119 = 8,29⁴ ≡ 64,29⁵ = 64 × 29 = 1856 mod 119 = 71。m′ = 37 × 71 = 2627 mod 119 = 9。

签名:s′ = 9⁷⁷ mod 119。平方链 9² = 81,9⁴ ≡ 16,9⁸ ≡ 18,9¹⁶ ≡ 86,9³² ≡ 18,9⁶⁴ ≡ 86。77 = 64 + 8 + 4 + 1,86 × 18 × 16 × 9 逐步取模得 25。

去盲:29⁻¹ mod 119 = 78,因为 29 × 78 = 2262 = 19 × 119 + 1。s = 78 × 25 = 1950 mod 119 = 46。

核对:直接算 37⁷⁷ mod 119 也是 46,验签 46⁵ mod 119 = 37。题里的 r 就是协议里的 k。

课堂批注(课件 p.36):Exercise-2 换三处算法

课堂上讲师补充了另一套手算路线:d 靠试 k,9⁷⁷ 先凑出 9¹⁰,29⁻¹ 用欧拉定理直接写成一个幂。

提示

d = (k × 96 + 1) ÷ 5,从 k = 1 试起。77 = 10 × 7 + 7。r 和 n 互素时 r^φ(n) ≡ 1,所以 r 的 φ(n) − 1 次方就是它的逆。

解答

求 d:k = 1、2、3 时 97、193、289 都不能被 5 整除;k = 4 时 385 = 5 × 77,d = 77。

签名:先算 9¹⁰ mod 119 = 30。于是 9⁷⁷ = (9¹⁰)⁷ × 9⁷ ≡ 30⁷ × 9⁷。30⁷ mod 119 = 72,9⁷ mod 119 = 2,72 × 2 = 144 ≡ 25,s′ = 25。

去盲:gcd(29, 119) = 1,由欧拉定理 29⁹⁶ ≡ 1 (mod 119),所以 29⁻¹ ≡ 29⁹⁵ (mod 119) = 78。s = 25 × 78 mod 119 = 46,和上面扩展欧几里得的结果一样。

29⁹⁵ 手算要做一串平方-乘,步数比扩展欧几里得的几行回代多,它的好处是不用记回代。

例 2(课件 p.43):Exercise-7,另一组 Chaum 盲签名

见下方完整例题。

完整例题

课件 p.43 这道 take-home 把求 d、求逆和三步协议串在一起,适合练手算,不代表官方承诺考试题型。

e = 5,n = 17 × 23 = 391,请求者要签 m = 89,盲化因子 r = 48(p.43 Exercise-7)

  1. 求私钥:φ = 16 × 22 = 352。352 = 70 × 5 + 2,5 = 2 × 2 + 1,回代 1 = 5 − 2 × 2 = 5 − 2 × (352 − 70 × 5) = 141 × 5 − 2 × 352,d = 141。验算 5 × 141 = 705 = 2 × 352 + 1 ✓。
  2. 查盲化因子:391 = 8 × 48 + 7,48 = 6 × 7 + 6,7 = 1 × 6 + 1,gcd(48, 391) = 1 ✓。
  3. 盲化:48² = 2304 ≡ 349。把 349 写成 −42 再平方,48⁴ ≡ 1764 ≡ 200。48⁵ = 200 × 48 = 9600 ≡ 216。m′ = 89 × 216 = 19224 ≡ 65。
  4. 签名:s′ = 65¹⁴¹ mod 391。141 = 128 + 8 + 4 + 1,平方链 65² ≡ 315,65⁴ ≡ 302,65⁸ ≡ 101,65¹⁶ ≡ 35,65³² ≡ 52,65⁶⁴ ≡ 358,65¹²⁸ ≡ 307。307 × 101 ≡ 118,× 302 ≡ 55,× 65 ≡ 56。
  5. 去盲:用第 2 步倒代,1 = 7 − 6 = 7 × 7 − 48 = 7 × 391 − 57 × 48,所以 48⁻¹ ≡ −57 ≡ 334。验算 48 × 334 = 16032 = 41 × 391 + 1 ✓。s = 334 × 56 = 18704 ≡ 327。
  6. 核对:89¹⁴¹ mod 391 = 327,验签 327⁵ mod 391 = 89 ✓。

变式题(先自己做)

改编自课件 p.36:签名者公钥 e = 5、n = 119(私钥沿用 p.36 求出的 77)。请求者要签 m = 12,盲化因子 r = 10。求 m′、s′、s,并验证 s 就是 m 的普通 RSA 签名。

提示

10⁴ mod 119 会落到一个很小的数,10⁵ 随之好算。算 s′ 时留意平方链里会出现 18 × 86 ≡ 1。10⁻¹ mod 119 看一眼 10 × 12 就有了。

判分点与答案(非官方评分标准)

判分点:每一步先写「谁算、用哪把钥匙、mod 什么」;r⁻¹ 要验算乘积 ≡ 1;最后用公钥验 s。

盲化:10² = 100,10⁴ = 10000 mod 119 = 4,10⁵ = 40;m′ = 12 × 40 = 480 mod 119 = 4。签名 s′ = 4⁷⁷ mod 119:4² = 16,4⁴ ≡ 18,4⁸ ≡ 86,4¹⁶ ≡ 18,4³² ≡ 86,4⁶⁴ ≡ 18;77 = 64 + 8 + 4 + 1 → 18 × 86 ≡ 1,再 × 18 × 4 = 72。去盲:10⁻¹ ≡ 12(10 × 12 = 120 = 119 + 1),s = 12 × 72 = 864 mod 119 = 31。验签:31² = 961 ≡ 9,31⁴ ≡ 81,31⁵ = 81 × 31 = 2511 ≡ 12 = m ✓。

闪卡自测

1. 盲签名要达到什么效果?课件说它在哪个领域需要?

签名者签了 m 却不知道 m 是什么。课件说 this is needed in e-commerce,典型场景是电子现金(p.31)。

2. 盲签名三步各叫什么?最后的 s 怎么验?

盲化、签名、去盲。s 用签名者的公钥按普通 RSA 方式验,看不出经历过盲化(p.32)。

3. 盲化因子 k 要满足什么条件?为什么?

0 < k < n 且 gcd(k, n) = 1,因为去盲要用 k⁻¹ mod n,不互素就没有逆(p.34)。

4. 为什么 k 能剥掉?写出那一行。

(m·kᵉ)ᵈ = mᵈ·k^(ed) ≡ mᵈ·k,因为 k^(ed) ≡ k (mod n);再乘 k⁻¹ 得 mᵈ(p.35)。

5. p.36 的四个答案是什么?

d = 77,m′ = 9,s′ = 25,s = 46;验签 46⁵ mod 119 = 37(p.36)。

6. p.33 示意图和 p.35 的记号有哪两处不同?

示意图用 p 当模数、r 当盲化因子;p.35 用 n 和 k(p.33、35)。

下一讲

下一页换到离散对数难题上:先认识生成元,查一张模 7 的乘方表,再看 Elgamal 怎么用它签出一对 (r, s),见 L04c。

下一讲 →
L04c L04c 离散对数与 Elgamal:一个私钥、一个临时 k、一对 (r, s)

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