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

进阶：椭圆曲线计算加速

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