secp256k1 is an elliptic curve used with Bitcoin. With this we have a curve of \(y^2=x^3+7\) (Weierstrass form of elliptic curve) and with a base point of g=(0x79be667ef9dcbbac55a06295ce870b 07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd 17b448a68554199c47d08ffb10d4b8) with a prime number of \(2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1\). The order of the curve is \(n\)=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141. In this case we will prove that \((ab)G\) is equal to \((a)(b)G\).
ECDH with secp256k1 using Python |
X2519 and ECDH
We must thus create a unique encryption key for each routing host. This is often achieved by using secp256k1, and uses ECDH (Elliptic Curve Diffie Hellman). With this we select a base x co-ordinate point of G, and then Bob and Alice generate random values, and determine their public keys. Alice generates \(a\), and Bob generates \(b\). Alice’s public key will be:
\(A= aG \)
and Bob’s public key becomes:
\(B=bG \)
The exchange their values, and Alice multiplies by the value received from Bob by \(a\), and Bob multiplies the value he receives from Alice by \(b\). They should then end up with the same value, and which should be:
\(K= abG \)
So here is a basic Python program to implement:
from secp256k1 import curve,scalar_mult import random print("Basepoint:\t", curve.g) aliceSecretKey = random.randrange(1, curve.n) alicePublicKey = scalar_mult(aliceSecretKey, curve.g) bobSecretKey = random.randrange(1, curve.n) bobPublicKey = scalar_mult(bobSecretKey, curve.g) print("\nAlice\'s secret key:\t", aliceSecretKey) print("Alice\'s public key:\t", alicePublicKey) print("\nBob\'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("\n==========================") print("abG: \t", (sharedSecret1[0])) res=(aliceSecretKey*bobSecretKey) % curve.n res=scalar_mult(res, curve.g) print("(ab)G \t", (res[0]))
We can see here that the perform the \((ab)G\) operation by multiplying \(aliceSecretKey\) and \(bobSecretKey\) and then taking \(\mod n\) and then scaling this with \(G\). The res[0] element means that we just take the x co-ordinate value:
res=(aliceSecretKey*bobSecretKey) % curve.n res=scalar_mult(res, curve.g) print("(ab)G \t", (res[0]))
And here is secp256k1.py:
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
A sample run is:
Basepoint: (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) Alice's secret key: 4343994315440782507420089117650409135767624159733852799554305098867261718156 Alice's public key: (78297706197955729350667779391386441808284296051751165431039294303456744675395, 53026595987980089952057873560627991776900908823460698813038262338893485972970) Bob's secret key: 65170588075519180455552204289336723056354524029876452054263255971647918539276 Bob's public key: (95103350695611509758480650883534725116254969214790126410271490073854292336714, 104926054008673271728343434701453979994709138304414019234704185907996583773111) ========================== ========================== Alice's shared key: (115660414424092852739774689410671739462086977293256206809544563743959327999239, 32139619968824126694502263965253429226345100195006162372388222594743027172750) Bob's shared key: (115660414424092852739774689410671739462086977293256206809544563743959327999239, 32139619968824126694502263965253429226345100195006162372388222594743027172750) ========================== abG: 115660414424092852739774689410671739462086977293256206809544563743959327999239 (ab)G 115660414424092852739774689410671739462086977293256206809544563743959327999239