← COMP5521 全部讲次
L08b · 第 8 周

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 却没有捷径。

  1. 选一条点数是素数的曲线和一个基点 P,大家都知道。

  2. 选一个整数 k 当私钥,自己保密。

  3. 算 Q = kP,把 Q 公开当公钥。这一步用倍加法,几百次点运算就够。

  4. 别人手里只有 P 和 Q。要找 k,除了一个个试倍数,没有已知的捷径。

    左框是私钥 k 和基点 P,右框是公钥 Q=kP;上方实线箭头从左到右写着倍点加法几百次点运算,下方青绿虚线箭头从右往左表示求 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。

  1. 13 写成二进制是 1101。

  2. 最高位 1:起点 G = (5, 1)。

  3. 下一位 1:先倍点得 2G = (6, 3),再加 G 得 3G = (10, 6)。

  4. 下一位 0:只倍点,得 6G = (16, 13)。

  5. 最后一位 1:倍点得 12G = (0, 11),再加 G 得 13G = (16, 4)。

    六个方框排成一行:G(5,1) 倍到 2G(6,3),加 G 到 3G(10,6),倍到 6G(16,13),倍到 12G(0,11),加 G 到青绿的 13G(16,4);下方注明共 3 次倍点 2 次加法

  6. 一共 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% 以上。

出处:Bitcoin Wiki: Secp256k1

直觉

名字可以拆开读:sec 是标准名,p 表示定义在模素数 p 上,256 是位数,k 表示 Koblitz 曲线,1 是编号。

方程只有 y² = x³ + 7,a = 0,所以倍点公式的 λ 里只剩 3x₁²。课件那张图画的是实数上的平滑曲线,实际用的模 p 版本是一片看起来随机的散点。

一步一步看

目标:逐项认清 secp256k1 的曲线、素数 p、基点和阶 n,并留意课件印的常数为什么不能原样照抄。

  1. 曲线:y² = x³ + 7 mod p,即 a = 0、b = 7。

  2. 素数 p:比 2²⁵⁶ 略小。

  3. 基点 P = (x, y):所有比特币公钥都是它的倍数。

  4. n:基点的阶,也是 256 位素数,nP = O。私钥从 1 到 n − 1 里选。

  5. 课件把四个十六进制常数各印错一处,原样代进去,基点不在曲线上,p 和 n 也不是素数。

    四行对照表:p 第 7 组印成 FFFFFFFF 应为 FFFFFFFE;基点 x 第 6 组少一位应为 2DCE28D9;基点 y 第 8 组少一位应为 FB10D4B8;n 第 4 组应为 FFFFFFFE,正确值用青绿

怎么算

正确的 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。

  1. 双方约定曲线和基点 P。

  2. A 选私钥 a,公开 aP;B 选私钥 b,公开 bP。

  3. A 收到 bP,算 a·(bP);B 收到 aP,算 b·(aP)。

  4. 两边得到同一个点 abP,拿它当共享密钥。

    左边 A 选私钥 a 公开 aP,右边 B 选私钥 b 公开 bP,两条箭头互相发送;下排 A 算 a 乘 bP、B 算 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 的十六进制常数不用背,背结构。

必背

  1. ECDLP:已知 k、P 算 Q = kP 容易,已知 Q、P 求 k 难
  2. 倍加法:按 k 的二进制从高位读,遇 1 倍点再加 P,遇 0 只倍点,约 log₂k 次倍点
  3. 比特币用 secp256k1:y² = x³ + 7 mod p,a = 0,b = 7,p 和 n 都是 256 位素数
  4. n 是基点 P 的阶,nP = O,私钥取值范围是 {1, …, n − 1}
  5. 课件 p.28 的 secp256k1 常数印错四处,正确的 p = 2²⁵⁶ − 2³² − 977
  6. ECDH:A 公开 aP,B 公开 bP,双方都算出 abP 当共享密钥

课件例题

例 1(课件 p.28):核对 secp256k1 的常数

题面:课件给出 p、基点 (x, y) 和阶 n。指出哪些地方印错,并写出 p 的简洁形式。

课件原样印出的 secp256k1 常数,每 8 位十六进制一组:p 是七组 FFFFFFFF 加末组 FFFFFC2F;x 是 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D 59F2815B 16F81798;y 也是八组,从 483ADA77 起到末组 FB10D4B;n 是四组 FFFFFFFF 后接 BAAEDCE6 AF48A03B BFD25E8C D0364141
图片来源:COMP5521 Lecture_8-elliptic curve cryptography.pdf, p.28
提示

每 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₁)⁻¹。

解法:

  1. 13 = 1101(二进制)。最高位 1,起点 G = (5, 1)。
  2. 倍点得 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)。
  3. 这一位是 1,加 G:λ = (1 − 3)/(5 − 6) = 2。x = 4 − 6 − 5 = −7 ≡ 10,y = 2 × (6 − 10) − 3 = −11 ≡ 6。3G = (10, 6)。
  4. 下一位 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)。
  5. 最后一位 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)。
  6. 再加 G:λ = (1 − 11)/(5 − 0) = −2 ≡ 15。x = 225 − 0 − 5 = 220 ≡ 16,y = 15 × (0 − 16) − 11 = −251 ≡ 4。13G = (16, 4)。
  7. 核对: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。

下一讲 →
L08b-2 L08b-2 ECDSA:比特币怎样用椭圆曲线签名

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