ECC

数学基础

椭圆曲线

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

常见曲线参数:

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

  $\begin{array}{rl}& 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{array}$

• 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{array}{rl}& p=FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF\\ & a=FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC\\ & b=28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93\\ & n=FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123\\ & G_x=32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7\\ & G_y=BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0\end{array}$

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

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

一些特殊曲线

• Baby Jubjub Elliptic Curve（扭曲爱德华曲线方程）：$a{x}^2+y^2=1+d{x}^2{y}^2$

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

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

$$x_3=(x_1{y}_1+y_1{x}_2)/(1+d{x}_1{x}_2{y}_1{y}_2)modp$$$$y_3=(y_1{y}_2-a{x}_1{x}_2)/(1-d{x}_1{x}_2{y}_1{y}_2)modp$$

点加法

对于椭圆曲线上的两个不同点 $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}modp$$

2. 新点坐标：

   $\begin{array}{rl}& x_3={\lambda }^2-x_1-x_{2}modp\\ & y_3=\lambda (x_1-x_3)-y_{1}modp\end{array}$

数学推导

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 cx+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{array}{rl}& y_3=-(\lambda x_3+c)=-\lambda x_3-(y_1-\lambda x_1)\\ & y_3=\lambda (x_1-x_3)-y_1\end{array}$

倍乘运算

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

1. 斜率计算：

   $$\lambda =\frac{3x_1^2+a}{2y_1}modp$$

2. 新点坐标：

   $\begin{array}{rl}& x_3={\lambda }^2-2x_{1}modp\\ & y_3=\lambda (x_1-x_3)-y_{1}modp\end{array}$

数学推导同上

标量乘法

标量乘法 $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\le d\le 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\le d\le n-1$$

公钥生成

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

$$Q=d\cdot G$$

加密过程

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

1. 生成随机数 $k$，满足 $1\le k\le 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\le d\le n-1$$

公钥生成

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

$$Q=d\cdot G$$

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

签名生成

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

步骤1：生成随机数

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

$$1\le k\le n-1$$

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

步骤2：计算点

计算椭圆曲线点：

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

步骤3：计算 r

$$r=x_{1}modn$$

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

步骤4：计算 s

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

!!!：

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

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

步骤5：输出签名

签名为 $(r,s)$。

签名验证

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

步骤1：参数验证

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

$$1\le r\le n-1$$$$1\le s\le n-1$$

步骤2：计算逆元

计算 $s$ 的乘法逆元：

$$w=s^{-1}modn$$

步骤3：计算标量

$$u_1=h\cdot wmodn$$$$u_2=r\cdot wmodn$$

步骤4：计算验证点

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

步骤5：验证结果

如果 ${x_1}^{{}^{\prime }}modn=r$，则签名有效；否则无效。

数学原理

从签名生成有：

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

重排得到：

$$k=s^{-1}(h+r\cdot d)modn(\alpha )$$

在验证过程中：

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

替换 $u_1$ 和 $u_2$：

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

由于 $Q=d\cdot G$：

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

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

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

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

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

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

// TODO

进阶：椭圆曲线计算加速

Jacobian坐标

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

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

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

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

• 仿射 $\to$ Jacobian：$(x,y)\to (X,Y,Z)=(x,y,1)$
• Jacobian $\to$ 仿射：$(X,Y,Z)\to (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{array}{rl}& 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_1{H}^2\\ & Y_3=r(u_1{H}^2-X_3)-s_1{h}^3\\ & Z_3=h{Z}_1{Z}_2\end{array}$

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

倍乘

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

$\begin{array}{rl}& S=4X_1{Y}_1^2\\ & M=3X_1^2+a{Z}_1^4\\ \\ & X_3=M^2-2S\\ & Y_3=M(S-X_3)-8Y_1^4\\ & Z_3=2Y_1{Z}_1\end{array}$

(里面的$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