import random

'''
'secp256k1',
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
a=0,
b=7,
g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
# Subgroup order.
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
# Subgroup cofactor.
h=1,
'''

# y2 = x3 + ax + b
class Curve:
    
    def __init__(self, p, a, b, g, n, h):
        # размер конечного поля
        self.p = p
        # коэффиценты уравнения a и b
        self.a = a
        self.b = b
        # базовая точка
        self.g = g
        # порядок подруппы
        self.n = n
        # кофактор подгруппы
        self.h = h

    # Обратное деление по модулю p кривой
    def inverseMod(self, k):
        if k == 0:
            raise ZeroDivisionError('division by zero')
        if k < 0:
            # k ** -1 = p - (-k) ** -1  (mod p)
            return self.p - self.inverseMod(-k)
        # Расширенный алгоритм Евклида
        s, old_s = 0, 1
        t, old_t = 1, 0
        r, old_r = self.p, self.k
        while r != 0:
            quotient = old_r // r
            old_r, r = r, old_r - quotient * r
            old_s, s = s, old_s - quotient * s
            old_t, t = t, old_t - quotient * t
        gcd, x, y = old_r, old_s, old_t
        #assert gcd == 1
        #assert (k * x) % p == 1
        return x % self.p


    # Проверка расположения точки на кривой
    def isPointCurve(self, x, y):
        return (y * y - x * x * x - self.a * x - self.b) % self.p == 0

    
    def point_neg(self, x, y):
        """Returns -point."""
        #assert is_on_curve(point)
        #result = (x, -y % self.p)
        #assert is_on_curve(result)
        #return result
        return Point(
            x = self.x,
            y = -y % self.curve.p,
        )


    def point_add(point1, point2):
        """Returns the result of point1 + point2 according to the group law."""
        assert is_on_curve(point1)
        assert is_on_curve(point2)

        if point1 is None:
            # 0 + point2 = point2
            return point2
        if point2 is None:
            # point1 + 0 = point1
            return point1

        x1, y1 = point1
        x2, y2 = point2

        if x1 == x2 and y1 != y2:
            # point1 + (-point1) = 0
            return None

        if x1 == x2:
            # This is the case point1 == point2.
            m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
        else:
            # This is the case point1 != point2.
            m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)

        x3 = m * m - x1 - x2
        y3 = y1 + m * (x3 - x1)
        result = (x3 % curve.p, -y3 % curve.p)
    #assert is_on_curve(result)

    return result


def scalar_mult(k, point):
    """Returns k * point computed using the double and point_add algorithm."""
    assert is_on_curve(point)

    if k % curve.n == 0 or point is None:
        return None

    if k < 0:
        # k * point = -k * (-point)
        return scalar_mult(-k, point_neg(point))

    result = None
    addend = point

    while k:
        if k & 1:
            # Add.
            result = point_add(result, addend)

        # Double.
        addend = point_add(addend, addend)

        k >>= 1

    assert is_on_curve(result)

    return result


# Keypair generation and ECDHE ################################################

def make_keypair():
    """Generates a random private-public key pair."""
    private_key = random.randrange(1, curve.n)
    public_key = scalar_mult(private_key, curve.g)

    return private_key, public_key