Elliptic Curve Diffie Hellman (ECDH) is used to create a shared key. In this we use the elliptic curve defined as secp256k1 to generate points on the curve. Bob will generate a public key (\(Q_B\)) and private key (\(d_B\)), as will Alice (\(Q_A\) and \(d_A\)). They then exchange their public keys, and the shared key will then be \(d_A \times d_B \times G\), and where \(G\) is the generator point on the elliptic curve. Another popular curve is Curve 25519, and which is used by Tor nodes [here]
Elliptic Curve Diffie Hellman (ECDH) with secp256k1 |
Theory
Elliptic Curve Diffie Hellman (ECDH) is used to create a shared key. In this example we use secp256k1 (as used in Bitcoin) to generate points on the curve. Its format is:
\(y^2 = x^3+7\)
with a prime number (p) of 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
and which is \( 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 \)
All our operations will be (mod p)
Bob will generate a public key and a private key by taking a point on the curve. The private key is a random number (\(d_B\)) and the Bob's public key (\(Q_B\)) will be:
\(Q_B = d_B \times G\)
Alice will do the same and generate her public key (\(Q_A\)) from her private key (\(d_A\)):
\(Q_A = d_A \times G\)
They then exchange their public keys. Alice will then use Bob's public key and her private key to calculate:
SharekeyAlice\( = d_A \times Q_B\)
This will be the same as:
SharekeyAlice\( = d_A \times d_B \times G\)
Bob will then use Alice's public key and his private key to determine:
SharekeyBob \(= d_B \times Q_A\)
This will be the same as:
SharekeyBob\( = d_B \times d_A \times G\)
And the keys will thus match.
The following illustrates the process:
Sample run
A sample run is:
G: (55066263022277343669578718895168534326250603453777594175500187360389116729240L, 32670510020758816978083085130507043184471273380659243275938904335757337482424L) P: 115792089237316195423570985008687907853269984665640564039457584007908834671663 Alice's secret key: 11302873530277286977317330088775295887228613968519091334644437952622729383175 Alice's public key: (43762022694931184757492607356752180905518342017728551120282167112666275442351L, 114384988717018399469597034834957578408750274128921832447140766594105794755401L) Bob's secret key: 57357023452856094330375933847127925090028363431260832480927591194583881325524 Bob's public key: (55091946369527979001134485845266995342724549818123857460791054009076326226426L, 97187020471842083008659802753584322405090644904628617139758459912605661136781L) ========================== ========================== Alice's shared key: (57532214745918139757345382685094974834256492408547750418623750043147069440196L, 96501482835335029014756728397878054304682795886955595404840493797142776000789L) Bob's shared key: (57532214745918139757345382685094974834256492408547750418623750043147069440196L, 96501482835335029014756728397878054304682795886955595404840493797142776000789L) ========================== The shared value is the x-value: 57532214745918139757345382685094974834256492408547750418623750043147069440196
Code
Here is the code to generate this:
import collections import random EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') curve = EllipticCurve( 'secp256k1', # Field characteristic. p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f, # Curve coefficients. a=0, b=7, # Base point. g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), # Subgroup order. n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141, # Subgroup cofactor. h=1, ) # Modular arithmetic ########################################################## def inverse_mod(k, p): """Returns the inverse of k modulo p. This function returns the only integer x such that (x * k) % p == 1. k must be non-zero and p must be a prime. """ if k == 0: raise ZeroDivisionError('division by zero') if k < 0: # k ** -1 = p - (-k) ** -1 (mod p) return p - inverse_mod(-k, p) # Extended Euclidean algorithm. s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = p, 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 % p # Functions that work on curve points ######################################### def is_on_curve(point): """Returns True if the given point lies on the elliptic curve.""" if point is None: # None represents the point at infinity. return True x, y = point return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0 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 ECDSA ################################################ 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 print("Basepoint:\t", curve.g) aliceSecretKey, alicePublicKey = make_keypair() bobSecretKey, bobPublicKey = make_keypair() print("Alice\'s secret key:\t", aliceSecretKey) print("Alice\'s public key:\t", alicePublicKey) print("Bob\'s secret key:\t", bobSecretKey) print("Bob\'s public key:\t", bobPublicKey) print("==========================") sharedSecret1 = scalar_mult(bobSecretKey, alicePublicKey) sharedSecret2 = scalar_mult(aliceSecretKey, bobPublicKey) print("==========================") print("Alice\'s shared key:\t", sharedSecret1) print("Bob\'s shared key:\t", sharedSecret2) print("==========================") print("The shared value is the x-value: \t", (sharedSecret1[0]))