12 of 46
Fix
fgrieu
  • 114k
  • 10
  • 245
  • 479

I'll assume the question asks: in the Diffie-Hellman key exchange protocol, how large does the secret random natural number that Alice and Bob each select needs to be.

Common wisdom is that a newly generated cryptographically secure random integer $x$ with $0\le x<2^{256}$ is safe, for otherwise sound parameters. That's possibly good for a few decades, not accounting for mathematical breakthrough, nor hypothetical quantum computers usable for cryptanalysis. More generally, $k$-kit security requires choosing an upper bound of at least $2^{2k}$. It does not harm to choose a larger bound, except for speed.

Implementations vary; most use a bound of $2^{160}$ to $2^{4096}\;$. Those that use a bound larger than about $2^{600}$ do so because the bound is set to match some other parameter (like a modulus $p\;$, see below).


The simplest form of Diffie-Hellman key exchange protocol uses the multiplicative group $\mathbb Z_p^*$ for some suitable public prime $p$, and some suitable public member $g$ of that group. Alice (resp. Bob):

  • selects a random integer $x_a$ (resp. $x_b\;$) less than $2^{2k}$ for some security parameter $k$, as considered in the question;
  • computes and sends $y_a\;=\;g^{x_a}\bmod p$ (resp. $y_b\;=\;g^{x_b}\bmod p\;$);
  • receives $y_b$ (resp. $y_a\;$);
  • computes $z_a\;=\;{y_b}^{x_a}\bmod p$ (resp. $z_b\;=\;{y_a}^{x_b}\bmod p\;$).

If the messages exchanged have not been altered during the exchange, then $z_a=z_b\;$. Both are $z\;=\;g^{x_a\cdot x_b}\bmod p\;$. For proper choice of $p$ and $g$ it is believed hard to determine that common $z\;$ from knowledge of $y_a$, $y_b$, $p$ and $g\;$. That $z$ can be used, for example, to establish a common symmetric secret key, by way of a key derivation function.

Regardless of parameters $p$ and $g$, there are generic attacks with cost $O(2^k)$ modular multiplications (with a bound of $2^{2k}$ for $x\;$). One such attack finds $x_b$ from $y_b$, by precomputing $y_b\cdot g^u\bmod p$ for $u<2^k$, then searching $(g^{2^k})^v\bmod p$ for $v\le2^k$ among that; once a match is found, it comes $x_b\;=\;v\cdot2^k-u\;$, and $z$ is then computed as ${y_a}^{x_b}\bmod p\;$. There are better methods requiring much less memory, but we know no method requiring much less time and still generic (that is working for any $p$ and $g$, and more generally any group used for a generalized Diffie-Hellman key exchange protocol).

Note: how to chose parameters $p$ and $g$, or more generally the group used, is a different matter.

fgrieu
  • 114k
  • 10
  • 245
  • 479