Alan's Blog

点的加法 $P + Q$#

给定两点 $P=(x_1,y_1)$, $Q=(x_2,y_2)$：

• 如果 $P = \mathcal{O}$ → $P + Q = Q$
• 如果 $Q = \mathcal{O}$ → $P + Q = P$
• 如果 $x_1 = x_2$ 且 $y_1 \equiv -y_2 \pmod p$ → $P+Q = \mathcal{O}$ （互为对称点）
• 否则，斜率为： $$\lambda = \frac{y_2 - y_1}{x_2 - x_1} \pmod p$$ 结果点 $R = (x_3,y_3)$： $$x_3 = \lambda^2 - x_1 - x_2 \pmod p$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \pmod p$$

倍点 $2P$#

若 A 与 B 重合，其结果等同 2A（Point Doubling），即与曲线作切线求交点。

如果 $P=(x_1,y_1)$，则： • 若 $y_1 = 0$ → $2P = \mathcal{O}$ • 否则：

标量乘法 / Scalar Multiplication $kP$#

这是 ECC 的核心运算，也是公钥生成和加密的基础。ECDLP 的难题：已知 P 和 Q = kP，求 k 在大素数域下是指数级困难。

定义为 $P$ 自加 $k$ 次，即：

实际计算中用双倍-加法算法 (double-and-add)：

• 把 $k$ 写成二进制
• 每次循环做“倍点”和“条件加法”
• 时间复杂度 $O(\log k)$

由此可见 ECC 的加密与解密本质上都是标量乘法运算，可通过 double-and-add 或 windowing 等算法以 O(log k) 复杂度完成。这也引出了其与 RSA 的差异：

• RSA：加密快，解密慢
• ECC：加密与解密同速

如下为基点在有限域内经过多次点加后的结果。