Subversion Repositories Code-Repo

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)