In DH key exchange, first, both parties need to agree on a generator $g$ and prime $p$. After that each party computes its key (party A: $g^a \bmod p$) and (party B: $g^b \bmod p$), then they exchange these values to compute the shared secret. Can you please clarify which of these numbers should be random for each session (assume it is used with a protocol like TLS)?


TL;DR: $a$ and $b$.

For DHE in the multiplicative group modulo $p$, it is agreed on a large prime $p$ and an element $g$. This is typically long term, and there are standard public parameters, e.g. the 3072-bit MODP group of RFC 3526

After this, each time two parties A and B want a shared secret

  • party A draws a random $a$ and sends $h_A = g^a\bmod p$ and
  • party B draws a random $b$ and sends $h_B = g^b\bmod p$.
  • party A receives $h_B$ and computes $s_A={h_B}^a\bmod p$ and
  • party B receives $h_A$ and computes $s_B={h_A}^b\bmod p$.

If no message has been altered, $s_A=s_B$ and this is a shared secret $s$. It is typically used as input to a key derivation function or hash in order to generate some shared secret symmetric key(s).

More precisely, if the order of $g$ is a large prime (including when $(p-1)/2$ is prime and $g^{(p-1)/2}\bmod p=1$ and $1<g<p$), and $a$ and $b$ are uniformly random, independent, secret, and large enough, a passive adversary can not distinguish $s$ from a random element of the subgroup generated by $g$. Beware that the party sending its $h$ second can influence $s$ to some degree. Also, when $g$ is a generator of $[1,p)$ as in the question, the order of $g$ is $p-1$, thus even, and the Legendre symbol $\left(\frac sp\right)$ leaks. This is a consideration when using DHE without a key derivation function, discussed there.

The system was published by Withfield Diffie and Martin Hellman: New Directions in Cryptography, in IEEE Transactions in Information Theory, 1976, with some presentations in 1975. See this for how it was discovered but not published by Malcolm John Williamson, working for the GCHQ, in 1974.

Note: Nothing immediately disastrous happens if a single one of $a$ or $b$ is kept constant (making the corresponding $h_A$ or $h_B$ constant). However that static ephemeral setup is generally a bad idea for key exchange, because there remains no protection against a bad RNG on the side responsible for choosing the remaining random. Also, because it is used for a long time, the constant secret is more likely to leak, revealing all shared secrets. These are reasons why TLS 1.3 requires ephemeral ephemeral DHE (see this). When online key exchange is not an option, a secret must nevertheless be fixed: DHE becomes the first step of ElGamal encryption, with the static $h_A$ the public key for A, and $a$ the matching private key.

If we make both $a$ and $b$ static, the shared secret becomes a constant. That can still be useful (e.g. after a key derivation step with a random value), but this static static setup is hardly a key exchange protocol.

Note: In practice, in protocols like TLS, the exchange has extra steps in order to authenticate the parties using public/private key pairs, and guard against active attacks including Man in the Middle. This is Authenticated Diffie-Hellman key Exchange.

Note: the question says "each party computes its key", but $h_A$, $h_B$ are normally not considered "keys" in DHE. Only for static $a$ or $b$ are $h_A$ or $h_B$ said to be "public keys". $s_A$, $s_B$, normally the same, often are called the "shared key", although I prefer "shared secret", to distinguish from the output of a later key derivation step.

  • 1
    $\begingroup$ @fgrieu corrected the noted errors. You can delete them from your answer now I guess not to confuse the reader. $\endgroup$ – user9371654 Mar 18 '20 at 20:58
  • 1
    $\begingroup$ The original paper New Directions in Cryptography $\endgroup$ – kelalaka Mar 18 '20 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.