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. The MQV method does not include the authentication of Bob or Alice's identity as part of the key exchange. Thus HMQV protocol [2] supports this and where \(\bar {X}=H(X,IDB)\) and \(\bar {Y}=H(Y,IDA)\). \(H()\) is a hashing methold, Bob's identity is IDA and Alice's identity is IDA.
HMQV (Hashed 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. The MVQ method does not include the authentication of Bob or Alice's identity as part of the key exchange. Thus HMQV protocol [2] supports this and where \(\bar {X}=H(X,IDB)\) and \(\bar {Y}=H(Y,IDA)\). \(H()\) is a hashing method, Bob's identity is IDA and Alice's identity is IDA.
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 import hashlib print("Basepoint:\t", curve.g) BobID="Bob" AliceID="Alice" 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) sha1 = hashlib.sha1() sha1.update((BobID+str(X[0])).encode()) X_bar=int(sha1.hexdigest(),16) sha1 = hashlib.sha1() sha1.update((AliceID+str(Y[0])).encode()) Y_bar=int(sha1.hexdigest(),16) S_a = (x + X_bar * a) % curve.n S_b = (y + Y_bar * b) % curve.n print ("\nAlice ID=",AliceID) print ("Bob ID=",BobID) 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 ID= Alice Bob ID= Bob Alice a= 20716385454090237180301893780718680276625176897518302327963842746175928854727 Alice A= (52798889024308833134492983955480064440726105228424167515728588048319884202401, 109698607840564903011262848811205216896295045397692205478599322828400450013561) Bob b= 34407195498400719356221676491026172211859456788618813801849989109806213407394 Bob B= (14000654176380650776041165700355386233440811746803513001424224768640858738957, 99889796173146971313316231395966442376056851682167813735138603337268280460796) x= 106633680897723312731288587015942161088812449509172578727916425354390132797858 xG= (69055050563789248648007150116032237598956913587418246649720955442329109782712, 105370586810424086156959145063751469322518273187315970618918609619218290775358) y= 85886562442711020640661665958325208879113477133949141106580725396632437497397 yG= (36726244993597210780213788142423543032391812853368521306959736390500608705088, 71430479024840254627684470143516587382453870712797028399648853618919703228721) L : 128 Xbar: 1077440611788000102690626630372911028515539328320 Ybar: 155606856346751999706014217859425063027624139643 Sa: 83279919677866768976739144494277900340271946436491028200195902296883582673681 Sb: 35645066635997223896946393147025900904062275658523555192039105691327346892494 Key (Alice): 86786162048071063548277125531178743185916851921603806680816648596757821817608 Key (Bob): 86786162048071063548277125531178743185916851921603806680816648596757821817608
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.
[2] Krawczyk, H. (2005, August). HMQV: A high-performance secure Diffie-Hellman protocol. In Annual International Cryptology Conference (pp. 546-566). Springer, Berlin, Heidelberg [here].