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

Question

我正在尝试实现一个简单的椭圆曲线加密程序，但我无法获得加倍并添加点

P

直到

12P

的预期输出。曲线方程为

y^2 = x^3 +ax + b mod p

。根据这个网站

3P = [10, 6]

当

P = [5, 1]

时我得到

3p = [10, 5]

。我使用的方程可以在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

如果依次添加点

[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

这可以验证，例如这里。

发布的代码中的问题是确定模逆

gcdExtended(a, b)

的方法仅对正

a

和

b

有效。虽然在

double_point

和

add_points

b

中具有值

prime

(

= 17 > 0

)，但

a

可以取负值。

gcdExtended

通常会返回错误的负值

a

:

• 5 或 -12 的模逆为 7：5 x 7 mod17 = 35 mod17 = 1 和 7 x (-12) mod17 = -84 mod17 = 85 mod17 = 1。

• gcdExtended

  返回以下值：

  gcdExtended(5, 17)[1] = 7

  （为 true）和

  gcdExtended(-12, 17)[1] = -7

  （为 false）。

允许

a

为负值，例如可以定义以下方法，请参见这里：

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

将

gcdExtended

和

gcdExtendedGeneralized

中的

double_point

替换为

add_points

可提供正确的值（请注意，当前实现不考虑无穷远点）。

Answer 2

您在

P

中互换了

Q

和

add_points

。 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 3

您可以使用 LightPHE 构建椭圆曲线

# !pip install lightphe
from lightphe.elliptic_curve_forms.weierstrass import Weierstrass

# construct secp256k1 curve
curve = Weierstrass(curve = "secp256k1")

# base point
G = curve.G

# order of the elliptic curve
n = curve.n

for i in range(0, n):
   P = curve.double_and_add(G, i)
   print(f"{i} x G =  {P}")