ECC

数学基础

椭圆曲线

形如$y^2=x^3+ax^2+bx+c$的曲线被称为椭圆曲线，其中$\Delta = -16(4a^3 + 27b^2) \neq 0$。

常见曲线参数:

• secp256k1: $y^2 = x^3 + 7$

  $\begin{aligned} & a = 1 \\ & b = 7 \\ & p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 \\ & n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8D0364141 \\ & G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 \\ & G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 \end{aligned}$

• P-256(FIST): $y^2 = x^3 - 3x + b$

• BLS128_381: $y^2 = x^3 + 4$ 二次扩域: $y^2 = x^3 + 4(1 + i)$

• SM2: $y^2 = x^3 + ax + b$

  $\begin{aligned} & p = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF \\ & a = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC \\ & b = 28E9FA9E 9D9F5E34 4D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93 \\ & n = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123 \\ & G_x = 32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7 \\ & G_y = BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0 \end{aligned}$

• BN128(zk-snark): $y^2 = x^3 + 3$

  $\begin{aligned} & p = 21888242871839275222246405745257275088548364400416034343698204186575808495617 \\ & a = 0 \\ & b = 3 \\ & n = 21888242871839275222246405745257275088548364400416034343698204186575808495617 \\ \end{aligned}$

一些特殊曲线

• Baby Jubjub Elliptic Curve（扭曲爱德华曲线方程）：$ax^2 + y^2 = 1 + dx^2y^2$

  $\begin{aligned} & r = 21888242871839275222246405745257275088548364400416034343698204186575808495617 \\ & a = 168700 \\ & d = 168696 \\ & n = 21888242871839275222246405745257275088614511777268538073601725287587578984328 = h \times l \\ & h = 8 \quad l = 2736030358979909402780800718157159386076813972158567259200215660948447373041 \\ & G_x = 995203441582195749578291179787384436505546430278305826713579947235728471134 \\ & G_y = 5472060717959818805561601436314318772137091100104008585924551046643952123905 \\ & B_x = 5299619240641551281634865583518297030282874472190772894086521144482721001553 \\ & B_y = 16950150798460657717958625567821834550301663161624707787222815936182638968203 \\ \end{aligned}$

• • 对于运算 $P + Q$，运算如下:

$x_3 = (x_1y_1 + y_1x_2) / (1 + dx_1x_2y_1y_2) \;mod\; p$

$y_3 = (y_1y_2 - ax_1x_2) / (1 - dx_1x_2y_1y_2) \;mod\; p$

点加法

对于椭圆曲线上的两个不同点 $P_1(x_1, y_1)$ 和 $P_2(x_2, y_2)$，其和 $P_3 = P_1 + P_2$ 计算如下：

1. 斜率计算：

   $\lambda = \frac{y_2 - y_1}{x_2 - x_1} \;mod\; p$

2. 新点坐标：

   $\begin{aligned} & x_3 = \lambda^2 - x_1 - x_2 \;mod\; p \\ & y_3 = \lambda(x_1 - x_3) - y_1 \;mod\; p \end{aligned}$

数学推导

1. 直线方程：通过 $P_1(x_1, y_1)$ 和 $P_2(x_2, y_2)$ 的直线：

   $y = \lambda x + c$

   其中 $c = y_1 - \lambda x_1$

2. 求交点：将直线方程代入椭圆曲线 $y^2 = x^3 + ax + b$：

   $(\lambda x + c)^2 = x^3 + ax + b$

   展开得：

   $\lambda^2 x^2 + 2\lambda c x + c^2 = x^3 + ax + b$

   整理为三次方程：

   $x^3 - \lambda^2 x^2 + (a - 2\lambda c)x + (b - c^2) = 0$

3. 根的关系：设三个根为 $x_1, x_2, x_3$，由韦达定理：

   $x_1 + x_2 + x_3 = \lambda^2$

   因此：

   $x_3 = \lambda^2 - x_1 - x_2$

4. y坐标计算：将 $x_3$ 代入直线方程得到交点，然后取其关于x轴的对称点：

   $\begin{aligned} & \quad y_3 = -(\lambda x_3 + c) = -\lambda x_3 - (y_1 - \lambda x_1) \\ & \quad y_3 = \lambda(x_1 - x_3) - y_1 \end{aligned}$

倍乘运算

当 $P_1 = P_2$ 时（$P^{'} = 2 \cdot P = P + P$），进行点倍乘操作：

1. 斜率计算：

   $\lambda = \frac{3x_1^2 + a}{2y_1} \;mod\; p$

2. 新点坐标：

   $\begin{aligned} & x_3 = \lambda^2 - 2x_1 \;mod\; p\\ & y_3 = \lambda(x_1 - x_3) - y_1 \;mod\; p \end{aligned}$

数学推导同上

标量乘法

标量乘法 $k \cdot P$ 是计算点 $P$ 自身相加 $k$ 次的结果。通常使用二进制展开法（类似于快速幂）来高效计算：

输入：点 P，标量 k
输出：k·P

1. 初始化 Q = O (无穷远点)
2. 将 k 表示为二进制
3. 从最低位开始：
   - 如果当前位为1，则 Q = Q + P
   - P = 2P (点倍乘)
   - 移到下一位
4. 返回 Q

ECDH(密钥交换)

密钥生成

私钥生成

私钥 $d$ 是一个随机整数，满足：

$1 \leq d \leq n-1$

公钥生成

公钥 $Q$ 通过标量乘法计算：

$Q = d \cdot G$

密钥交换

Alice 和 Bob 通过以下步骤交换密钥：

1. Alice 生成私钥 $d_A$ 和公钥 $Q_A = d_A \cdot G$，将 $Q_A$ 发送给 Bob。
2. Bob 生成私钥 $d_B$ 和公钥 $Q_B = d_B \cdot G$，将 $Q_B$ 发送给 Alice。
3. Alice 接收到 $Q_B$ 后，计算共享密钥：

   $K_A = d_A \cdot Q_B = d_A \cdot (d_B \cdot G) = (d_A \cdot d_B) \cdot G$

4. Bob 接收到 $Q_A$ 后，计算共享密钥：

   $K_B = d_B \cdot Q_A = d_B \cdot (d_A \cdot G) = (d_B \cdot d_A) \cdot G$

5. 最终得到相同共享密钥 $K = (d_A \cdot d_B) \cdot G$。

ECIES(公钥加密)

密钥生成

私钥生成

私钥 $d$ 是一个随机整数，满足：

$1 \leq d \leq n-1$

公钥生成

公钥 $Q$ 通过标量乘法计算：

$Q = d \cdot G$

加密过程

给定消息 $M$ 和公钥 $Q$，ECIES加密过程如下：

1. 生成随机数 $k$，满足 $1 \leq k \leq n-1$。
2. 计算点 $P = k \cdot G = (x_1, y_1)$。
3. 计算公钥 $K = k \cdot Q = k \cdot d \cdot G$。
4. 生成对称密钥 $K_{sym} = H(K)$，其中 $H$ 是哈希函数。
5. 加密消息 $C = M \oplus K_{sym}$。
6. 输出密文 $(C, P)$。
7. 发送密文 $(C, P)$ 给接收方。

解密过程

给定密文 $(C, P)$ 和私钥 $d$，ECIES解密过程如下：

1. 计算共享密钥 $K = d \cdot P = d \cdot k \cdot G$。
2. 生成对称密钥 $K_{sym} = H(K)$。
3. 解密消息 $M = C \oplus K_{sym}$。
4. 输出明文 $M$。

ECDSA(签名)

域参数

• $p$：有限域的大小
• $a, b$：椭圆曲线参数
• $G$：基点（生成元）
• $n$：基点的阶（即 $n \cdot G = O$）

密钥生成

私钥生成

私钥 $d$ 是一个随机整数，满足：

$1 \leq d \leq n-1$

公钥生成

公钥 $Q$ 通过标量乘法计算：

$Q = d \cdot G$

其中 $G$ 是椭圆曲线的基点。

签名生成

给定消息的哈希值 $h$ 和私钥 $d$，ECDSA签名过程如下：

步骤1：生成随机数

生成一个随机数 $k$，满足：

$1 \leq k \leq n-1$

!!!：这里是简化的，具体参照这里，简单说就是$Hash(h || d)$

步骤2：计算点

计算椭圆曲线点：

$P = k \cdot G = (x_1, y_1)$

步骤3：计算 r

$r = x_1 \; mod \; n$

!!!：取点 $P$ 的 $x$ 坐标模 $n$，作为签名的第一部分。如果 $r = 0$，则重新选择 $k$。

步骤4：计算 s

$s = k^{-1}(h + r \cdot d) \; mod \; n$

!!!：

• $k^{-1}$ 是 $k$ 在模 $n$ 下的乘法逆元
• $(h + r \cdot d)$ 将消息哈希与私钥信息结合
• 整个表达式确保了签名与私钥和消息的绑定关系

如果 $s = 0$，则重新选择 $k$。

步骤5：输出签名

签名为 $(r, s)$。

签名验证

给定消息哈希 $h$、签名 $(r, s)$ 和公钥 $Q$，验证过程如下：

步骤1：参数验证

验证 $r$ 和 $s$ 在有效范围内：

$1 \leq r \leq n-1$

$1 \leq s \leq n-1$

步骤2：计算逆元

计算 $s$ 的乘法逆元：

$w = s^{-1} \; mod \; n$

步骤3：计算标量

$u_1 = h \cdot w \; mod \; n$

$u_2 = r \cdot w \; mod \; n$

步骤4：计算验证点

$P^{'} = u_1 \cdot G + u_2 \cdot Q = ({x_1}^{'}, {y_1}^{'})$

步骤5：验证结果

如果 ${x_1}^{'} \; mod \; n = r$，则签名有效；否则无效。

数学原理

从签名生成有：

$s = k^{-1}(h + r \cdot d) \; mod \; n$

重排得到：

$k = s^{-1}(h + r \cdot d) \; mod \; n \quad (\alpha)$

在验证过程中：

$P^{'} = u_1 \cdot G + u_2 \cdot Q$

替换 $u_1$ 和 $u_2$：

$P^{'} = (h \cdot s^{-1}) \cdot G + (r \cdot s^{-1}) \cdot Q$

由于 $Q = d \cdot G$：

$P^{'} = (h \cdot s^{-1}) \cdot G + (r \cdot s^{-1}) \cdot (d \cdot G)$

$P^{'} = s^{-1}(h + r \cdot d) \cdot G$

根据签名生成中(式$\alpha$)的关系：

$P^{'} = k \cdot G = P$

这证明了验证点 $P^{'}$ 的 $x$ 坐标确实等于 $r$，从而验证了签名的有效性。

Add-On v的生成与公钥恢复

由于压缩传输空间的需要以及ECDSA可以从签名恢复公钥的性质，往往只传输 $(r, s)$ ，而不传输公钥 $Q$ 。

// TODO

进阶：椭圆曲线计算加速

Jacobian坐标

由于椭圆曲线是 $mod \; p$ 的，并且显然在计算 $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$ 时需要在 $\mathbb{F}_p$ 中求逆，故而需要较大的计算量。

在椭圆曲线上，我们定义单位元为无穷远点 $\mathcal{O}$，但是在仿射坐标系 $y^2 = x^3 + ax + c$ 中，而在射影坐标系中，方程可以表示为 $Y^2Z = X^3 + aXZ^2 + cZ^3$，于是，存在如下转换：（别问我是怎么来的，我也不是很明白，都是从py_ecc.secp256k1里看的）

• 仿射 $\rightarrow$ 射影：$(x, y) \rightarrow (X, Y, Z) = (x, y, 1)$
• 射影 $\rightarrow$ 仿射：$(X, Y, Z) \rightarrow (x, y) = (X/Z, Y/Z)$

而对于实际应用中常使用Jacobian坐标，其转换如下：

• 仿射 $\rightarrow$ Jacobian：$(x, y) \rightarrow (X, Y, Z) = (x, y, 1)$
• Jacobian $\rightarrow$ 仿射：$(X, Y, Z) \rightarrow (x, y) = (X/Z^2, Y/Z^3)$

注意这里所有的运算都是在mod p下的

加法

注意这里所有的运算都是在mod p下的

对于 $P(X_1, Y_1, Z_1), Q(X_2, Y_2, Z_2)$，其和 $R = P + Q = (X_3, Y_3, Z_3)$ 计算如下：

$\begin{aligned} & u_1 = X_1 Z_2^2 \\ & u_2 = X_2 Z_1^2 \\ & s_1 = Y_1 Z_2^3 \\ & s_2 = Y_2 Z_1^3 \\ & h = u_2 - u_1 \\ & r = s_2 - s_1 \\ & H^2 = h^2 \\ \\ & X_3 = r^2 - h^3 - 2u_1H^2 \\ & Y_3 = r(u_1H^2 - X_3) - s_1h^3 \\ & Z_3 = hZ_1Z_2 \end{aligned}$

如果 $P = Q$ 直接用倍乘

倍乘

注意这里所有的运算都是在mod p下的

$\begin{aligned} & S = 4X_1Y_1^2 \\ & M = 3X_1^2 + aZ_1^4 \\ \\ & X_3 = M^2 - 2S \\ & Y_3 = M(S - X_3) - 8Y_1^4 \\ & Z_3 = 2Y_1Z_1 \end{aligned}$

(里面的$a$是椭圆曲线的参数)

注意倍乘时可以用类似平方快速幂的方式加速

 

    if a[1] == 0 or n == 0:
        return cast("PlainPoint3D", (0, 0, 1))
    if n == 1:
        return a
    if n < 0 or n >= N:
        return jacobian_multiply(a, n % N)
    if (n % 2) == 0:
        return jacobian_double(jacobian_multiply(a, n // 2))
    if (n % 2) == 1:
        return jacobian_add(jacobian_double(jacobian_multiply(a, n // 2)), a)
    raise ValueError("Unexpected case in jacobian_multiply: This should never happen.")

扩展域

// TODO

Code

ECC_Simple