L08b-2 ECDSA:比特币怎样用椭圆曲线签名
ECDSA 签名五步、验签五步,用代数一行说清为什么验得过;再用课件那道 mod 17 练习完整走一遍,最后看同一个随机数签两次怎样泄露私钥。
一句话版
ECDSA 是第 4 讲 DSA 的椭圆曲线版本。签名时临时取一个随机数 j,算出点 jP,取它的横坐标得 r,再用私钥算出 s;验签的人只用公钥,把 r、s 拼成另一个点,看它的横坐标是不是 r。
比特币每一笔交易都靠这个签名证明「花钱的人确实握着私钥」。曲线和单向性见 L08b,点加法公式见 L08a。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| ECDSA | Elliptic Curve Digital Signature Algorithm | 椭圆曲线上的数字签名算法 |
| e | message hash | 消息的哈希值,比特币里做两次 SHA-256 |
| j | ephemeral nonce,随机数 | 每次签名临时取的数,用完就扔 |
| (r, s) | signature | 签名本身,两个 256 位的数 |
| w | 读「w」 | s 在模 n 下的逆元,验签时第一步算它 |
| u、v | 两个系数 | 验签时分别乘基点和公钥的倍数 |
一个类比:一次性印章
想象每次签字前,你都临时刻一枚只用一次的小印章 j,先在纸上盖出一个图案,图案的位置记作 r。然后你用自己的私人密码把「这份文件、这个图案、你的密码」揉成一个数 s 写在旁边。
检查的人看不到你的密码,也看不到那枚小印章。但他手里有你公开的「密码指纹」,可以用 r、s 和文件把那个图案重新拼出来。拼出来的位置和 r 对上,就说明签字的人确实知道密码。
小印章必须每次重刻。同一枚印章盖两份不同的文件,两个图案位置一样,旁人对比两份签字就能把你的密码解出来。
类比在哪里失效:
- 印章图案是看得见的形状,r 只是点 jP 的横坐标取模 n 后的一个整数。
- 「揉成一个数」在 ECDSA 里是一条精确的模 n 公式,每一步都能逆推,所以才会有随机数重用的攻击。
- 现实印章可以伪造;ECDSA 伪造签名要先解 ECDLP。
从零讲起
1. 签名五步
它解决什么问题
公钥 U = kP 已经公开,私钥 k 必须保密。签名要做到两件事:只有握着 k 的人才能算出来,任何拿着 U 的人都能检查。ECDSA 的签名就是满足这两点的一对数 (r, s)。
从哪来(补充)
ECDSA 由 Scott Vanstone 在 1992 年提出,当时是回应 NIST 对第一版 DSS 提案的征求意见。之后它陆续成为标准:1998 年进入 ISO 14888-3,1999 年成为 ANSI X9.62,2000 年进入 IEEE 1363-2000 和 FIPS 186-2。
出处:Johnson、Menezes、Vanstone《The Elliptic Curve Digital Signature Algorithm (ECDSA)》
直觉
签名分两半。r 来自一个随机点 jP,它把这次签名「锚定」在曲线上的某个位置。s 把消息哈希 e、私钥 k 和 r 绑在一起,再除以 j。
这样一来,s 里同时藏着 j 和 k。外人只看到 r 和 s,解不开这两个未知数;验签时的那套代数正好能把 j 和 k 抵消掉。
一步一步看
目标:按五步走一遍 ECDSA 签名,看出 r 来自随机点 jP 的横坐标,s 才用到私钥。
-
对消息做两次 SHA-256,得到哈希 e。
-
从 1 到 n − 1 里随机取 j,这个数每次签名都要重新取。
-
用倍加法算出点 jP,取它的横坐标模 n,得到 r。
-
用私钥 k 算 s。
-
输出签名 (r, s)。
怎么算
签名公式:
r = (jP 的横坐标) mod n,s = j⁻¹(e + kr) mod n
意思是:r 是随机点的横坐标;s 是「哈希加私钥乘 r」再除以随机数,全部模 n。注意模的是基点的阶 n,坐标运算才模 p。
签名长 512 位:r、s 各是一个 256 位的数。
和第 4 讲 DSA 对照:
| DSA | ECDSA | |
|---|---|---|
| r 从哪来 | 一个模幂再模 q | 点 jP 的横坐标再模 n |
| s 的公式 | j⁻¹(e + kr) mod q | j⁻¹(e + kr) mod n |
| 难题 | 离散对数 | ECDLP |
s 的公式一模一样,只换了 r 的来源和模数。实际标准还要求:r 或 s 算出来为 0 时重新取 j,手算练习一般碰不到。
常见误解
把 s 的模数写成 p
r、s 都模 n,n 是基点的阶。p 只用在曲线坐标的运算里。练习题里 p = 17、n = 19,混用会得到错的签名。
以为 r 就是 jP 这个点
r 只取了点 jP 的横坐标,再模 n,是一个整数。签名里不带纵坐标。
试一下
签名用到了哪几样只有签名者知道的东西?
私钥 k 和随机数 j。e 和 r 都可以被别人算出或看到。
2. 验签五步
它解决什么问题
收到消息 m 和签名 (r, s) 的人,手里只有公钥 U。他要在不知道 k、也不知道 j 的情况下判断签名是不是真的。
直觉
验签的人没法直接重算 jP,因为不知道 j。但他可以用两块公开的积木 P 和 U 拼出一个点:取 P 的 u 倍、U 的 v 倍相加。u、v 由 e、r、s 算出,签名是真的,拼出来的就恰好是 jP。
一步一步看
目标:按五步走一遍 ECDSA 验签,看出验证方只用公钥算出一个点,再拿它的横坐标去比 r。
-
同样对消息做两次 SHA-256,得到 e。
-
求 s 在模 n 下的逆元 w。
-
算两个系数 u 和 v。
-
算点 Q = uP + vU。
-
Q 的横坐标模 n 等于 r,就接受签名。
怎么算
验签公式:
w = s⁻¹ mod n,u = ew mod n,v = rw mod n,Q = uP + vU
意思是:先把 s 倒过来,再分别乘 e 和 r 得到两个系数;用它们把基点和公钥拼成一个点。当且仅当 r = Q 的横坐标 mod n 时接受。
整个过程只用公钥 U,用不到私钥 k,这正是签名的意义。
常见误解
把这里的 Q 当成公钥
这里的 Q 是验签中间算出来的点。上一页 Q = kP 里的 Q 是公钥,两者同名不同物。本页公钥一律叫 U。
以为验签要比较整个点
只比较横坐标模 n 是否等于 r。签名里本来就只有 r,没有纵坐标可比。
试一下
s = 1 时,w、u、v 分别等于什么?
w = 1⁻¹ = 1,u = e,v = r。这正是课件练习题的情况。
3. 为什么验得过
它解决什么问题
验签五步看上去像一串随意的运算。要相信它,必须能证明:签名是真的,拼出来的点就一定是 jP。这一步也是考试常问的推导。
直觉
把 u、v 代回去,把公钥 U 换成 kP,所有东西都变成 P 的某个倍数。这个倍数整理一下,正好是 w(e + kr)。而 s 的定义说的就是 s 等于 j⁻¹(e + kr),倒过来 w(e + kr) 就是 j。
一步一步看
目标:把验签的点 uP + vU 逐步代入化简,看出它为什么正好回到签名时的 jP。
-
从验签的点出发:uP + vU。
-
代入 u = ew、v = rw,U = kP,得 ewP + rw·kP。
-
提出公因子:w(e + kr)P。
-
由 s = j⁻¹(e + kr) 得 w = j(e + kr)⁻¹,所以 w(e + kr) = j,点就是 jP。
-
jP 的横坐标模 n 正是签名时的 r,所以真签名一定能通过。
怎么算
一行推导:
uP + vU = (u + vk)P = w(e + kr)P = jP
意思是:验签拼出的点就是签名时的随机点,横坐标自然对得上。
手算时可以用它自查:算出 (u + vk) mod n,如果等于签名时的随机数,最后的点一定对。考试时仍要按五步写,自查只是核对。
常见误解
以为推导里用到了私钥,所以验签要知道私钥
推导是写给人看的证明,借用了 U = kP 这层关系。实际验签时直接用公开的 U 算 vU,不需要知道 k。
以为 w(e + kr) 要模 p
整个推导里的系数都是 P 的倍数,倍数按阶 n 取模,所以是模 n。
试一下
用课件练习的数字自查:u = 9,v = 10,私钥 7,n = 19,u + v × 私钥 模 19 等于多少?
9 + 10 × 7 = 79,79 = 76 + 3,结果 3,正好是签名时的随机数。
4. 随机数重用:同一个 j 签两次
它解决什么问题
签名公式里 j 是唯一的「新鲜」成分。课件只说随机取 j,没说为什么一定要每次重取。这一节说明:j 只要重复一次,私钥就会被公开数据算出来。
从哪来(补充)
这不是纸上谈兵。2010 年 12 月,fail0verflow 小组公开恢复出索尼给 PS3 软件签名用的 ECDSA 私钥,原因是索尼每次签名都用同一个静态随机数。标准还规定,r 或 s 算出为 0 时要重取随机数,验签时要求 r、s 都在 [1, n − 1] 内。
出处:Wikipedia: Elliptic Curve Digital Signature Algorithm
直觉
j 相同,jP 就相同,两条签名的 r 也相同。攻击者一眼就能看出这两条签名用了同一个 j。
两条 s 的公式里,j 和 k 是同样的两个未知数,e₁、e₂、s₁、s₂、r 全是公开的。两个方程、两个未知数,先消掉 k 解出 j,再代回去解出 k。
一步一步看
目标:把用同一个 j 签出的两条签名相减,看出 j 和私钥 k 怎样被依次解出来。
-
两条签名 (r, s₁)、(r, s₂) 的 r 相同,对应哈希 e₁、e₂。
-
两式相减:s₁ − s₂ = j⁻¹(e₁ − e₂),k 被消掉。
-
解出 j。
-
把 j 代回任意一条签名的公式,解出私钥 k。
怎么算
两步公式:
j = (e₁ − e₂)/(s₁ − s₂) mod n,k = (s₁j − e₁)/r mod n
意思是:除法都换成乘模 n 的逆元。只要两条签名的 r 相同,这两行就能算出私钥。
用课件练习的参数验证过:e₁ = 9、e₂ = 5 用同一个随机数 3 签名,得 s₁ = 1、s₂ = 6;第一行还原出随机数 3,第二行还原出私钥 7。
常见误解
以为随机数只要保密就行,重复用没关系
重复用本身就会泄露它。两条签名的 r 一样,攻击者不需要事先知道 j,从公开数据就能解出来。
以为随机数用伪随机生成就一定安全
生成器坏了、种子固定了,j 就会重复或可预测,效果和静态随机数一样。PS3 的事故就是每次用同一个值。
试一下
两条签名的 r 相同说明了什么?
说明它们用了同一个 j(或者极巧合地碰上同一个横坐标),攻击者可以按上面两步解出私钥。
把它们串起来
签名用私钥和一次性随机数造出 (r, s),验签只用公钥把同一个随机点拼回来,一行代数保证真签名一定通过。随机数是整套流程里最脆弱的一环,重复一次就前功尽弃。
| 环节 | 用到的秘密 | 用到的公开信息 | 输出 |
|---|---|---|---|
| 签名 | 私钥、随机数 | 消息、基点、n | (r, s) |
| 验签 | 无 | 消息、(r, s)、公钥、基点、n | 接受或拒绝 |
| 重用攻击 | 无 | 两条同 r 的签名 | 随机数、私钥 |
下一讲进入比特币交易:每个输入里的解锁脚本带的就是这里的 ECDSA 签名,验签那五步由每个节点替你跑一遍。
课件里的坑
- [字母] p.29–31 用 k 表示私钥、j 表示随机数;p.36 的练习换成 d 表示私钥、k 表示随机数。做题前先看清题目用哪套字母,最容易把两者代反。
- [同名] p.31 验签里的 Q 是中间点,和 p.26 里 Q = kP 的公钥 Q 不是同一个东西。
- [模数] p.30 第 4 步的模是 n(点的阶),不是 p(坐标的模);p.36 里 p = 17、n = 19。
- [漏条件] p.30 没写 r 或 s 为 0 时要重取随机数,标准里有这一条。
- [题目假设] p.36 说「假设 G 的阶是 19」。这条曲线连 O 共 19 个点,19 是素数,所以假设成立。
课后 10 分钟:考点复习
这 10 分钟怎么用:先默写签名、验签两组公式;再合上页面,把 p.36 的练习从 2G 一路算到验签结果;做完用 u + vd 自查;最后做变式题。
必背
- ECDSA 参数:曲线、基点 P、阶 n;私钥 k ∈ {1, …, n − 1},公钥 U = kP
- 签名:e = SHA256(SHA256(m)),r = (jP 的 x) mod n,s = j⁻¹(e + kr) mod n,签名 512 位
- 验签:w = s⁻¹,u = ew,v = rw,Q = uP + vU,接受当且仅当 r = x mod n
- 验得过的原因:uP + vU = w(e + kr)P = jP
- p = 17 练习:kG = (10, 6),r = 10,k⁻¹ = 13,s = 1,公钥 (0, 6),验签得 (10, 6),有效
- 同一个随机数签两条消息,r 相同,可以先解出随机数,再解出私钥
课件例题
例 1(课件 p.36):小参数 ECDSA 签名与验签
见下方完整例题。
例 2(课件 p.31):证明验签会接受真签名
提示
把 u、v 代进 uP + vU,再用 U = kP 和 s 的定义。
解答
uP + vU = ewP + rw·kP = w(e + kr)P。由 s = j⁻¹(e + kr) 得 w = s⁻¹ = j(e + kr)⁻¹,所以 w(e + kr) = j,uP + vU = jP,横坐标模 n 就是签名时的 r。
例 3(课件 p.30):说明签名的组成和长度
提示
r、s 各自从哪来,各有多少位。
解答
r 是随机点 jP 的横坐标模 n,s = j⁻¹(e + kr) mod n。n 是 256 位素数,r、s 各 256 位,签名共 512 位。
完整例题
题面(课件 p.36):p = 17,曲线 y² = x³ + 2x + 2,基点 G = (5, 1),阶 n = 19。私钥 d = 7,随机数 k = 3,消息哈希 H(m) = 9。求签名,并验证。
约定:这一题私钥叫 d、随机数叫 k;坐标模 17,r、s、u、v 模 19。
解法:
- 2G:λ = (3 × 25 + 2) × 2⁻¹ = 77 × 9,77 ≡ 9,λ = 81 ≡ 13;x = 169 − 10 = 159 ≡ 6;y = 13 × (5 − 6) − 1 = −14 ≡ 3。2G = (6, 3)。
- 3G = 2G + G:λ = (1 − 3)/(5 − 6) = 2;x = 4 − 6 − 5 = −7 ≡ 10;y = 2 × (6 − 10) − 3 = −11 ≡ 6。kG = (10, 6)。
- r = 10 mod 19 = 10。
- k⁻¹:3 × 13 = 39 = 38 + 1,k⁻¹ = 13。
- s = 13 × (9 + 7 × 10) = 13 × 79;79 ≡ 3,13 × 3 = 39 ≡ 1。签名 (r, s) = (10, 1)。
- 验签:公钥 Q = 7G = (0, 6);w = 1⁻¹ = 1;u = 9 × 1 = 9;v = 10 × 1 = 10。
- uG = 9G = (7, 6);vQ = 10 × 7G = 70G,70 = 57 + 13,即 13G = (16, 4)。
- (7, 6) + (16, 4):λ = (4 − 6)/(16 − 7) = −2 × 9⁻¹ = 15 × 2 = 30 ≡ 13;x = 169 − 7 − 16 = 146 ≡ 10;y = 13 × (7 − 10) − 6 = −45 ≡ 6。得 (10, 6)。
- 10 mod 19 = 10 = r,签名有效。
- 自查:u + vd = 9 + 70 = 79 ≡ 3 = k,和签名时的点一致。
要点:字母先对齐;坐标模 17、系数模 19 不能混;70G 先把 70 模 19 再查表。
答题格式:分 Q1、Q2 两段。Q1 依次写 kG、r、k⁻¹、s;Q2 依次写公钥、w、u、v、uG、vQ、两点相加、结论。
变式题(先自己做)
(1) 改编自课件 p.36:同一条曲线和 G,私钥 d = 5,随机数 k = 2,H(m) = 4,求签名并验证。 (2) 改编自课件 p.30:用 p.36 的参数(私钥 7,n = 19,r = 10),同一个随机数 3 又签了 H(m) = 5 的消息,得到 s₂ = 6。已知两条签名,求私钥。
提示
(1) 2⁻¹ mod 19 = 10,17⁻¹ mod 19 = 9;80 模 19 是 4。(2) 先算 (e₁ − e₂)/(s₁ − s₂),14⁻¹ mod 19 = 15,10⁻¹ mod 19 = 2。
判分点与答案(非官方评分标准)
判分点:① 字母代对;② 模数分清 17 和 19;③ (1) 验签最后点的横坐标等于 r;④ (2) 两步都写出来。
(1) kG = 2G = (6, 3),r = 6;k⁻¹ = 10;s = 10 × (4 + 5 × 6) = 340 ≡ 17。签名 (6, 17)。公钥 5G = (9, 16);w = 17⁻¹ = 9;u = 4 × 9 = 36 ≡ 17;v = 6 × 9 = 54 ≡ 16。uG = 17G = (6, 14);vQ = 16 × 5G = 80G = 4G = (3, 1)。(6, 14) + (3, 1):λ = 13 × 3⁻¹ = 13 × 6 = 78 ≡ 10(mod 17),x = 100 − 6 − 3 = 91 ≡ 6,y = 10 × 0 − 14 ≡ 3,得 (6, 3),6 = r,有效。自查 u + vd = 17 + 80 = 97 ≡ 2。
(2) j = (9 − 5)/(1 − 6) = 4 × (−5)⁻¹ = 4 × 14⁻¹ = 4 × 15 = 60 ≡ 3。私钥 = (1 × 3 − 9)/10 = −6 × 2 = −12 ≡ 7。
闪卡自测
1. ECDSA 的私钥和公钥各是什么?
私钥 k ∈ {1, …, n − 1},公钥 U = kP(p.29)。
2. 比特币里 e 怎么算?
e = SHA256(SHA256(m)),两次 SHA-256(p.30)。
3. r 和 s 的公式?
r = jP 的横坐标 mod n,s = j⁻¹(e + kr) mod n(p.30)。
4. 签名多长?
512 位,r、s 各 256 位(p.30)。
5. 验签五步?
算 e;w = s⁻¹;u = ew,v = rw;Q = uP + vU;Q 的横坐标模 n 等于 r 则接受(p.31)。
6. 为什么验得过?
uP + vU = w(e + kr)P = jP(p.31 补充推导)。
7. p.36 练习里私钥和随机数各用什么字母?
私钥 d,随机数 k,和 p.29–31 不同(p.36)。
8. p.36 练习的签名是多少?
(10, 1),验签得 (10, 6),有效(p.36)。
9. 同一个随机数签两次会怎样?
两条签名 r 相同,可先解出随机数,再解出私钥(p.30 补充)。
下一讲
比特币交易:输入、输出和 UTXO,每个输入里的签名就是这一讲的 ECDSA。见 L09a。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。