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