priv-key to pub-key on the Bitcoin elliptic curve

priv_to_pub.py

"""
Bitcoin elliptic curve pub-key from priv-key in raw python, as dicusssed in the video

https://youtu.be/RZzB-vPFYmo

This is a follow-up to the previous video
https://youtu.be/LYN3h5DjeXw

This script is directly based off
https://github.com/peterscott78/offline_signer/blob/master/ecdsa_keys.py

See also
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
I'll keep this short, so for other peoples videos on elliptic curve's, see
https://www.youtube.com/results?search_query=Secp256k1

For the curve tested, see
https://en.bitcoin.it/wiki/Secp256k1

Don't write me emails asking how to install python or something of the sort. 
If you ask me something, use an adult sentence structure and attire.
Disclaimer: Due to potential bugs, don't use functions from this script for anything of value!
Don't use this script for anything of value - I've tinkered around
with it a lot and it might be buggy in various places.
Instead, e.g. use the 'ecdsa' python python library that I also use for some
validation checks here at the end of this script.
"""


def inverse_mod(a, m):
    """
    Returns and x with (a * x) % m == 1
    See
    https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
    """
    if a < 0 or m <= a:
        a = a % m
    c, d = a, m
    uc, vc, ud, vd = 1, 0, 0, 1
    while c:
        q, c, d = divmod(d, c) + (c, )
        uc, vc, ud, vd = ud - q * uc, vd - q * vc, uc, vc
    assert d == 1
    x = ud if ud > 0 else ud + m
    assert (a * x) % m == 1
    return x


class Point(object):
    def __init__(self, curve, x, y, order):
        """
        The parameter curve is a dict with keys 'a', 'b' and 'p' capturing
        y^3 == x^2 + a * x + b over F_p.
        See also the sanity checks below.
        """
        self.__curve = curve
        self.__x = x
        self.__y = y
        self.order = order

        # Sanity checks
        if order:
            assert self.scalar_mult(order) == _INFINITY

        if self.__curve:
            # Validate that the point (x, y) is on the curve
            y2 = y * y
            x3 = x * x * x
            ax = curve['a'] * x
            d = y2 - (x3 + ax + curve['b'])
            assert d % curve['p'] == 0

    def get_coords(self):
        return self.__x, self.__y

    def scalar_mult(self, e):
        """
        From the 'eliptic curve mutliplication Wikipedia page',
        "Elliptic curve scalar multiplication is the operation of successively
        adding a point along an elliptic curve to itself repeatedly"
        """
        if self.order:
            e = e % self.order
        if e == 0 or self == _INFINITY:
            return _INFINITY
        assert e > 0

        e3 = 3 * e
        # Compute leftmost bit index
        j = 1
        while j <= e3:
            j *= 2
        i = j // 4

        # Do the math
        point = self
        while i > 1:
            point = point.__double()
            u = e & i  # Note: Using bitwise and on the binary expressions of those numbers
            u3 = e3 & i
            if u3 and not u:
                point = point.__add(self)
            if u and not u3:
                self_y_flipped = Point(self.__curve, self.__x, -self.__y, self.order)
                point = point.__add(self_y_flipped)
            i = i // 2

        return point

    def __add(self, other):
        """
        For a visual motivation of addition, see e.g. the graphs on
        the 'eliptic curve mutliplication Wikipedia page'.
        """
        # Simple cases
        if other == _INFINITY:
            return self
        if self == _INFINITY:
            return other
        assert self.__curve == other.__curve

        # Auxiliary abbreviations
        x = self.__x
        ox = other.__x
        y = self.__y
        oy = other.__y

        # Another simple case
        if x == ox:
            return _INFINITY if (y + oy) % self.__curve['p'] == 0 else self.__double()

        # Do the math
        p = self.__curve['p']
        im = inverse_mod(ox - x, p)
        l = ((oy - y) * im) % p
        x3 = (l * l - x - ox) % p
        y3 = (l * (x - x3) - y) % p

        return Point(self.__curve, x3, y3, None)

    def __double(self):
        if self == _INFINITY:
            return _INFINITY
        # Auxiliary abbreviations
        p = self.__curve['p']
        x = self.__x
        y = self.__y

        # Do the math
        im = inverse_mod(2 * y, p)
        l = (3 * x * x + self.__curve['a']) * im
        l = l % p
        x3 = l * l - 2 * x
        x3 = x3 % p
        y3 = l * (x - x3) - y
        y3 = y3 % p

        return Point(self.__curve, x3, y3, None)


_INFINITY = Point(None, None, None, None)


if __name__ == "__main__":
    """
    Validate custom eliptic curve point implementation
    using the Bitcoin curve and base point (Secp256k1)
    by using the ecdsa python library.
    """

    BTC_CURVE = dict(a=0, b=7, p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)  # a, b, modulus 
    Secp256k1 = Point(
        BTC_CURVE,
        0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,  # x_G
        0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,  # y_G
        0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # order
    )

    def is_matching_keys(secret, public_point_coords):
        import ecdsa
        import binascii
        sk = ecdsa.SigningKey.from_secret_exponent(secret, curve=ecdsa.SECP256k1) # Uses Secp256k1!
        pubk = binascii.b2a_hex(sk.verifying_key.to_string()).decode('ascii')

        # Convert 'public_point_coords' to the same format
        def cast_to_hex(coordinate):
            LEN = 64  # 2**6 hex chars
            hex_string = hex(coordinate)[2:]  # convert to hex but drop "0x"
            prefix_zeros = "0" * (LEN - len(hex_string))
            return prefix_zeros + hex_string

        pubk_x, pubk_y = map(cast_to_hex, public_point_coords)

        success = pubk_x == pubk[:64] and pubk_y == pubk[64:]

        return success

    # Validate the eliptic curve point class for the private keys (SECRETS).
    SECRETS = [1, 2, 3, 9, 10**50, Secp256k1.order - 1]
    for secret in SECRETS:
        public_point = Secp256k1.scalar_mult(secret)
        assert is_matching_keys(secret, public_point.get_coords())
        print(f"✅ Validated module for secret={secret}")