Elliptic Curve Diffie-Hellman key exchange from scratch

ecdh.py

#!/usr/bin/env python3

# The below code is an attemt to understand Elliptic Curve Cryptography
# by implementing Elliptic Curve Diffie-Hellman key exchange from scratch.

# DON'T USE THIS CODE IN YOUR APP!!
# It is not safe and is intended only as a learning tool.


import secrets

# Returns (gcd, x, y) such that a * x + b * y == gcd,
# where gcd is the greatest common divisor of a and b
def extended_euclidean_algorithm(a, b):
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

    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

    return old_r, old_s, old_t


# Returns an integer m such that (n * m) % p == 1
# m is the multiplicative inverse of n modulo p
def inverse_mod(n, p):
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd

    if gcd != 1:
        # Either n is 0, or p is not a prime number.
        raise ValueError('{} has no inverse modulo {}'.format(n, p))

    return x % p

class Curve:
    def __init__(self, name, p, a, b, G, h, n):
        self.name = name
        self.p = p
        self.a = a
        self.b = b
        self.G = G
        self.h = h
        self.n = n
        self.order = h * n

    def __repr__(self):
        return "Curve(\n\tname={},\n\tp={},\n\ta={},\n\tb={},\n\tG={},\n\tn={}\n)".format(
            self.name, self.p, self.a, self.b, self.G, self.n)

    # Returns True if the given point lies on the elliptic curve
    def is_point(curve, point):
        if point is None:
            # None represents the point at infinity.
            return True
        x, y = point
        a, b, p = curve.a, curve.b, curve.p
        return (y * y - x * x * x - a * x - b) % p == 0

    # Returns the result of point1 + point2 according to the group law.
    def add_points(curve, point1, 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:
            # point1 == point2.
            m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
        else:
            # 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)

        return result


    def negative_of_point(curve, point):
        # None represents the neutral element at inifinity 0
        # Negative of neutral element is neutral element -0 = 0
        if point is None:
            return None

        x, y = point
        return (x, -y % curve.p)

    def multiply_point_with_scalar(curve, k, point):
        if k % curve.order == 0 or point is None:
            return None

        if k < 0:
            # k * point = -k * (-point)
            return curve.multiply_point_with_scalar(-k, curve.negative_of_point(point))

        result = None
        addend = point

        while k:
            # Add if bit is 1
            if k & 1:
                result = curve.add_points(result, addend)

            # Double on all
            addend = curve.add_points(addend, addend)

            k >>= 1

        return result


def ecdh(curve):
    alice_private_key = secrets.SystemRandom().randint(2, curve.order - 1)
    alice_public_key = curve.multiply_point_with_scalar(alice_private_key, curve.G)
    # send alice_public_key to bob

    bob_private_key = secrets.SystemRandom().randint(2, curve.order - 1)
    bob_public_key = curve.multiply_point_with_scalar(bob_private_key, curve.G)
    # send bob_public_key to alice

    # alice calculates
    s1 = curve.multiply_point_with_scalar(alice_private_key, bob_public_key)

    # bob calculates
    s2 = curve.multiply_point_with_scalar(bob_private_key, alice_public_key)

    # both arrive at the same result
    assert s1 == s2


    print("Alice: Private Key:", hex(alice_private_key))
    print("Alice's Public key: (0x{:x}, 0x{:x})".format(*alice_public_key))

    print("Bob's Private key:", hex(bob_private_key))
    print("Bob's Public key: (0x{:x}, 0x{:x})".format(*bob_public_key))

    print('Alice - Shared Secret: (0x{:x}, 0x{:x})'.format(*s1))
    print('Bob - Shared Secret: (0x{:x}, 0x{:x})'.format(*s2))


toy = Curve(
    name='Toy Curve',

    # the prime modulus
    p=17,

    # coefficients a and b in the curve equation
    a=2,
    b=2,

    # base point
    G=(5,1),

    # order of the curve is h * n
    h=1,
    n=19
)

p256 = Curve(
    name='P-256',

    # the prime modulus
    p=0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff,

    # coefficients a and b in the curve equation
    a=-3,
    b=0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b,

    # base point
    G=(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
       0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5),

    # order of the curve is h * n
    h=1,
    n=0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
)

ecdh(p256)






# This above code heavily inspired from Andrea Corbellini's example here:
# https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdhe.py
# MIT LICENCE
# Copyright (c) 2015 Andrea Corbellini