logo标签列表

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

pythonmathcryptographyelliptic-curve
8
简而言之，我正在尝试在有限域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

这些公式与此处发现的相同。需要修改什么？
澄清一下：上面的代码适用于R上的椭圆曲线。我想知道为了使其适用于阶数为p的有限域上的点加法，需要进行哪些更改。
你是指在模P下的有限域F中的Fp吗？ - Rob Foley
@rocky 在有限域上的点加法与实数域上的不同，是的，P、Q、Z 是一个具有属性 x、y 的 Point 类。我不知道如何解释这种差异。 - Raylan
你只会将点加倍，还是会添加到不同的点上？一个重要的事情是计算模P的逆元。 - Rob Foley
@RobFoley 两者皆可，代码中需要有区别。我找到了一些相关信息，但是无法得出可行的解决方案。 - Raylan
据我所了解，正如评论链所澄清的那样，他想知道如何将上述点加法应用于模P的有限域。 - Rob Foley
显示剩余7条评论
2个回答
17

这里有几个问题。首先是您使用了错误的公式：那些是求和的否定的公式，或者等效地说，是通过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 的除法，并对计算出的 x 和 y 坐标进行最终的模 p 减法约减。

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)
很抱歉，由于 Android 应用程序将其标记为已读，我错过了您在我的帖子上的评论。您的答案填补了我知识中的所有空白，非常感谢！ - Raylan
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接