Faster Point Multiplication with Endomorphisms Optimization

1. Endomorphism 简介
2. 利用 Endomorphisms 加速点的倍乘
3. 参考

1. Endomorphism 简介

2001 年，Robert P. Gallant 等人在论文 Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms 中提出了一种加快椭圆曲线上 Point Multiplication 运算的方法。书籍 Guide to Elliptic Curve Cryptography 第 3.5 节 Curves with efficiently computable endomorphisms 也对这个方法进行了描述。

1.1. Endomorphism 定义

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

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

值得注意的是，自同态映射 $ϕ$ 同时也是一个群同态映射（Group Homorphism），也就是说满足 $ϕ (P_{1} + P_{2}) = ϕ (P_{1}) + ϕ (P_{2}), \forall P_{1}, P_{2} \in E$

1.2. Endomorphism 例子

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

Figure 1: Endomorphism on $y^{2} = x^{3} + b$

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

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

lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

1.3. 验证 Secp256k1 上的 Endomorphism

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

Px = 0x79f823642ddb09f87acae2126775613542af3fe156d1b936a813cc368ff626bd
Py = 0x316b223447295841d0d025b5c76b87b42c6ddf879ec812bcf9eaeb538565a6b2

Px = 0x8effca731d7b8c9a8b3c2c8a00b69912afb4a417387ad1b25d17831aded7d202
Py = 0x22439f0e43813d54eb833d794408d6f436ae5d2237960da81f54536ba15b32fc

我们来验证一下这两个点是否都满足 $λ P = (β x mod 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)

2. 利用 Endomorphisms 加速点的倍乘

式子 $λ P = (β x mod p, y)$ 表明， 椭圆曲线 Secp256k1 上任意点 $P = (x, y)$ 倍乘 $λ$ 的计算将很快： $λ P$ 可转化为一个标量乘法再加个取模运算。

设 $k \in [0, n - 1]$ ，如何利用 Endomorphisms 来加快 $k P$ 的计算呢？思路如下：先把 $k$ 拆分为下面形式 $k = k_{1} + k_{2} λ (\mod n)$ 其中 $k_{1}, k_{2}$ 的比特长度大约为 $k$ 的一半，代入进来有： $k P = k_{1} P + k_{2} \underset{Fast}{\underset{⏟}{λ P}}$

由于 $λ P$ 的计算非常快，而 $k_{1}, k_{2}$ 的比特长度大约为 $k$ 的一半，从而实现了 $k P$ 计算的加速。

至于如何把 $k$ 拆分为 $k = k_{1} + k_{2} λ (\mod n)$ ，可以参考 Guide to Elliptic Curve Cryptography 中的 Algorithm 3.74 Balanced length-two representation of a multiplier.

3. 参考

Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms
Guide to Elliptic Curve Cryptography, 3.5 Curves with efficiently computable endomorphisms
Speeding up signature verification: https://bitcointalk.org/index.php?topic=3238.msg45565#msg45565