椭圆曲线 - 如何处理点乘除法

Question

我正在致力于用 C++ 实现 EC 计算（首先）。一切对我来说都有意义，但点乘法中使用的除法。据我了解，使用整数很常见，但由于结果的近似值，用于加法或加倍的 lambda (https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication) 除法会带来一些不确定性。通常如何处理这个问题，以便每个人都得到相同的结果，尽管在点后使用不同数量的数字？

（不幸的是我找不到openssl返回EC_POINT_add函数的实现来比较他们的解决方案）

Answer 1

我制作了一个小型 Python 库，可以执行所有椭圆点运算，包括乘法和加法。

还使用相同的代码制作了类似的 C++ 库，但用 C++ 重新编写。

虽然你用C++标记了问题，但你的问题仍然更通用，更数学，因此我决定在下面分享两个Python函数，只是为了解释你在真实例子中回答你的问题。将 Python 视为（比 C++）更容易理解的伪代码：

def __add__(self, other):
    A, B, N = self.A, self.B, self.N
    Px, Py, Qx, Qy = self.x, self.y, other.x, other.y
    if Px == Qx and Py == Qy:
        s = ((Px * Px * 3 + A) * pow(Py * 2, -1, N)) % N
    else:
        s = ((Py - Qy) * pow(Px - Qx, -1, N)) % N
    x = (s * s - Px - Qx) % N
    y = (s * (Px - x) - Py) % N
    return ECPoint(A, B, N, x, y)

def __rmul__(self, other):
    assert other >= 1
    if other == 1:
        return self
    other -= 1
    r = self
    while True:
        if other & 1:
            r = r + self
            if other == 1:
                return r
        other >>= 1
        self = self + self

在这里，在点加法中，您可以看到我使用的构造为

pow(a, -1, n)

，它正在寻找a模

n

的

模乘法逆

。

这就是你所谓的除法。您可能知道，您可以通过扩展欧几里得算法找到模逆。

从椭圆曲线点加法的数学中你应该知道，我们有两个地方需要除法，我在下图中用箭头指出了这些地方：

这个除法基本上是数字的模逆运算。例如，在上图中的分母中，我们有

... / (Xq - Xp)

。这意味着我们要寻找这样的

A

A * (Xq - Xp) = 1 (mod N)

，这个

A

被称为

Xq - Xp

模数

N

的模逆（这是取自椭圆曲线方程的模数）。在 python 中，我们只需编写

A = pow(Xq - Xp, -1, N)

- 该函数计算模逆。

所以我们实际上并没有进行任何实际的除法，从浮点算术的意义上来说，这里的除法只是模数意义上的。

如果您有任何疑问，例如您需要更多公式，或者更多解释，或者更多代码，请在评论中告诉。另外，如果您需要 Python 或 C++ 的完整代码、椭圆曲线计算的完整代码，也请告诉我。

Answer 2

答案似乎是模除法或更好的逆元乘法。

Answer 3

在“实现 EC 计算”的范围内，您可能基本上会考虑投影坐标 (X,Y) <--> (XZ,YZ,Z) 中的点运算。这避免了点乘法中连续的昂贵的反转。

参见Nayuki 项目。该链接还引用了 Python 脚本。