L08b 椭圆曲线密码:单向的 kP、倍加法、secp256k1 和 ECDH
为什么已知 kP 求 k 很难,kP 自己又怎样快速算出来;比特币选的 secp256k1 曲线和课件印错的四处常数;最后用两个点换出同一个密钥。
一句话版
在一条点数是大素数的椭圆曲线上,给定整数 k 和点 P,算出 kP 只要几百次点运算;反过来只给 P 和 kP,求 k 没有已知的快办法。这道「求 k」的难题叫 ECDLP,比特币的私钥是 k,公钥是 kP,安全性就靠它。
这一页先讲这道难题,再讲 kP 本身怎么算得快,然后看比特币选的那条具体曲线,最后用同一道难题让两个人交换出一把共享密钥。点加法公式见 L08a,模 p 上的点群见 L08a-2。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| kP | 读「k 倍 P」 | 点 P 自己加自己 k 次 |
| ECDLP | elliptic curve discrete logarithm problem | 已知 P 和 kP,求 k 的难题 |
| 基点 | base point,常写 P 或 G | 大家约定好的起点,所有公钥都是它的倍数 |
| 倍加法 | double-and-add | 按 k 的二进制一边倍点一边加点,快速算 kP |
| secp256k1 | 读「sec-p-256-k-1」 | 比特币用的那条曲线的名字 |
| n | order of the base point | 基点的阶,nP = O |
| ECDH | elliptic curve Diffie-Hellman | 两个人只交换点,算出同一个密钥 |
一个类比:在环形跑道上跑圈
把曲线上的点群想成一条环形跑道,跑道上有 n 个格子。基点 P 是起跑线,每加一次 P 就往前跳一格,但每一跳落在哪儿看上去毫无规律,跳着跳着就满场乱窜。
告诉你「跳了 k 次」,你可以很快算出终点在哪。告诉你终点,问你跳了几次,你只能从头一次次试,因为终点的位置不会透露它离起点多远。
跑道上有个捷径:会「分身」的跑者可以一步把已经跑的步数翻倍。这就是倍点,靠它跑 k 步只需要大约「k 的二进制位数」那么多次动作。
类比在哪里失效:
- 真实跑道上能量距离,曲线上的点没有「离起点多远」这种量,这正是难的原因。
- 跑道格子顺着排;点的坐标和倍数之间没有可见的顺序关系。
- 小曲线上确实可以把所有倍数列一张表去查,类比里的「从头试」是可行的;只有 n 大到 256 位时才真正试不完。
从零讲起
1. ECDLP:往前算容易、往回求难
它解决什么问题
公钥密码需要一个「单向」的运算:用私钥算公钥很快,用公钥倒推私钥做不到。第 2 讲的离散对数 gˣ mod n 是一个例子,椭圆曲线上的 kP 是另一个,而且同样安全时需要的数字更短。
从哪来(补充)
把椭圆曲线用到密码学上,是 Neal Koblitz 和 Victor S. Miller 在 1985 年各自独立提出的。之后很长一段时间只在学术界流行,2004 年起才进入广泛使用,今天 TLS 和比特币都在用。
出处:Wikipedia: Elliptic-curve cryptography
直觉
点加法的结果在曲线上跳来跳去。上一页模 11 的例子里,1α 在 (2, 7),2α 跳到 (5, 2),3α 又跳到 (8, 3),坐标和倍数之间看不出任何关系。
小曲线上,求 k 的办法就是把 P 的倍数一个个列出来比对。13 个点的群几秒就能翻完;基点的阶 n 有 256 位时,这张表的长度是个天文数字,列不完。
一步一步看
目标:从选私钥走到公开 Q = kP,看出正着算只要几百次点运算,反过来求 k 却没有捷径。
-
选一条点数是素数的曲线和一个基点 P,大家都知道。
-
选一个整数 k 当私钥,自己保密。
-
算 Q = kP,把 Q 公开当公钥。这一步用倍加法,几百次点运算就够。
-
别人手里只有 P 和 Q。要找 k,除了一个个试倍数,没有已知的捷径。
怎么算
ECDLP 的两个方向:
Q = kP
意思是:已知 k 和 P,算 Q 很容易;已知 Q 和 P,求出 k 很难,这个 k 叫 Q 的「椭圆曲线离散对数」。
和第 2 讲的离散对数逐项对应:
| 离散对数 | 椭圆曲线离散对数 |
|---|---|
| 乘法群里的 g | 曲线上的基点 P |
| 幂 gᵏ | 倍数 kP |
| 已知 gᵏ 求 k 难 | 已知 kP 求 k 难 |
课件要求曲线的阶是素数,这样每个非 O 点都是生成元,k 的取值范围就是 1 到 n − 1。
常见误解
以为 kP 是把坐标乘以 k
kP 是 P 自己做 k 次点加法,坐标要一步步按公式算,和把 x、y 各乘 k 毫无关系。坐标乘 k 得到的点一般根本不在曲线上。
以为「难」是说永远算不出来
小曲线上逐个试就能算出来。「难」说的是没有比逐个试快很多的已知办法,n 一大,逐个试的时间就远超现实。
试一下
在 y² = x³ + x + 6 (mod 11) 上,已知 Q = (7, 9),α = (2, 7),求 k 使 Q = kα。
查上一页的 α 表:6α = (7, 9),所以 k = 6。小群可以直接查表,这正说明安全性要靠很大的 n。
2. 倍加法:kP 本身怎么算得快
它解决什么问题
如果算 kP 要老老实实加 k − 1 次,k 有 256 位时谁也算不完,公钥都生成不出来。倍加法让「往前算」真正变快,单向性的另一半才成立。
从哪来(补充)
倍加法按 k 的二进制位逐位处理,迭代次数约为 log₂k,和模幂里的「平方-乘法」是同一个思路。它有一个实战弱点:遇到 1 要多做一次加法,运行时间会随 k 的二进制位变化,容易被计时分析攻击,实际实现常改用 Montgomery ladder。
出处:Wikipedia: Elliptic curve point multiplication
直觉
倍点一步就能把倍数翻一番:P 变 2P,2P 变 4P,4P 变 8P。课件总结页那张图画的就是这件事,每次「切线 + 翻折」翻一番。
任意 k 都能写成二进制,二进制就是「翻倍再加一」的记录。从最高位往下读,每读一位就把手里的倍数翻倍;这一位是 1 的话,再补加一个 P。
一步一步看
目标:按 13 的二进制逐位倍点或加点算出 13G,看出 5 次点运算就能代替逐个加的 12 次。
用 L08b-2 练习题那条曲线 y² = x³ + 2x + 2 (mod 17),G = (5, 1),算 13G。
-
13 写成二进制是 1101。
-
最高位 1:起点 G = (5, 1)。
-
下一位 1:先倍点得 2G = (6, 3),再加 G 得 3G = (10, 6)。
-
下一位 0:只倍点,得 6G = (16, 13)。
-
最后一位 1:倍点得 12G = (0, 11),再加 G 得 13G = (16, 4)。
-
一共 3 次倍点、2 次加法,5 次点运算;一个个加要 12 次。
怎么算
倍加法的规则:
- 把 k 写成二进制,从最高位往下读
- 手里的结果先置为 P(对应最高位的 1)
- 每读下一位:先倍点;这一位是 1 就再加 P
意思是:倍点次数等于 k 的二进制位数减 1,约 log₂k 次;加法次数等于其余位里 1 的个数。256 位的 k 大约 256 次倍点,加法最多 256 次,加起来几百次点运算。
常见误解
以为倍加法从最低位读起也一样
这一页讲的写法是从最高位读,每步「先倍再看要不要加」。从最低位读也能做,但要额外维护一串 P、2P、4P……,步骤不同,答题时别把两种混写。
以为每一位都要做一次加法
只有是 1 的位才加。读到 0 只倍点。13 = 1101 里有一个 0,那一步只倍不加。
试一下
用倍加法算 6G 需要几次倍点、几次加法?
6 = 110。G → 2G(倍)→ 3G(加)→ 6G(倍),2 次倍点、1 次加法。查表 6G = (16, 13)。
3. secp256k1:比特币选的那条曲线
它解决什么问题
前面的讨论都是「某一条曲线」。真要用,所有人必须约定同一条曲线、同一个基点和它的阶,否则你的公钥别人没法验证。比特币约定的就是 secp256k1。
从哪来(补充)
secp256k1 定义在 Certicom 公司的 SEC 2 标准里。它是一条 Koblitz 曲线,参数 a = 0、b = 7 按特殊的非随机方式构造,常数是可预测的。按 Bitcoin Wiki 的说法,充分优化后它的运算比其他曲线快 30% 以上。
直觉
名字可以拆开读:sec 是标准名,p 表示定义在模素数 p 上,256 是位数,k 表示 Koblitz 曲线,1 是编号。
方程只有 y² = x³ + 7,a = 0,所以倍点公式的 λ 里只剩 3x₁²。课件那张图画的是实数上的平滑曲线,实际用的模 p 版本是一片看起来随机的散点。
一步一步看
目标:逐项认清 secp256k1 的曲线、素数 p、基点和阶 n,并留意课件印的常数为什么不能原样照抄。
-
曲线:y² = x³ + 7 mod p,即 a = 0、b = 7。
-
素数 p:比 2²⁵⁶ 略小。
-
基点 P = (x, y):所有比特币公钥都是它的倍数。
-
n:基点的阶,也是 256 位素数,nP = O。私钥从 1 到 n − 1 里选。
-
课件把四个十六进制常数各印错一处,原样代进去,基点不在曲线上,p 和 n 也不是素数。
怎么算
正确的 p 有一个好记的写法:
p = 2²⁵⁶ − 2³² − 977
意思是:p 比 2²⁵⁶ 小一点点,二进制几乎全是 1。课件印的版本等于 2²⁵⁶ − 977,它不是素数。
四个正确常数(为了好读,每 4 位十六进制隔一个空格;前面说的「第几组」按 8 位一组数,也就是这里每两块算一组):
p = FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE FFFF FC2F
x = 79BE 667E F9DC BBAC 55A0 6295 CE87 0B07 029B FCDB 2DCE 28D9 59F2 815B 16F8 1798
y = 483A DA77 26A3 C465 5DA4 FBFC 0E11 08A8 FD17 B448 A685 5419 9C47 D08F FB10 D4B8
n = FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141
考试不会让人背这串数字。要记的是结构:p 和 n 都略小于 2²⁵⁶,n 是基点的阶,私钥范围由 n 决定。
常见误解
把 p 和 n 当成同一个数
p 是坐标取模用的素数,n 是基点的阶。两者都是 256 位、开头都是一串 F,但从第 4 组起就不同。签名里的 r、s 取模 n,坐标运算取模 p。
照着课件的常数直接代程序
课件四处印错,x、y 各少一位十六进制,只有 63 位。直接用会得到不在曲线上的「基点」。
试一下
secp256k1 上倍点公式的 λ 是什么?
a = 0,λ = (3x₁² + 0)/(2y₁) = 3x₁² × (2y₁)⁻¹ mod p。
4. ECDH:只交换点,算出同一把密钥
它解决什么问题
两个人在公开信道上要商量出一把只有他们知道的密钥。第 3 讲的 Diffie-Hellman 用模幂做到了这一点,换到椭圆曲线上就是 ECDH,课件只放了一个讲它的视频。
直觉
两个人各自选一个私钥,用它乘基点,把结果公开。拿到对方的点之后,再用自己的私钥乘一次。
乘法顺序不影响结果:a 倍的 (b 倍 P) 和 b 倍的 (a 倍 P) 都是 ab 倍 P。窃听者只看到 aP 和 bP,想要 abP 就得先从其中一个点求出 a 或 b,这就是 ECDLP。
一步一步看
目标:跟着双方各用私钥乘上对方公开的点,看出两边只交换点也能得到同一个 abP。
-
双方约定曲线和基点 P。
-
A 选私钥 a,公开 aP;B 选私钥 b,公开 bP。
-
A 收到 bP,算 a·(bP);B 收到 aP,算 b·(aP)。
-
两边得到同一个点 abP,拿它当共享密钥。
怎么算
共享密钥:
a·(bP) = b·(aP) = abP
意思是:两个人各做一次倍点乘法,结果相同。窃听者手里的 aP、bP 相加也只能得到 (a + b)P,得不到 abP。
和第 3 讲逐项对应:
| Diffie-Hellman | ECDH |
|---|---|
| 公开 gᵃ、gᵇ | 公开 aP、bP |
| 共享 gᵃᵇ | 共享 abP |
| 靠离散对数难 | 靠 ECDLP 难 |
常见误解
以为窃听者把 aP 和 bP 加起来就能得到密钥
点加法得到的是 (a + b)P,不是 abP。要得到 abP 必须知道 a 或 b 中的一个。
以为 ECDH 能证明对方身份
ECDH 只负责商量密钥,不知道对面是谁。中间人可以分别和双方各做一次 ECDH。证明身份要靠签名,见下一页。
试一下
在 y² = x³ + 2x + 2 (mod 17)、G = (5, 1) 上,a = 2,b = 3,共享密钥是 G 的几倍?
abG = 6G。查表 6G = (16, 13)。
把它们串起来
ECDLP 给出单向性,倍加法让单向的「容易那一头」真的容易。secp256k1 把所有参数定死,大家用同一条曲线、同一个基点。在这上面,私钥是整数,公钥是点。
| 东西 | 在比特币里 | 安全靠什么 |
|---|---|---|
| 私钥 k | 1 到 n − 1 里的整数 | 保密 |
| 公钥 kP | secp256k1 上的点 | 求 k 是 ECDLP |
| 算公钥 | 倍加法 | 几百次点运算 |
| 共享密钥 | ECDH 的 abP | ECDLP |
ECDH 解决了「商量密钥」,但没有回答「这条消息是不是你发的」。下一页用同一对私钥、公钥做签名,这就是比特币交易里用的 ECDSA。
课件里的坑
- [课件有误] p.28 的四个常数各印错一处:p 第 7 组应为 FFFFFFFE,x 第 6 组应为 2DCE28D9,y 第 8 组应为 FB10D4B8,n 第 4 组应为 FFFFFFFE。
- [读图提醒] p.27 的图是实数上的 y² = x³ + 7。实际的 secp256k1 定义在模 p 上,图像是一片看起来随机的散点。
- [符号] p.26 里 Q = kP 的 k 是私钥;下一页 p.36 的练习里 k 变成了随机数,私钥改叫 d。
- [补充] p.35 只有 ECDH 视频链接,没有正文,ECDH 的流程是按第 3 讲的 Diffie-Hellman 补的。
- [读图提醒] p.33 总结页的倍点链图只画了 G、2G、4G、8G,没画加法那一步;任意 k 要靠倍点配合加法。
课后 10 分钟:考点复习
这 10 分钟怎么用:先用自己的话说清 ECDLP 哪头容易、哪头难;再合上页面,用倍加法把 13G 从头算一遍;最后做变式题。secp256k1 的十六进制常数不用背,背结构。
必背
- ECDLP:已知 k、P 算 Q = kP 容易,已知 Q、P 求 k 难
- 倍加法:按 k 的二进制从高位读,遇 1 倍点再加 P,遇 0 只倍点,约 log₂k 次倍点
- 比特币用 secp256k1:y² = x³ + 7 mod p,a = 0,b = 7,p 和 n 都是 256 位素数
- n 是基点 P 的阶,nP = O,私钥取值范围是 {1, …, n − 1}
- 课件 p.28 的 secp256k1 常数印错四处,正确的 p = 2²⁵⁶ − 2³² − 977
- ECDH:A 公开 aP,B 公开 bP,双方都算出 abP 当共享密钥
课件例题
例 1(课件 p.28):核对 secp256k1 的常数
题面:课件给出 p、基点 (x, y) 和阶 n。指出哪些地方印错,并写出 p 的简洁形式。
提示
每 8 位一组数,x、y 应各有 64 位十六进制。
解答
p 第 7 组应为 FFFFFFFE;x 第 6 组少一位,应为 2DCE28D9;y 第 8 组少一位,应为 FB10D4B8;n 第 4 组应为 FFFFFFFE。正确的 p = 2²⁵⁶ − 2³² − 977。课件原样的 p 等于 2²⁵⁶ − 977,不是素数;原样的基点也不在曲线上。
例 2(课件 p.26):说明 ECDLP 的两个方向
提示
一个方向用倍加法,另一个方向只能逐个试。
解答
已知 k、P 算 Q = kP:倍加法约 log₂k 次倍点,256 位的 k 几百次点运算。已知 Q、P 求 k:点加法结果在曲线上跳来跳去,没有已知捷径,只能逐个试,n 有 256 位时试不完。
完整例题
题面:曲线 y² = x³ + 2x + 2 (mod 17),G = (5, 1),用倍加法算 13G,并写出每一步的坐标。
约定:所有运算模 17;倍点用 λ = (3x₁² + 2)(2y₁)⁻¹,加法用 λ = (y₂ − y₁)(x₂ − x₁)⁻¹。
解法:
- 13 = 1101(二进制)。最高位 1,起点 G = (5, 1)。
- 倍点得 2G:λ = (75 + 2) × 2⁻¹ = 77 × 9,77 ≡ 9,λ = 81 ≡ 13。x = 169 − 10 = 159 ≡ 6,y = 13 × (5 − 6) − 1 = −14 ≡ 3。2G = (6, 3)。
- 这一位是 1,加 G:λ = (1 − 3)/(5 − 6) = 2。x = 4 − 6 − 5 = −7 ≡ 10,y = 2 × (6 − 10) − 3 = −11 ≡ 6。3G = (10, 6)。
- 下一位 0,只倍点:λ = (300 + 2) × 12⁻¹,302 ≡ 13,12⁻¹ = 10(12 × 10 = 120 = 119 + 1),λ = 130 ≡ 11。x = 121 − 20 = 101 ≡ 16,y = 11 × (10 − 16) − 6 = −72 ≡ 13。6G = (16, 13)。
- 最后一位 1,先倍点:λ = (768 + 2) × 26⁻¹,770 ≡ 5,26 ≡ 9,9⁻¹ = 2,λ = 10。x = 100 − 32 = 68 ≡ 0,y = 10 × (16 − 0) − 13 = 147 ≡ 11。12G = (0, 11)。
- 再加 G:λ = (1 − 11)/(5 − 0) = −2 ≡ 15。x = 225 − 0 − 5 = 220 ≡ 16,y = 15 × (0 − 16) − 11 = −251 ≡ 4。13G = (16, 4)。
- 核对:16³ + 2 × 16 + 2 = 4130 = 17 × 242 + 16,4² = 16,在曲线上。
要点:二进制从高位读;0 位只倍不加;每个分母先取余再求逆。
答题格式:先写二进制,再每步一行写「操作、λ、坐标」,最后验证。
变式题(先自己做)
(1) 改编自课件 p.26:同一条曲线和 G,用倍加法算 11G,写出用了几次倍点、几次加法。 (2) 改编自课件 p.35:同一条曲线和 G,A 的私钥 a = 3,B 的私钥 b = 5,写出双方公开的点和共享密钥。 (3) 自编情境:有人说「把 aP 和 bP 相加就能得到 ECDH 的共享密钥」,指出错在哪。
提示
(1) 11 = 1011。(2) 公开的是 3G 和 5G,共享的是 15G,可以查 G 的倍数表。(3) 点加法加的是倍数。
判分点与答案(非官方评分标准)
判分点:① 二进制写对;② 0 位不加;③ (2) 区分公开的点和共享的点;④ (3) 写出 (a + b)P。
(1) 11 = 1011:G → 2G(倍)→ 4G(倍)→ 5G(加)→ 10G(倍)→ 11G(加)。坐标依次是 (5, 1)、(6, 3)、(3, 1)、(9, 16)、(7, 11)、(13, 10)。3 次倍点、2 次加法。
(2) A 公开 3G = (10, 6),B 公开 5G = (9, 16)。共享密钥 15G = (3, 16)。
(3) aP + bP = (a + b)P,不是 abP。要得到 abP 必须知道 a 或 b。
闪卡自测
1. ECDLP 是什么?
已知 P 和 Q = kP,求整数 k(p.26)。
2. 为什么 kP 算得快?
倍加法,约 log₂k 次倍点,256 位的 k 只需几百次点运算(p.26)。
3. 倍加法读到 0 位做什么?
只倍点,不加 P(p.26 补充)。
4. secp256k1 的方程是什么?
y² = x³ + 7 mod p,a = 0、b = 7(p.27)。
5. p 和 n 分别是什么?
p 是坐标取模的素数,n 是基点的阶,nP = O,两者都是 256 位素数(p.28)。
6. 课件 p.28 印错几处?
四处:p 第 7 组、x 第 6 组、y 第 8 组、n 第 4 组(p.28)。
7. 正确的 p 怎么写?
2²⁵⁶ − 2³² − 977(p.28)。
8. 比特币的私钥和公钥各是什么?
私钥是 1 到 n − 1 里的整数 k,公钥是点 kP(p.29)。
9. ECDH 的共享密钥是什么?
A 公开 aP,B 公开 bP,双方都算出 abP(p.35 补充)。
下一讲
用同一对私钥、公钥给消息签名:ECDSA 签名五步、验签五步,为什么验得过,以及随机数重用会怎样泄露私钥。见 L08b-2。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。