如何在python中添加椭圆曲线点？

Question

我正在尝试实现一个简单的椭圆曲线加密程序，但我无法获得加倍和添加点 P 直到 12P 的预期输出。曲线方程是 y^2 = x^3 +ax + b mod p。据此site 3P = [10, 6] when P = [5, 1] while I get 3p = [10, 5]. The equations I use can be found on Wikipedia.

P = [5, 1]
prime = 17
a = 2
b = 2

def gcdExtended(a, b):
     if a == 0:
          return b, 0, 1
     gcd, x1, y1 = gcdExtended(b % a, a)
     x = y1 - (b // a) * x1
     y = x1
     return gcd, x, y

def double_point(point: list):
     x = point[0]
     y = point[1]

     s = ((3*(x**2)+a) * (gcdExtended(2*y, prime)[1])) % prime

     newx = (s**2 - x - x) % prime
     newy = (s * (x - newx) - y) % prime

     return [newx, newy]

def add_points(P: list, Q: list):
     x1 = P[0]
     y1 = P[1]
     x2 = Q[0]
     y2 = Q[1]

     s = ((y2 - y1) * ((gcdExtended(x2-x1, prime))[1] % prime)) % prime

     newx = (s**2 - x1 - x2) % prime
     newy = (s * (x1 - newx) - y1) % prime

     return [newx, newy]

Q = P
index = 2
while True:
     if Q[0] == P[0] and Q[1] == P[1]:
          print("doubling")
          Q = double_point(P)
     else:
          print("adding")
          Q = add_points(Q, P)

     if index == 12 :
          break

     print(f"{index}P = {Q}")
     index += 1

Answer 1

您在 add_points 中互换了 P 和 Q。对 s:

的计算也做了一个小的简化

def add_points(P: list, Q: list):
    x1 = P[0]
    y1 = P[1]
    x2 = Q[0]
    y2 = Q[1]

    #s = ((y2 - y1) * ((gcdExtended(x2-x1, prime))[1] % prime)) % prime
    s = (y2-y1) * (gcdExtended(x2-x1, prime)[1] % prime)

    newx = (s**2 - x1 - x2) % prime
    newy = (s * (x1 - newx) - y1) % prime

    return [newx, newy]

Q = P
index = 2
while True:
    if Q[0] == P[0] and Q[1] == P[1]:
        print("doubling")
        Q = double_point(P)
    else:
        print("adding")
        Q = add_points(P, Q)

    if index == 12 :
        break

    print(f"{index}P = {Q}")
    index += 1

这导致

doubling
2P = [6, 3]
adding
3P = [10, 6]
adding
4P = [3, 1]
adding
5P = [9, 16]
adding
6P = [16, 13]
adding
7P = [0, 6]
adding
8P = [13, 8]
adding
9P = [8, 7]
adding
10P = [8, 10]
adding
11P = [13, 9]
adding

Answer 2

如果点[5,1]依次相加，得到如下序列：

 1P = [ 5,  1]          
 2P = [ 6,  3]
 3P = [10,  6]
 4P = [ 3,  1]
 5P = [ 9, 16]
 6P = [16, 13]
 7P = [ 0,  6]
 8P = [13,  7]
 9P = [ 7,  6]
10P = [ 7, 11]
11P = [13, 10]
12P = [ 0, 11]
13P = [16,  4]
14P = [ 9,  1]
15P = [ 3, 16]
16P = [10, 11]
17P = [ 6, 14]
18P = [ 5, 16]
19P = point at infinity

这可以验证，例如here.

已发布代码中的问题是确定模逆的方法 gcdExtended(a, b) 仅对正数 a 和 b 有效。在 double_point 和 add_points 中，b 的值为 prime (= 17 > 0)，a 可以取负值。

gcdExtended 通常 returns 负数的错误值 a:

5 或 -12 的模逆是 7：5 x 7 mod17 = 35 mod17 = 1 和 7 x (-12) mod17 = -84 mod17 = 85 mod17 = 1。
这些值的 gcdExtended returns：gcdExtended(5, 17)[1] = 7（为真）和 gcdExtended(-12, 17)[1] = -7（为假）。

允许 a 的负值，例如可以定义以下方法，参见here:

def sign(x): 
    return 1 if x >= 0 else -1

def gcdExtendedGeneralized(a, b):
    gcd, x1, y1 = gcdExtended(abs(a), b)
    return gcd, (sign(a) * x1) % b, y1 % b

在 double_point 和 add_points 中用 gcdExtendedGeneralized 替换 gcdExtended 提供了正确的值（请注意，当前的实现不考虑无穷远点）。

如何在python中添加椭圆曲线点？

How to add elliptic curve points in python?

python

encryption

cryptography

elliptic-curve