| 0,0 → 1,112 |
|---|
| |
| def Extended_Euclidian(a, b): |
| ''' Takes values a and b and returns a tuple (r,s,t) in the following format: |
| r = s * a + t * b where r is the GCD and s and t are the inverses of a and b''' |
| t_ = 0 |
| t = 1 |
| s_ = 1 |
| s = 0 |
| q = int(a/b) |
| r = a - q * b |
| # print("%d\t= %d * %d + %d" % (a, q, b, r)) |
| while r > 0: |
| temp = t_ - q * t |
| t_ = t |
| t = temp |
| temp = s_ - q * s |
| s_ = s |
| s = temp |
| a = b |
| b = r |
| q = int(a/b) |
| r = a - q * b |
| # print("%d\t= %d * %d + %d" % (a, q, b, r)) |
| r = b |
| return (r, s, t) |
| |
| def GCD(q,N): |
| '''Returns the multiplicative inverse of a and b''' |
| ret = Extended_Euclidian(q,N) |
| return ret[0] |
| |
| def Inverse(a, b): |
| '''Returns the multiplicative inverse of a mod b''' |
| if (a < 0): |
| a = a + b |
| ret = Extended_Euclidian(a,b) |
| if (ret[1] < 0): |
| inv = ret[1] + b |
| else: |
| inv = ret[1] |
| return inv |
| |
| def Elliptic_Curve_Add(p, a, b, point_1, point_2): |
| '''Adds two points on an Elliptical Curve and returns the result''' |
| # Adding a point at infinity results in the same point |
| if point_1[0] == 'x' and point_1[1] == 'x': |
| return point_2 |
| if point_2[0] == 'x' and point_2[1] == 'x': |
| return point_1 |
| |
| # Test to make sure both points are on the curve |
| z = (point_1[0]**3 + a*point_1[0] + b) % p |
| if z**((p-1)//2)%p != 1: |
| print("Point", point_1, "is not on the elliptic curve!") |
| return |
| z = (point_2[0]**3 + a*point_2[0] + b) % p |
| if z**((p-1)//2)%p != 1: |
| print("Point", point_2, "is not on the elliptic curve!") |
| return |
| |
| # If x_1 == x_2 and y_1 != y_2, return point at infinity |
| if point_1[0] == point_2[0] and point_1[1] != point_2[1]: |
| return ('x','x') |
| |
| # If point_1 == point_2, slope = (3 x_1^2 + a)(2 y_1)^-1 |
| if point_1[0] == point_2[0] and point_1[1] == point_2[1]: |
| inv = Inverse(2*point_1[1], p) |
| slope = ((3 * point_1[0]**2 + a) * inv) % p |
| else: # Otherwise point_1 != point_2, slope = (y_2 - y_1)(x_2 - x_1)^-1 |
| inv = Inverse(point_2[0] - point_1[0], p) |
| slope = ((point_2[1] - point_1[1]) * inv) % p |
| |
| # Calculate the third point given the slope |
| x_3 = (slope**2 - point_1[0] - point_2[0]) % p |
| y_3 = (slope * (point_1[0] - x_3) - point_1[1]) % p |
| return (x_3,y_3) |
| |
| def Elliptic_Curve_Multiple(p, a, b, point, multiple): |
| '''Returns a multiple of a point on an Elliptical Curve''' |
| ret = point |
| for i in range(multiple-1): |
| ret = Elliptic_Curve_Add(p, a, b, ret, point) |
| print(i+2,":",ret) |
| return ret |
| |
| if __name__ == '__main__': |
| # print("For the following tests, the curve y^2 = x^3 + x + 6 is used") |
| # print("\nResult when point is not on the curve (quadratic residue failed):") |
| # print(Elliptic_Curve_Add(11, 1, 6, (1,2), (2,7))) |
| |
| # print("\nResult when one or both points being the point at infinity:") |
| # print(Elliptic_Curve_Add(11, 1, 6, ('x','x'), (2,7))) |
| # print(Elliptic_Curve_Add(11, 1, 6, (2,7), ('x','x'))) |
| # print(Elliptic_Curve_Add(11, 1, 6, ('x','x'), ('x','x'))) |
| |
| # print("\nResult when adding two distinct points:") |
| # print(Elliptic_Curve_Add(11, 1, 6, (2,7), (7,9))) |
| |
| # print("\nResult when adding a point to itself:") |
| # print(Elliptic_Curve_Add(11, 1, 6, (2,7), (2,7))) |
| |
| # print("\nResult when computing multiples of a point:") |
| # Elliptic_Curve_Multiple(11, 1, 6, (2,7), 3) |
| |
| # print("\nFor the following tests, the curve y^2 = x^3 + 5x + 4 is used") |
| # print("\nAttempting to add point (220,407) to itself:") |
| # print(Elliptic_Curve_Add(997, 5, 4, (220,407), (220,407))) |
| |
| # print("\nResult of 267(220,407):") |
| # Elliptic_Curve_Multiple(997, 5, 4, (220,407), 267) |
| |
| Elliptic_Curve_Multiple(71,1,28,(1,32),10) |