MQV (Menezes–Qu–Vanstone) was created Alfred Menezes, Minghua Qu and Scott Vanstone [1] in 1995 and is an authenticated key exchange method. It was integrated into the IEEE P1363 standard, and uses points on an elliptic curve to generate a shared key. Overall Bob and Alice will hold a long-term key pair, and where these are then used to generate a shared session key.
MQV (Menezes–Qu–Vanstone) Authenticated Key Exchange |
Theory
MQV (Menezes–Qu–Vanstone) [1] was created Alfred Menezes, Minghua Qu and Scott Vanstone in 1995 and is an authenticated key exchange method. Alice holds a key pair \((A,a)\). With this \(a\) is Alice's private key, and \(A=aG\) is her public key. For Bob, his public key will be \(B=aG\) and a private key of \(b\), and where \(G\) is the base point on the elliptic curve.
We initally define a function of \( \bar{R} = (x\, \bmod\, 2^L) + 2^L \) where \(L = \left \lceil \frac{\lfloor \log_{2} n \rfloor + 1}{2} \right \rceil\), and where \(R(x,y)\) is a point on an elliptic curve. In this case \(n\) is the order of the elliptic curve. This is quite a simple translation which truncates a value to the half of the bits within the value. Thus if a value has 256 bits, this function will truncate the value to 128 bits.
Alice creates a key pair \((X,x)\) and where \(x\) is a private key value and \(X\) is a point on the elliptic curve (\(xG\)). Bob creates a key pair \((Y,y)\) and where \(y\) is a private key value and \(Y\) is a point on the elliptic curve (\(yG\)).
Alice determines:
\(S_a = x + \bar{X} a \pmod n \)
and sends \(X\) to Bob.
Bob determines:
\(S_b = y + \bar{Y} b \pmod n \)
and sends \(Y\) to Alice.
Alice computes the shared key of:
\(K = S_a (Y + \bar{Y}B)\)
Bob computes the shared key of:
\(K = S_b (X + \bar{X}A)\)
This works because Bob calculates:
\(K = S_b (X + \bar{X}A) = S_b (xG + \bar{X}aG) = S_b (x + \bar{X}a)G = S_b S_a G\)
And Alice calculates:
\(K = S_a (Y + \bar{Y}B) = S_a (yG + \bar{Y}bG) = S_a (y + \bar{Y}b)G = S_b S_a G\)
Coding
The following is the code:
from secp256k1 import curve,scalar_mult,point_add import random from math import log10,ceil print("Basepoint:\t", curve.g) L = ceil(( (log10(curve.n)/log10(2)) + 1)//2) a = random.randrange(1, curve.n) A = scalar_mult(a, curve.g) b = random.randrange(1, curve.n) B = scalar_mult(b, curve.g) x = random.randrange(1, curve.n) X = scalar_mult(x, curve.g) y = random.randrange(1, curve.n) Y = scalar_mult(y, curve.g) X_bar = (X[0] % pow(2,L)) + pow(2,L) Y_bar = (Y[0] % pow(2,L)) + pow(2,L) S_a = (x + X_bar * a) % curve.n S_b = (y + Y_bar * b) % curve.n print ("\nAlice a=",a) print ("Alice A=",A) print ("\nBob b=",b) print ("Bob B=",B) print ("\nx=",x) print ("xG=",X) print ("\ny=",y) print ("yG=",Y) print ("\nL :",L) print ("\nXbar:",X_bar) print ("Ybar:",Y_bar) print ("\nSa: ",S_a) print ("Sb: ",S_b) K1 = scalar_mult(S_a,( point_add(Y,scalar_mult(Y_bar,B)))) K2 = scalar_mult(S_b,( point_add(X,scalar_mult(X_bar,A)))) print ("\nKey (Alice):\t",K1[0]) print ("Key (Bob):\t",K2[0])
In this case we are using the secp256k1 curve:
import collections 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
And a sample run:
Basepoint: (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) Alice a= 54677135889956186114833392190043256219084694446266850335253815664319535282377 Alice A= (37992355285785692277721705802159719239535227727719651135511450302236165471786, 92734539453490230967279369595246558957376200670317938503775309873871842638670) Bob b= 48011648504757969241157227149981625595403395498739884790495888821113703073990 Bob B= (60229158858503931061859391851770936672950434585680335908405800781205194787271, 27974868771654965394661360462280402327167205235204572978148684642192488352734) x= 100783997897395859931320208985245917378076614208138531209075139569466706910045 xG= (58409368630775415313972497876052814207357071462793418361906151238116922778592, 2230785494946111895856553340998371168846149442022593855472021701025352396586) y= 63860555811958896940453412037364978059485044160334053391418061345321364933851 yG= (1730500702520367133613114637121096073981878203054817832980669146229670262305, 85735024726209329702368931285935332206394901745619771766642604257973811301236) L : 128 Xbar: 435304805608706423907456539206568272864 Ybar: 356187564779594259048747622414685943329 Sa: 13726329177401971082328566101755389081187909242254781874077679257657211199908 Sb: 60728322767876910521711344541051577957025970434253998749261687617430445992097 Key (Alice): 4278604123137778440614847009388675611814347867043782196913331343343648231581 Key (Bob): 4278604123137778440614847009388675611814347867043782196913331343343648231581
Reference
[1] Menezes, A., Menezes, F. A., Qu, M., Vanstone, S., & Sutherland, K. J. (1995). Elliptic curve systems. In IEEE P1363, Part 4: Elliptic Curve Systems.