Created
March 5, 2020 20:47
-
-
Save mrinalwadhwa/1b3c0a6c6da74065d2baf755a8fc90e8 to your computer and use it in GitHub Desktop.
Elliptic Curve Diffie-Hellman key exchange from scratch
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment