在Python中的有限字段上添加椭圆曲线点 [英] Elliptic curve point addition over a finite field in Python

问题描述

简而言之，我试图在有限域Fp上的椭圆曲线y ^ 2 = x ^ 3 + ax + b上添加两个点.我已经在R上有一个可行的实现，但是不知道如何更改Ive所找到的通用公式，以使它们能够维持Fp之上的加法运算.

In short, Im trying to add two points on an elliptic curve y^2 = x^3 + ax + b over a finite field Fp. I already have a working implementation over R, but do not know how to alter the general formulas Ive found in order for them to sustain addition over Fp.

当P不等于Q，并且Z是P和Q之和:

When P does not equal Q, and Z is the sum of P and 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作为总和:

When P equals Q, again with Z as the sum:

        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

这些是与此处所用的相同公式.需要修改什么?

These are the same formules as found here. What needs to be modified?

澄清:上面的代码适用于R上的椭圆曲线.我正在寻找需要进行哪些更改才能使其在

Clarification: The code above works for elliptic curves over R. I am looking to find what needs to be changed for it to work for addition of points over a finite field of order p.

推荐答案

这里有两个问题.首先是您使用了错误的公式:这些是求和的求反的公式，或者等价于通过P和Q的直线上的曲线的第三点.请与您比较的公式进行比较链接到Wikipedia上，您会发现Z.y的值是对它们的值的否定.

There are a couple of issues here. First is that you have the wrong formulas: those are the formulas for the negation of the sum, or equivalently the third point of the curve that lies on the line through P and Q. Compare with the formula you linked to on Wikipedia, and you'll see that what you have for Z.y is the negation of the value they have.

第二个问题是您的公式未考虑原点:如果P是群律中Q的倒数，则P + Q将是原点，它不位于等式的仿射部分曲线，因此不能描述为一对(x, y)坐标.因此，您将需要某种方式来指定原点.

A second issue is that your formulas don't take the origin into account: if P is the inverse of Q in the group law, then P + Q will be the origin, which doesn't lie on the affine part of the curve and so can't be described as a pair of (x, y) coordinates. So you'll need some way to specify the origin.

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

Let's write some code. First we need a representation for the points on the curve. We use the string 'Origin' to represent the origin, and a simple named tuple for the points on the affine part of the elliptic curve.

# 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才能使加法公式有效.我们还编写了一个函数，可用于检查特定点是否是曲线上某个点的有效表示.这将有助于检查我们在实现加法公式时没有犯任何错误.

For demonstration purposes, we choose a particular elliptic curve and prime. The prime should be greater than 3 for the addition formulas to be valid. We also write a function that we can use to check that a particular point is a valid representation of a point on the curve. This will be useful in checking that we didn't make any mistakes in implementing the addition formulas.

# 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定理，pow(a, p-2, p)将给出a取模p的逆(当然，前提是该逆存在) -即a不能被p整除).

To do divisions modulo p you'll need some way to compute inverses modulo p. A simple and reasonably efficient trick here is to use Python's three-argument variant of the pow function: by Fermat's Little Theorem, pow(a, p-2, p) will give an inverse of a modulo p (provided of course that that inverse exists - that is, that a is not divisible by 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的除法，并对计算出的x和y坐标.

And finally, here are the two functions to compute negation and addition on the elliptic curve. The addition function is based directly on the formulas you gave (after correcting the sign of Z.y), makes use of inv_mod_p to perform the divisions modulo p, and does a final reduction modulo p for the computed x and y coordinates.

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

我们可以通过在曲线上创建几个点并检查它们是否符合预期的算术定律来检查上面的代码.

We can check the code above by creating a handful of points on the curve and checking that they obey the expected arithmetic laws.

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)

这篇关于在Python中的有限字段上添加椭圆曲线点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！