ecc.py

class Point:    def __init__(self, x, y, a, b):        self.a = a        self.b = b        self.x = x        self.y = y        if self.x is None and self.y is None:            return        if self.y**2 != self.x**3 + a * x + b:            raise ValueError('({}, {}) is not on the curve'.format(x, y))    # end::source1[]    def __eq__(self, other):        return self.x == other.x and self.y == other.y \            and self.a == other.a and self.b == other.b    def __ne__(self, other):        # this should be the inverse of the == operator        return not (self == other)    def __repr__(self):        if self.x is None:            return 'Point(infinity)'        elif isinstance(self.x, FieldElement):            return 'Point({},{})_{}_{} FieldElement({})'.format(                self.x.num, self.y.num, self.a.num, self.b.num, self.x.prime)        else:            return 'Point({},{})_{}_{}'.format(self.x, self.y, self.a, self.b)    def __add__(self, other):        if self.a != other.a or self.b != other.b:            raise TypeError('Points {}, {} are not on the same curve'.format(self, other))        # Case 0.0: self is the point at infinity, return other        if self.x is None:            return other        # Case 0.1: other is the point at infinity, return self        if other.x is None:            return self        # Case 1: self.x == other.x, self.y != other.y        # Result is point at infinity        if self.x == other.x and self.y != other.y:            return self.__class__(None, None, self.a, self.b)        # Case 2: self.x ≠ other.x        # Formula (x3,y3)==(x1,y1)+(x2,y2)        # s=(y2-y1)/(x2-x1)        # x3=s**2-x1-x2        # y3=s*(x1-x3)-y1        if self.x != other.x:            s = (other.y - self.y) / (other.x - self.x)            x = s**2 - self.x - other.x            y = s * (self.x - x) - self.y            return self.__class__(x, y, self.a, self.b)        # Case 4: if we are tangent to the vertical line,        # we return the point at infinity        # note instead of figuring out what 0 is for each type        # we just use 0 * self.x        if self == other and self.y == 0 * self.x:            return self.__class__(None, None, self.a, self.b)        # Case 3: self == other        # Formula (x3,y3)=(x1,y1)+(x1,y1)        # s=(3*x1**2+a)/(2*y1)        # x3=s**2-2*x1        # y3=s*(x1-x3)-y1        if self == other:            s = (3 * self.x**2 + self.a) / (2 * self.y)            x = s**2 - 2 * self.x            y = s * (self.x - x) - self.y            return self.__class__(x, y, self.a, self.b)    # tag::source3[]    def __rmul__(self, coefficient):        coef = coefficient        current = self  # <1>        result = self.__class__(None, None, self.a, self.b)  # <2>        while coef:            if coef & 1:  # <3>                result += current            current += current  # <4>            coef >>= 1  # <5>        return result    # end::source3[]class PointTest(TestCase):    def test_ne(self):        a = Point(x=3, y=-7, a=5, b=7)        b = Point(x=18, y=77, a=5, b=7)        self.assertTrue(a != b)        self.assertFalse(a != a)    def test_on_curve(self):        with self.assertRaises(ValueError):            Point(x=-2, y=4, a=5, b=7)        # these should not raise an error        Point(x=3, y=-7, a=5, b=7)        Point(x=18, y=77, a=5, b=7)    def test_add0(self):        a = Point(x=None, y=None, a=5, b=7)        b = Point(x=2, y=5, a=5, b=7)        c = Point(x=2, y=-5, a=5, b=7)        self.assertEqual(a + b, b)        self.assertEqual(b + a, b)        self.assertEqual(b + c, a)    def test_add1(self):        a = Point(x=3, y=7, a=5, b=7)        b = Point(x=-1, y=-1, a=5, b=7)        self.assertEqual(a + b, Point(x=2, y=-5, a=5, b=7))    def test_add2(self):        a = Point(x=-1, y=1, a=5, b=7)        self.assertEqual(a + a, Point(x=18, y=-77, a=5, b=7))# tag::source2[]class ECCTest(TestCase):    def test_on_curve(self):        prime = 223        a = FieldElement(0, prime)        b = FieldElement(7, prime)        valid_points = ((192, 105), (17, 56), (1, 193))        invalid_points = ((200, 119), (42, 99))        for x_raw, y_raw in valid_points:            x = FieldElement(x_raw, prime)            y = FieldElement(y_raw, prime)            Point(x, y, a, b)  # <1>        for x_raw, y_raw in invalid_points:            x = FieldElement(x_raw, prime)            y = FieldElement(y_raw, prime)            with self.assertRaises(ValueError):                Point(x, y, a, b)  # <1>    # end::source2[]    def test_add(self):        # tests the following additions on curve y^2=x^3-7 over F_223:        # (192,105) + (17,56)        # (47,71) + (117,141)        # (143,98) + (76,66)        prime = 223        a = FieldElement(0, prime)        b = FieldElement(7, prime)        additions = (            # (x1, y1, x2, y2, x3, y3)            (192, 105, 17, 56, 170, 142),            (47, 71, 117, 141, 60, 139),            (143, 98, 76, 66, 47, 71),        )        # loop over additions        # initialize x's and y's as FieldElements        # create p1, p2 and p3 as Points        # check p1+p2==p3        for x1,y1,x2,y2,x3,y3 in additions:            p1=Point(FieldElement(x1, prime), FieldElement(y1, prime), a, b)            p2=Point(FieldElement(x2, prime), FieldElement(y2, prime), a, b)            p3=Point(FieldElement(x3, prime), FieldElement(y3, prime), a, b)            self.assertEqual(p1+p2, p3)    def test_rmul(self):        # tests the following scalar multiplications        # 2*(192,105)        # 2*(143,98)        # 2*(47,71)        # 4*(47,71)        # 8*(47,71)        # 21*(47,71)        prime = 223        a = FieldElement(0, prime)        b = FieldElement(7, prime)        multiplications = (            # (coefficient, x1, y1, x2, y2)            (2, 192, 105, 49, 71),            (2, 143, 98, 64, 168),            (2, 47, 71, 36, 111),            (4, 47, 71, 194, 51),            (8, 47, 71, 116, 55),            (21, 47, 71, None, None),        )        # iterate over the multiplications        for s, x1_raw, y1_raw, x2_raw, y2_raw in multiplications:            x1 = FieldElement(x1_raw, prime)            y1 = FieldElement(y1_raw, prime)            p1 = Point(x1, y1, a, b)            # initialize the second point based on whether it's the point at infinity            if x2_raw is None:                p2 = Point(None, None, a, b)            else:                x2 = FieldElement(x2_raw, prime)                y2 = FieldElement(y2_raw, prime)                p2 = Point(x2, y2, a, b)            # check that the product is equal to the expected point            self.assertEqual(s * p1, p2)# tag::source6[]A = 0B = 7# end::source6[]# tag::source4[]P = 2**256 - 2**32 - 977# end::source4[]# tag::source9[]N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141# end::source9[]# tag::source5[]class S256Field(FieldElement):    def __init__(self, num, prime=None):        super().__init__(num=num, prime=P)    def __repr__(self):        return '{:x}'.format(self.num).zfill(64)# end::source5[]# tag::source7[]class S256Point(Point):    def __init__(self, x, y, a=None, b=None):        a, b = S256Field(A), S256Field(B)        if type(x) == int:            super().__init__(x=S256Field(x), y=S256Field(y), a=a, b=b)        else:            super().__init__(x=x, y=y, a=a, b=b)  # <1>    # end::source7[]    def __repr__(self):        if self.x is None:            return 'S256Point(infinity)'        else:            return 'S256Point({}, {})'.format(self.x, self.y)    # tag::source8[]    def __rmul__(self, coefficient):        coef = coefficient % N  # <1>        return super().__rmul__(coef)    # end::source8[]    # tag::source12[]    def verify(self, z, sig):        s_inv = pow(sig.s, N - 2, N)  # <1> 1/s        u = z * s_inv % N  # <2>        v = sig.r * s_inv % N  # <3>        total = u * G + v * self  # <4>        return total.x.num == sig.r  # <5>    # end::source12[]# tag::source10[]G = S256Point(    0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,    0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)# end::source10[]class S256Test(TestCase):    def test_order(self):        point = N * G        self.assertIsNone(point.x)    def test_pubpoint(self):        # write a test that tests the public point for the following        points = (            # secret, x, y            (7, 0x5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc, 0x6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da),            (1485, 0xc982196a7466fbbbb0e27a940b6af926c1a74d5ad07128c82824a11b5398afda, 0x7a91f9eae64438afb9ce6448a1c133db2d8fb9254e4546b6f001637d50901f55),            (2**128, 0x8f68b9d2f63b5f339239c1ad981f162ee88c5678723ea3351b7b444c9ec4c0da, 0x662a9f2dba063986de1d90c2b6be215dbbea2cfe95510bfdf23cbf79501fff82),            (2**240 + 2**31, 0x9577ff57c8234558f293df502ca4f09cbc65a6572c842b39b366f21717945116, 0x10b49c67fa9365ad7b90dab070be339a1daf9052373ec30ffae4f72d5e66d053),        )        # iterate over points        for secret, x, y in points:            # initialize the secp256k1 point (S256Point)            point = S256Point(x, y)            # check that the secret*G is the same as the point            self.assertEqual(secret * G, point)    def test_verify(self):        point = S256Point(            0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c,            0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34)        z = 0xec208baa0fc1c19f708a9ca96fdeff3ac3f230bb4a7ba4aede4942ad003c0f60        r = 0xac8d1c87e51d0d441be8b3dd5b05c8795b48875dffe00b7ffcfac23010d3a395        s = 0x68342ceff8935ededd102dd876ffd6ba72d6a427a3edb13d26eb0781cb423c4        self.assertTrue(point.verify(z, Signature(r, s)))        z = 0x7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d        r = 0xeff69ef2b1bd93a66ed5219add4fb51e11a840f404876325a1e8ffe0529a2c        s = 0xc7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fddbdce6feab6        self.assertTrue(point.verify(z, Signature(r, s)))# tag::source11[]class Signature:    def __init__(self, r, s):        self.r = r        self.s = s    def __repr__(self):        return 'Signature({:x},{:x})'.format(self.r, self.s)# end::source11[]# tag::source13[]class PrivateKey:    def __init__(self, secret):        self.secret = secret        self.point = secret * G  # <1>    def hex(self):        return '{:x}'.format(self.secret).zfill(64)    # end::source13[]    # tag::source14[]    def sign(self, z):        k = self.deterministic_k(z)  # <1>        r = (k * G).x.num        k_inv = pow(k, N - 2, N)        s = (z + r * self.secret) * k_inv % N        if s > N / 2:            s = N - s        return Signature(r, s)    def deterministic_k(self, z):        k = b'\x00' * 32        v = b'\x01' * 32        if z > N:            z -= N        z_bytes = z.to_bytes(32, 'big')        secret_bytes = self.secret.to_bytes(32, 'big')        s256 = hashlib.sha256        k = hmac.new(k, v + b'\x00' + secret_bytes + z_bytes, s256).digest()        v = hmac.new(k, v, s256).digest()        k = hmac.new(k, v + b'\x01' + secret_bytes + z_bytes, s256).digest()        v = hmac.new(k, v, s256).digest()        while True:            v = hmac.new(k, v, s256).digest()            candidate = int.from_bytes(v, 'big')            if candidate >= 1 and candidate < N:                return candidate  # <2>            k = hmac.new(k, v + b'\x00', s256).digest()            v = hmac.new(k, v, s256).digest()    # end::source14[]class PrivateKeyTest(TestCase):    def test_sign(self):        pk = PrivateKey(randint(0, N))        z = randint(0, 2**256)        sig = pk.sign(z)        self.assertTrue(pk.point.verify(z, sig))