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

这些都是一样的formules为找到这里.需要修改什么？

澄清:上面的代码适用于R上的椭圆曲线.我希望找到需要更改的内容,以便在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函数的三参数变量:通过Fermat的Little Theorem,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)