椭圆曲线中的Double-and-Add

这张图在讲一件事：椭圆曲线标量乘法K⋅P（也就是“用整数 K 去乘一个点 P”）在实现里，最终会被拆成：

1. 上层的点运算：EC-Double（倍点，2Q）和EC-Add（加点，Q+P）

2. 更底层的有限域运算：FF-Mult / FF-Add / FF-Square（域乘/域加/域平方）

1) Double-and-Add 是怎么把 K⋅P 拆开的？

图顶端写了：

• n= Key size（通常指K的bit长度，比如 256 位）

• h= Hamming weight（K的二进制里1 的个数）

在经典二进制 **Double-and-Add（倍加法）**里（从最高位扫到最低位）：

• 每处理 1 个bit，必做 1 次 Double→ 次数大约是 n（严格说是 n−1）

• 遇到该bit为 1，才做 1 次 Add→ 次数大约是 h（严格说常见实现是 h−1，看初始化方式）

所以图里从 K⋅P 分两条边到：

• EC-Double上标n

• EC-Add上标h

这就是 Double-and-Add 的核心计数逻辑。

一个常见伪代码（MSB-first）：

Q = O // 无穷远点 for i from n-1 downto 0: Q = 2Q // EC-Double（每轮必做） if k_i == 1: Q = Q + P // EC-Add（看该位是否为1） return Q

2) 图里为什么强调“倍点/加点”下面又分解成 FF 运算？

因为在椭圆曲线实现中，点的坐标在有限域里（比如​ 或​），点公式里的加减乘平方，最后全都落到域运算：

• FF-Add：域加（通常很便宜，模 p 加减）

• FF-Square：域平方（在很多实现里比乘法略便宜/可优化）

• FF-Mult：域乘（最贵，涉及大整数乘法/约简）

图底部还写了复杂度暗示：

• FF-Mult标成：意思是大整数乘法在高阶算法（FFT/NTT）下可到这个量级（至少强调“乘法是主成本”）。

• FF-Add、FF-Square标 O(1)：表示相对便宜（更像“常数级开销”对比乘法的主导地位）。

3) 图上那些 7、13、4、5、7、1 是什么意思？

这些数字是在说：一次点运算，大概要用多少次域运算（在某种坐标表示/公式下；不同曲线、不同坐标系数字会变，但“乘法最贵”这一结论不变）。

从图里读数：

一次EC-Double约等于：

• 7 次FF-Mult

• 4 次FF-Add

• 5 次FF-Square

一次EC-Add约等于：

• 13 次FF-Mult

• 7 次FF-Add

• 1 次FF-Square

（你会发现：加点比倍点更贵，尤其多了很多乘法。）

现实工程里之所以会出现这种“几十个域运算的组合”，通常是因为实现用的是射影坐标/雅可比坐标来避免“求逆（inversion）”，因为域求逆往往比很多次乘法还贵。图里也刻意没画 inversion，正是这个思路。

4) 把整张图合起来：Double-and-Add 的总体成本怎么估？

如果把一次倍点成本记为​，一次加点成本记为，那么：

再用图里的分解，把成本进一步写成域乘/加/平方的数量级：

• 域乘次数

• 域加次数

• 域平方次数

因为域乘最贵，所以标量乘法的速度基本由“需要做多少次域乘”决定。

5) 工程上 Double-and-Add 的两个关键点

A. 性能优化方向

• 减少EC-Add次数（减少 h）：例如用NAF、wNAF、窗口法、预计算 P,3P,5P...

• 降低一次加点/倍点的域乘数量：选更优的坐标系/公式（Jacobian、Edwards 等）

B. 安全（侧信道）问题

朴素 Double-and-Add 的if bit==1 then Add会让耗时/功耗/分支行为随bit变化，可能泄露密钥。常见对策：

• Montgomery ladder（每一位都做固定模式的 double+add）

• 常数时间实现（避免条件分支、避免数据相关内存访问）

下面用一个非常小的“玩具曲线”，把椭圆曲线里的 **Double-and-Add（倍点-加点）**完整算一遍（每一步都带模运算与逆元），你就能直观看到图里“上层 EC-Double/EC-Add → 下层有限域运算”的含义。

1) 选一条玩具曲线 + 基点

取素域（也就是所有计算都对 17 取模）：

选点（基点）：

P=(5,1)

验证它在曲线上：

• 左边：

• 右边：

左右同为 1，所以。

2) 目标：算 K⋅P，取一个小整数 K=13​

• bit长度 n=4

• 汉明重量 h=3（1 的个数是 3）

这正对应你图里“EC-Double 约 ∼n、EC-Add 约 ∼h”的意思。

3) 点加 / 倍点公式（仿射坐标，素域）

设。

(1) 加点 P1≠P2​

(2) 倍点

然后同样算。

这里的“”就是模逆元：找一个数 t，使得。

4) 用 Double-and-Add（从高位到低位）计算 13P

用一种常见写法：先把最高位的 1 吃掉，令 Q=P，然后处理剩余位（这样加点次数是 h−1）。

​：最高位是 1，所以先设

接下来处理剩余三位：1、0、1，每一位都先Double，若该位为 1 再Add P。

第 1 位：1

4.1 先倍点：

P=(5,1)

• 分母，（因为）

所以

算坐标：

因此：

2P=(6,3)

4.2 再加点（因为该位=1）：

(6,3)+(5,1)

• −2 mod 17=15

• −1 mod 17=16，且（因为）

所以： 3P=(10,6)

第 2 位：0

4.3 只倍点：Q=2Q=2(3P)=6P

对 (10,6) 倍点：

• 分母 12，（因为）

所以：

6P=(16,13)

（该位为 0，不加点）

第 3 位：1

4.4 先倍点：Q=2Q=12P

对 (16,13) 倍点：

• 分子 3⋅1+2=5

• 分母，（）

所以：

12P=(0,11)

4.5 再加点（因为该位=1）：Q=12P+P=13P

(0,11)+(5,1)

• −10 mod 17=7

• （因为）

最终：

13P=(16,4)

5) 和图的对应关系（为什么 Double-and-Add 的成本长这样）

• 本例 n=4，处理剩余 3 位：做了3 次 EC-Double

• h=3，除去最高位那次初始化：做了2 次 EC-Add

而图里进一步强调：每次 EC-Double / EC-Add 都要展开成很多次有限域乘/加/平方，并且域乘最贵，所以整体性能基本看“要做多少次域乘”。