Faster Point Multiplication with Endomorphisms Optimization

设 \(E\) 是定义在域（Field） \(K\) 上的椭圆曲线，用 \(E\) 表示该椭圆曲线上的所有点的集合，则 \(E\) 上的自同态（Endomorphism）映射是满足 \[\phi(\mathcal{O}) = \mathcal{O}, \phi(P) = (g(P), h(P)), \forall P \in E\] 的映射 \(\phi: E \rightarrow E\) ，其中 \(g\) 和 \(h\) 是系数位于 \(K\) 的有理函数。

如果 \(\phi_1\) 和 \(\phi_2\) 是自同态映射，则定义两者的和 \(\phi_1+\phi_2\) 为 \((\phi_1+\phi_2)(P) = \phi_1(P) + \phi_2(P)\) 。定义两者的乘积 \(\phi_1\phi_2\) 为 \((\phi_1\phi_2)(P)=\phi_1(\phi_2(P))\) 。在这样的加法和乘法的定义下， \(E\) 上的所有的自同态映射构成一个环（Ring），称为域 \(K\) 上 \(E\) 的自同态环（Endomorphism Ring of \(E\) over \(K\) ）。

值得注意的是，自同态映射 \(\phi\) 同时也是一个群同态映射（Group Homorphism），也就是说满足 \[\phi(P_1 + P_2) = \phi(P_1) + \phi(P_2), \forall P_1, P_2 \in E\]

在 Guide to Elliptic Curve Cryptography 的 Example 3.71 中给出了几个自同态（Endomorphism）映射的例子，图 1 是其中有一个例子。

也就是说：如果椭圆曲线 \(y^2 = x^3 + b\) 的参数满足 \(p \equiv 1 \pmod 3\) ，那么一定存在两个数 \(\lambda, \beta\) 使椭圆曲线上任意点 \(P=(x,y)\) 满足： \[\lambda P = (\beta x \bmod p, y)\] 椭圆曲线 Secp256k1（ \(y^2 = x^3 + 7\) ）的参数 \[p=\texttt{0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f}\] 它恰好满足条件 \(p \equiv 1 \pmod 3\) ，所以存在 \(\lambda, \beta\) 使得 Secp256k1 上的任意点都满足上面等式。

这里不介绍如何具体求解 Secp256k1 中的 \(\lambda, \beta\) ，直接给出结论（来源于：https://bitcointalk.org/index.php?topic=3238.msg45565#msg45565 ）：

lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

在椭圆曲线 Secp256k1 上任意找两个点，如：

Px = 0x79f823642ddb09f87acae2126775613542af3fe156d1b936a813cc368ff626bd
Py = 0x316b223447295841d0d025b5c76b87b42c6ddf879ec812bcf9eaeb538565a6b2

Px = 0x8effca731d7b8c9a8b3c2c8a00b69912afb4a417387ad1b25d17831aded7d202
Py = 0x22439f0e43813d54eb833d794408d6f436ae5d2237960da81f54536ba15b32fc

我们来验证一下这两个点是否都满足 \[\lambda P = (\beta x \bmod p, y)\] 下面给出一个验证程序：

import ecdsa
from ecdsa.ellipticcurve import PointJacobi

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F  # secp256k1


def satisfy_endomorphism(x, y):
    """ Verify any curve point P = (x,y) satisfy:
        lambda * P = (beta * x mod p, y)
    """
    lamb = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
    beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

    q: PointJacobi = PointJacobi(ecdsa.curves.SECP256k1.curve,
                                 x,
                                 y,
                                 1,
                                 ecdsa.curves.SECP256k1.order)

    left: PointJacobi = lamb * q
    left_x = left.x()
    left_y = left.y()

    right_x = beta * x % p
    right_y = y

    print('left_x', left_x.to_bytes(32, byteorder='big').hex())
    print('left_y', left_y.to_bytes(32, byteorder='big').hex())
    print('right_x', right_x.to_bytes(32, byteorder='big').hex())
    print('right_y', right_y.to_bytes(32, byteorder='big').hex())

    return left_x == right_x and left_y == right_y


def is_on_curve_secp256k1(x, y):
    return y**2 % p - (x**3 + 7) % p == 0


Px = 0x79f823642ddb09f87acae2126775613542af3fe156d1b936a813cc368ff626bd
Py = 0x316b223447295841d0d025b5c76b87b42c6ddf879ec812bcf9eaeb538565a6b2
assert is_on_curve_secp256k1(Px, Py)
assert satisfy_endomorphism(Px, Py)

Px = 0x8effca731d7b8c9a8b3c2c8a00b69912afb4a417387ad1b25d17831aded7d202
Py = 0x22439f0e43813d54eb833d794408d6f436ae5d2237960da81f54536ba15b32fc
assert is_on_curve_secp256k1(Px, Py)
assert satisfy_endomorphism(Px, Py)