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 Bob and Alice will have long term private and public keys, and then will use session keys to generated a shared secret. Alice's long term private key is \(a\) and her public key is \(aG\). Bob's long term private key is \(b\) and his public key is \(bG\). Alice and Bob will generate \(x\) and \(y\), respectively for each session. They should then end up with a shared key of \((abxy)G\). In this example we will prove that \((abxy)G\) is equal to \((a)(b)(x)(y)G\).
Authenticated ECDH with secp256k1 using Python |
X2519 and ECDH
When Bob and Alice are communicating over a network, they might want to create a unique encryption key for each session. 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 long-term private key of \(a\), and Bob generates a long term private key of \(b\). Alice’s long public key will be:
\(A_{pub}= aG \)
and Bob’s long-term public key becomes:
\(B_{pub}=bG \)
Alice will store Bob's long-term key, and Bob will store Alice's long-term key, and they will use these to compute the shared key for each session. For a new session, Bob generates a random private key value of \(b\) and Alice generates a random private key of \(a\). Alice will then share a public key by and multiplying Bob's long term public key by \(a\) and \(x\):
\(A_{share}= a x B_{pub} = axbG \)
And Bob takes Alice's public key and multiplies by \(b\) and \(y\):
\(B_{share}= b y A_{pub} = byaG \)
The exchange their values, and Alice multiplies by the value received from Bob by \(y\), and Bob multiplies the value he receives from Alice by \(x\). They should then end up with the same value, and which should be:
\(A_{key}= yaxbG = abxyG )
and:
\(B_{key}= xbyaG = abxyG \)
and which are the same values.
An overview is:
So here is a basic Python program to implement using secp256k1:
from secp256k1 import curve,scalar_mult import random print("Basepoint:\t", curve.g) a = random.randrange(1, curve.n) a_pub = scalar_mult(a, curve.g) b = random.randrange(1, curve.n) b_pub = scalar_mult(b, curve.g) x = random.randrange(1, curve.n) xG = scalar_mult(x, curve.g) y = random.randrange(1, curve.n) yG = scalar_mult(y, curve.g) Bob_send = scalar_mult(y, a_pub) # (y) aG Bob_send = scalar_mult(b, Bob_send) # (yb) aG Alice_send = scalar_mult(x, b_pub) # (x) bG Alice_send = scalar_mult(a, Alice_send) # (xa) bG k_a = scalar_mult(x, Bob_send) # x (yb) aG k_b = scalar_mult(y, Alice_send) # y ( xa) bG print("\nAlice\'s secret key (a):\t", a) print("Alice\'s public key:\t", a_pub) print("\nBob\'s secret key (b):\t", b) print("Bob\'s public key:\t", b_pub) print("==========================") print("\nAlice\'s session secret key (a):\t", x) print("Alice\'s session public key:\t", Alice_send) print("\nBob\'s session secret key (b):\t", y) print("Bob\'s session public key:\t", Bob_send) print("\n==========================") print("Alice\'s shared key:\t", k_a) print("Bob\'s shared key:\t", k_b) print("\n==========================") print("abxyG: \t", (k_a[0])) res=(a*b*x*y) % curve.n res=scalar_mult(res, curve.g) print("(abxy)G \t", (res[0]))
We can see here that the perform the \((abxy)G\) operation by multiplying \(a\), \(b\), \(x\) and \(y\) 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=(a*b*x*y) % curve.n res=scalar_mult(res, curve.g) print("(abxy)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 (a): 36174920093024219696392156306003690242162474822404603858328924369879994168253 Alice's public key: (3572052161433792509600267342175648279192831386679223652914158021842810378840, 1235342631816766697094392548458428723477445557255525298350020407132367900897) Bob's secret key (b): 53509219924942155473162132152965201264615451398261194516027329249696669422222 Bob's public key: (15951408455209101037028429025972391744911835080809580141193677976899118413256, 6918895901651896086852059768371461579836056836786554642802706405760362636912) ========================== Alice's session secret key (a): 19766948269856779597330086441495512536515020866159834941668545441640224511995 Alice's session public key: (72881623455733425619419705518220198066934991645428615027845183524295615871810, 83079200979961930241312957420210934573778128130262102744709021398140045287701) Bob's session secret key (b): 76683091699302157013559881564648733094848619480308123637466457796185861338661 Bob's session public key: (105694093852805773400411449889793866681555137517498926232436098077797554053548, 85006669603370824884600453389007789822283341602358778688845638680397707853560) ========================== Alice's shared key: (10748270688032665893452586036769175734536800018568665430743809582413501276795, 12838609976384858037993587302595420945433979446657814746572600295057624743669) Bob's shared key: (10748270688032665893452586036769175734536800018568665430743809582413501276795, 12838609976384858037993587302595420945433979446657814746572600295057624743669) ========================== abG: 10748270688032665893452586036769175734536800018568665430743809582413501276795 (abxy)G 10748270688032665893452586036769175734536800018568665430743809582413501276795