DI Management Home > Cryptography > Public key cryptography using discrete logarithms > Part 2: MQV Key Agreement

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$.
  1. Alice chooses a random number $x$ in the range $[2,q-2]$ and sends $X=g^x\mod p$ to Bob.
  2. Bob chooses a random number $y$ in the range $[2,q-2]$ and sends $Y=g^y\mod p$ to Alice.
  3. Alice and Bob both compute $\overline{X} = X \mod 2^{\ell} + 2^{\ell}$ and $\overline{Y} = Y \mod 2^{\ell} + 2^{\ell}$ where $\ell = \lceil f/2\rceil$ and $f$ is the bit length of $q$.
  4. Alice computes her implicit signature $S_A = (x + \overline{X}a) \mod q$.
  5. Alice computes $t_A = YB^{\overline{Y}} \mod p$.
  6. Alice computes $Z_A = \left(t_A\right)^{S_A} \mod p$.
  7. Return shared secret $Z = Z_A$.

Similarly, Bob can also compute the same value, $Z$, using steps 4 to 7 above.

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

$YB^{\overline{Y}} = g^y\cdot\left(g^b\right)^{\overline{Y}}$   $XA^{\overline{X}} = g^x\cdot\left(g^a\right)^{\overline{X}}$
$\qquad\; = g^{y+b\overline{Y}}$   $\qquad\; = g^{x+a\overline{X}}$
$\qquad\; = g^{(y+b\overline{Y})\mod q}$   $\qquad\; = g^{(x+a\overline{X})\mod q}$
$\qquad\; = g^{S_B}, \quad$   $\qquad\; = g^{S_A}$,
and thus
$Z_A\;=\left(YB^{\overline{Y}}\right)^{S_A} = \left(g^{S_B}\right)^{S_A}$
$\qquad = g^{S_BS_A}$.
  $Z_B\;=\left(XA^{\overline{X}}\right)^{S_B} = \left(g^{S_A}\right)^{S_B}$
$\qquad = g^{S_AS_B}$.

We are allowed to do the "trick" with the exponents modulo $q$ because even if $n\neq m$ but $n\equiv m\pmod{q}$ then $g^n\equiv g^m\pmod{p}$. 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}$ since $g^q\equiv 1\pmod{p}$ by the definition of $g$.

Example of MQV key agreement by Alice

Alice computes:

Bob computes:

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$.

References

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 1 October 2016.