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. With the long-term keys we will have a static key and the session keys will be ephemeral keys.
MQV (Menezes–Qu–Vanstone) Authenticated Key Exchange with Bouncy Castle and C# |
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\)
The computation of Alice's key is:
Coding
The following is the code:
namespace MQV { using Org.BouncyCastle.Asn1.X9; using Org.BouncyCastle.Crypto.Agreement; using Org.BouncyCastle.Crypto.Parameters; using Org.BouncyCastle.Security; class Program { static void Main(string[] args) { var curvename="secp256k1"; if (args.Length >0) curvename=args[0]; try { X9ECParameters ecParams = ECNamedCurveTable.GetByName(curvename); var curveparam = new ECDomainParameters(ecParams.Curve, ecParams.G, ecParams.N, ecParams.H, ecParams.GetSeed()); Org.BouncyCastle.Crypto.Parameters.ECKeyGenerationParameters keygenParams = new Org.BouncyCastle.Crypto.Parameters.ECKeyGenerationParameters (curveparam, new SecureRandom()); Org.BouncyCastle.Crypto.Generators.ECKeyPairGenerator generator = new Org.BouncyCastle.Crypto.Generators.ECKeyPairGenerator(); generator.Init(keygenParams); var aliceStatic = generator.GenerateKeyPair(); generator.Init(keygenParams); var aliceEmph = generator.GenerateKeyPair(); generator.Init(keygenParams); var bobStatic = generator.GenerateKeyPair(); generator.Init(keygenParams); var bobEmph = generator.GenerateKeyPair(); var u = new ECMqvBasicAgreement(); u.Init(new MqvPrivateParameters((ECPrivateKeyParameters) aliceStatic.Private, (ECPrivateKeyParameters) aliceEmph.Private, (ECPublicKeyParameters) aliceEmph.Public)); var aliceKey = u.CalculateAgreement(new MqvPublicParameters((ECPublicKeyParameters) bobStatic.Public, (ECPublicKeyParameters) bobEmph.Public)); var v = new ECMqvBasicAgreement(); v.Init(new MqvPrivateParameters((ECPrivateKeyParameters) bobStatic.Private, (ECPrivateKeyParameters) bobEmph.Private, (ECPublicKeyParameters) bobEmph.Public)); var bobKey = v.CalculateAgreement(new MqvPublicParameters((ECPublicKeyParameters) aliceStatic.Public, (ECPublicKeyParameters) aliceEmph.Public)); Console.WriteLine("Bob Key:\t{0}",bobKey); Console.WriteLine("Alice key:\t{0}",aliceKey); if (bobKey.Equals(aliceKey)) { Console.WriteLine("Keys match!!!"); } var privateKey = (ECPrivateKeyParameters) aliceStatic.Private; var publicKey = (ECPublicKeyParameters) aliceStatic.Public; Console.WriteLine("\n\n== Curve: {0} ",curvename); Console.WriteLine("\n== Alice Static Private key === "); Console.WriteLine("== D ==={0} ",privateKey.D.ToString()); Console.WriteLine("\n== Alice Static Public key === "); Console.WriteLine("== Q_x ==={0} ",publicKey.Q.XCoord); Console.WriteLine("== Q_t ==={0} ",publicKey.Q.YCoord); privateKey = (ECPrivateKeyParameters) aliceEmph.Private; publicKey = (ECPublicKeyParameters) aliceEmph.Public; Console.WriteLine("\n== Alice Ephemeral Private key === "); Console.WriteLine("== D ==={0} ",privateKey.D.ToString()); Console.WriteLine("\n== Alice Ephemeral Public key === "); Console.WriteLine("== Q_x ==={0} ",publicKey.Q.XCoord); Console.WriteLine("== Q_t ==={0} ",publicKey.Q.YCoord); privateKey = (ECPrivateKeyParameters) bobStatic.Private; publicKey = (ECPublicKeyParameters) bobStatic.Public; Console.WriteLine("\n== Bob Static Private key === "); Console.WriteLine("== D ==={0} ",privateKey.D.ToString()); Console.WriteLine("\n== Bob Static Public key === "); Console.WriteLine("== Q_x ==={0} ",publicKey.Q.XCoord); Console.WriteLine("== Q_t ==={0} ",publicKey.Q.YCoord); privateKey = (ECPrivateKeyParameters) bobEmph.Private; publicKey = (ECPublicKeyParameters) bobEmph.Public; Console.WriteLine("\n== Bob Ephemeral Private key === "); Console.WriteLine("== D ==={0} ",privateKey.D.ToString()); Console.WriteLine("\n== Bob Ephemeral Public key === "); Console.WriteLine("== Q_x ==={0} ",publicKey.Q.XCoord); Console.WriteLine("== Q_t ==={0} ",publicKey.Q.YCoord); } catch (Exception e) { Console.WriteLine("Error: {0}",e.Message); } } } }
In this case we are using the secp256k1 curve:
Bob Key: 95394429104596954477553644537192954621531036907800125619608473061332093811995 Alice key: 95394429104596954477553644537192954621531036907800125619608473061332093811995 Keys match!!! == Curve: P-256 == Alice Static Private key === == D ===108585388809762365192064751722695478305449845656161187703807186379732362930530 == Alice Static Public key === == Q_x ===a2a826efff993c55042f79940e2cc0ffcba65acec927e52ab2528f99898d95ce == Q_t ===46100cbc47c3ef480f52d4c56ad694a9bef472a63cc9276262fb6ab7f61ba85d == Alice Ephemeral Private key === == D ===78946773263570874571296732682517796013658492435047553744267319054733714025468 == Alice Ephemeral Public key === == Q_x ===e28ee6f06e1021eacc1c0f72b99082e5d2064606910fd77faa71e4c8ceaedef1 == Q_t ===97bb63bf27dddb277bf0f8d0fd2354126c989716ab8e2d8bff4c1d64f57bad0d == Bob Static Private key === == D ===43233267313253232378588447908906328203390218053442637164840679443910706549899 == Bob Static Public key === == Q_x ===c39487fa3af129690c02e607fdf63a01513cee8b79e72b6afa77954cbe159c33 == Q_t ===dd43bfa2ff346afa6f652e4727fe07a9cc943488957ef2da2dd16ddeb3add5c == Bob Ephemeral Private key === == D ===52843113830233224751159351548584319737720497401118175381195840465408582570917 == Bob Ephemeral Public key === == Q_x ===2261bfdb35ba5e59d68ff269dce329d901764feae25863fe7fbde347d2b21c2 == Q_t ===c6b5fff8127e0198d2a48024cc816eb1779603c3dd55808bd9c06404d35b7b17
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.