Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Elliptic Curve Diffie-Hellman key exchange from scratch
#!/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
You can’t perform that action at this time.