Python 中有限域上的椭圆曲线点加法

Question

简而言之，我试图在有限域 Fp 上的椭圆曲线 y^2 = x^3 + ax + b 上添加两个点。我已经在 R 上有一个有效的实现，但不知道如何改变我找到的一般公式，以便它们在 Fp 上维持加法。

当P不等于Q，且Z为P与Q之和时：

        dydx = (Q.y - P.y)/(Q.x - P.x)
        Z.x = dydx**2 - P.x - Q.x
        Z.y = dydx * (Z.x - P.x) + P.y

当P等于Q，再以Z为和：

        dydx = (3 * (P.x)**2 + self.a)/(2 * P.y)
        Z.x = dydx**2 - 2 * P.x
        Z.y = dydx * (Z.x - P.x) + P.y

这些公式与找到的公式相同 here。需要修改什么？

澄清：上面的代码适用于 R 上的椭圆曲线。我正在寻找需要更改的内容，以便它可以在 finite field 阶 p 上添加点。

Answer 1

这里有几个问题。首先是你有错误的公式：那些是求和的求反的公式，或者等效于曲线的第三点，它位于通过 P 和 Q 的线上。与你在维基百科上链接的公式，你会看到你所拥有的 Z.y 是他们所拥有的价值的否定。

第二个问题是你的公式没有考虑原点：如果 P 是群法中 Q 的倒数，那么 P + Q 将是原点，它不在仿射上曲线的一部分，因此不能描述为一对 (x, y) 坐标。所以你需要一些方法来指定原点。

让我们写一些代码。首先，我们需要曲线上点的表示。我们使用字符串 'Origin' 来表示原点，并使用一个简单的命名元组来表示椭圆曲线仿射部分上的点。

# Create a simple Point class to represent the affine points.
from collections import namedtuple
Point = namedtuple("Point", "x y")

# The point at infinity (origin for the group law).
O = 'Origin'

出于演示目的，我们选择特定的椭圆曲线和素数。素数应大于 3 才能使加法公式有效。我们还编写了一个函数，可用于检查特定点是否是曲线上点的有效表示。这将有助于检查我们在执行加法公式时没有犯任何错误。

# Choose a particular curve and prime.  We assume that p > 3.
p = 15733
a = 1
b = 3

def valid(P):
    """
    Determine whether we have a valid representation of a point
    on our curve.  We assume that the x and y coordinates
    are always reduced modulo p, so that we can compare
    two points for equality with a simple ==.
    """
    if P == O:
        return True
    else:
        return (
            (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and
            0 <= P.x < p and 0 <= P.y < p)

要进行除法模 p，您需要一些方法来计算逆模 p。这里一个简单且相当有效的技巧是使用 Python 的 pow 函数的三参数变体：根据费马小定理，pow(a, p-2, p) 将给出 a 的逆函数模 p（当然前提是逆存在——也就是说，a 不能被 p 整除）。

def inv_mod_p(x):
    """
    Compute an inverse for x modulo p, assuming that x
    is not divisible by p.
    """
    if x % p == 0:
        raise ZeroDivisionError("Impossible inverse")
    return pow(x, p-2, p)

最后，这是计算椭圆曲线上的求反和加法的两个函数。加法函数直接基于您给出的公式（在更正 Z.y 的符号后），利用 inv_mod_p 执行除法模 p，并最终减少模 p 用于计算的 x 和 y 坐标。

def ec_inv(P):
    """
    Inverse of the point P on the elliptic curve y^2 = x^3 + ax + b.
    """
    if P == O:
        return P
    return Point(P.x, (-P.y)%p)

def ec_add(P, Q):
    """
    Sum of the points P and Q on the elliptic curve y^2 = x^3 + ax + b.
    """
    if not (valid(P) and valid(Q)):
        raise ValueError("Invalid inputs")

    # Deal with the special cases where either P, Q, or P + Q is
    # the origin.
    if P == O:
        result = Q
    elif Q == O:
        result = P
    elif Q == ec_inv(P):
        result = O
    else:
        # Cases not involving the origin.
        if P == Q:
            dydx = (3 * P.x**2 + a) * inv_mod_p(2 * P.y)
        else:
            dydx = (Q.y - P.y) * inv_mod_p(Q.x - P.x)
        x = (dydx**2 - P.x - Q.x) % p
        y = (dydx * (P.x - x) - P.y) % p
        result = Point(x, y)

    # The above computations *should* have given us another point
    # on the curve.
    assert valid(result)
    return result

我们可以通过在曲线上创建一些点并检查它们是否遵守预期的算术定律来检查上面的代码。

P = Point(6, 15)
Q = Point(8, 1267)
R = Point(2, 3103)
TwoP = ec_add(P, P)
ThreeP = ec_add(TwoP, P)
# Compute 4P two different ways.
assert ec_add(P, ThreeP) == ec_add(TwoP, TwoP)
# Check the associative law.
assert ec_add(P, ec_add(Q, R)) == ec_add(ec_add(P, Q), R)

Answer 2

您可以在 https://github.com/user8547/fast-ecc-python.

查看 secp256k1、secp256r1 和 ed25519 的参考纯 python 实现

Python 中有限域上的椭圆曲线点加法

Elliptic curve point addition over a finite field in Python

python

math

cryptography

elliptic-curve