Public key cryptography using discrete logarithms.
Part 2: MQV Key Agreement
The original Diffie-Hellman Key Exchange method is still susceptible to a man-in-the-middle attack where an active adversary can manipulate the messages and discover the shared secret.
| << previous: Diffie-Hellman key exchange | next: ElGamal Encryption >> |
MQV Key Agreement
MQV key agreement is an improvement on the basic Diffie-Hellman designed to eliminate a man-in-the-middle attack. It is named after Menezes, Qu and Vanstone [MQV98]. The original paper is written for elliptic curve cryptography, but the protocol also works with discrete logarithms. Unfortunately there may be patents associated with it.
MQV assumes that the two parties, Alice and Bob, have already established and authenticated their static key pairs $(a,A)$ and $(b,B)$ with each other; that is, Alice trusts that Bob's public key $B$ really is his, and Bob trusts Alice's public key $A$. Each party generates a random sessional or ephemeral key pair, $(x,X=g^x)$ and $(y,Y=g^y)$, and these are used together with the static keys to create a new shared secret.
Algorithm: MQV Key Agreement
INPUT: Domain parameters $(p,q,g)$; pre-established D-H key pairs $(a,A=g^a)$ and $(b,B=g^b)$.
OUTPUT: Shared secret $Z$ in the range $0\lt Z\lt p$.
- Alice chooses a random number $x$ in the range $[2,q-2]$ and sends $X=g^x\bmod p$ to Bob.
- Bob chooses a random number $y$ in the range $[2,q-2]$ and sends $Y=g^y\bmod p$ to Alice.
- Alice and Bob both compute $\overline{X} = X \bmod 2^{\ell} + 2^{\ell}$ and $\overline{Y} = Y \bmod 2^{\ell} + 2^{\ell}$ where $\ell = \lceil f/2\rceil$ and $f$ is the bit length of $q$.
- Alice computes her implicit signature $S_A = (x + \overline{X}a) \bmod q$.
- Alice computes $t_A = YB^{\overline{Y}} \bmod p$.
- Alice computes $Z_A = \left(t_A\right)^{S_A} \bmod p$.
- Return shared secret $Z = Z_A$.
Similarly, Bob can also compute the same value, $Z$, using steps 4 to 7 above.
- 4. Bob computes his implicit signature $S_B = (y + \overline{Y}b) \bmod q$.
- 5. Bob computes $t_B = XA^{\overline{X}} \bmod p$.
- 6. Bob computes $Z_B = \left(t_B\right)^{S_B} \bmod p$.
- 7. Return shared secret $Z = Z_B$.
The value of $\ell$ is half the bit length of $q$ rounded upwards. The bit length of $q$ is given by $f = \lfloor\log_2 q\rfloor + 1$. The value $\overline{Y}$ is the right-most $\ell$ bits of $Y$ (i.e. bits $0$ to $\ell-1$) with bit $\ell$ set to one. The idea behind using a truncated $X$ and $Y$ is to reduce the computational effort in step 5.
▷ Why does this work?
Working modulo $p$ we have| \begin{align*} YB^{\overline{Y}} &= g^y\cdot\left(g^b\right)^{\overline{Y}} \\ &= g^{y+b\overline{Y}} \\ &= g^{(y+b\overline{Y})\bmod q}\\ &= g^{S_B}, \end{align*} | and | \begin{align*} XA^{\overline{X}} &= g^x\cdot\left(g^a\right)^{\overline{X}} \\ &= g^{x+a\overline{X}} \\ &= g^{(x+a\overline{X})\bmod q} \quad\text{(Note 1)}\\ &= g^{S_A}, \end{align*} |
| and thus | ||
| \begin{align*} Z_A&=\left(YB^{\overline{Y}}\right)^{S_A} = \left(g^{S_B}\right)^{S_A} \\ &= g^{S_BS_A} \end{align*} | \begin{align*} Z_B&=\left(XA^{\overline{X}}\right)^{S_B} = \left(g^{S_A}\right)^{S_B} \\ &= g^{S_AS_B} \end{align*} | |
We can do the operation with exponents modulo $q$ at Note (1) above because of the following:
If $n \equiv m \pmod q$ and $g^q \equiv 1 \pmod p$ then $g^n \equiv g^{m \bmod q} \equiv g^m \pmod p$, even if $n\ne m$.
This follows because $n\equiv m\pmod{q}$ means $n=m+kq$ for some integer $k$ and so
$g^n\equiv g^{m+kq} \equiv g^m\left(g^q\right)^k \equiv g^m(1)^k \equiv g^m \pmod{p}$.
Example of MQV key agreement by Alice
- INPUT: Domain parameters $(p=283, q=47, g=60)$
- INPUT: Pre-established static key pairs $(a,A)=(24,158)$ and $(b,B)=(7,216)$
- 1. Alice chooses a random $x=25$, computes $X=g^x = 60^{25}\bmod p = 141$, and sends $X$ to Bob.
- 2. Bob chooses a random $y=32$, computes $Y=g^y = 60^{32}\bmod p = 175$, and sends $Y$ to Alice.
- 3. Both parties compute:
$\qquad$ $f = 6$, the bit length of $q$, so $\ell=\lceil f/2\rceil = 3$,
$\qquad$ $\overline{X}=X\bmod 2^{\ell} + 2^{\ell} = 141\bmod 2^3 + 2^3 = 5 + 8 = 13$ and
$\qquad$ $\overline{Y}=Y\bmod 2^{\ell} + 2^{\ell} = 175\bmod 2^3 + 2^3 = 7 + 8 = 15$
Alice computes:
- 4. $S_A = (x + \overline{X}a) \bmod q = (25 + 13\cdot 24)\bmod 47 = 8$
- 5. $t_A = Y\cdot B^{\overline{Y}}\bmod p = 175\cdot 216^{15}\bmod 283 = 151$.
- 6. $Z_A = t_A^{S_A}\bmod p = 151^8\bmod 283 = 207$.
Bob computes:
- 4. $S_B = (y + \overline{Y}b) \bmod q = (32 + 15\cdot 7)\bmod 47 = 43$
- 5. $t_B = X\cdot A^{\overline{X}}\bmod p = 141\cdot 158^{13}\bmod 283 = 225$.
- 6. $Z_B = t_B^{S_B}\bmod p = 225^{43}\bmod 283 = 207$.
The shared secret known only to Alice and Bob is $Z=207$. Note that this works despite the very small numbers we end up with after truncating $X$ and $Y$.
Further improvements and issues
There are several improvements to the basic MQV protocol outlined above. These include HMQV: A High-Performance Secure Diffie-Hellman Protocol [Krawczyk, 2005], and the Fully Hashed MQV (FHMQV) [Sarr et al, 2009].
The MQV protocol was dropped from the NSA's Suite B of cryptographic standards (themselves since retired). The smell of patents also lingers.
References
- [MQV98] Law, Laurie, Alfred Menezes, Minghua Qu, Jerry Solinas, and Scott Vanstone (1998). An Efficient Protocol for Authenticated Key Agreement, Technical report CORR 98-05, University of Waterloo, Canada, March 1998. Revised August 28 1998. <pdf-link>
| << previous: Diffie-Hellman key exchange | next: ElGamal Encryption >> |
Contact us
To comment on this page or to contact us, please send us a message.
This page first published 25 August 2013. Last updated 9 September 2025.
