secp256k1 [here] 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 with a prime number of \(2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1\). In this example Alice sends \(aG\) and Bob sends back \(abG\). Alice then calculates \(a^{-1} \pmod n\) and can then determine \(a^{-1} a b G = bG\). The secp256k1 curve is in the Weierstrass curve form (\(y^2=x^3+ax+b\), and the order of the curve is \(n\)=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.
Inverse function with secp256k1 using Python |
secp256k1
Bob wants to send Alice a secret value of \(bG \pmod p\). Alice initially create a secret value of \(a\), and then sends:
\(A= aG \)
Bob then takes the value of \(bG\) can creates:
\(B=baG\)
When Alice received this, she calculates \(a^{-1} \pmod n\) to give:
\(K= a^{-1} baG = bG\)
Alice now knows \(bG\) and is a shared secret with Bob. So here is a basic Python program to implement:
from secp256k1 import curve,scalar_mult,inverse_mod import random print("Basepoint:\t", curve.g) a = random.randrange(1, curve.n) aG = scalar_mult(a, curve.g) b = random.randrange(1, curve.n) bG = scalar_mult(b, curve.g) abG = scalar_mult(b, aG) a_inv = inverse_mod(a,curve.n) bG_recover = scalar_mult(a_inv, abG) print("Alice\'s secret key:\t", a) print("a_inv:\t", a_inv) print("Alice\'s public key:\t", aG) print("Bob\'s secret key:\t", b) print("\n\nBob\'s public key:\t", bG) print("a_inv abG:\t", bG_recover) if (bG==bG_recover): print("\nKey recovered")
The inverse of \(a\) is found from:
a_inv = inverse_mod(a,curve.n)
Notice that we perform the inverse mod of \(a\) using the order \(n\) of the curve. The code for secp256k1.py is:
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: 93455496723977744457586585009441553807536854397191153857426187530792766479444 a_inv: 37446929603689486247008331844815733162082468936444825594207222018043323112094 Alice's public key: (20641337806677153468204693467008577158135955401195180498711323221994547044529, 31869550396796813052794502371688707065484052456243953668695795963785846424041) Bob's secret key: 83933898788801436908272714591881907219877099618403823397640930661995112028961 Bob's public key (bG): (38821259945020412927713737603418772221170787875864514879587521760697084601655, 31238864009531232703040050319234808994055603027311761919776268119275001998114) a_inv abG: (38821259945020412927713737603418772221170787875864514879587521760697084601655, 31238864009531232703040050319234808994055603027311761919776268119275001998114) Key recovered