Diffie-Hellman, random number size

Question

During the key exchange, Alice and Bob both select a random natural number.

The question is how big this integer is? How many digits/bits it must have at least/most?

Answer 1

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.

It can be used a newly generated cryptographically secure random integer $x$ of 256 bits. This is conjectured safe for sound parameters (detailed below) and protocols used in practice. That's possibly good for a few decades, not accounting for mathematical breakthrough, nor hypothetical quantum computers usable for cryptanalysis.

PKCS#3 v1.4:1993 (official home) allows this, with an optional parameter $l$ length of private value in bits. When this option is used, $2^{l-1}\le x<2^l\;$ (with this option, PKCS#3 uses $x$ of fixed bit length, perhaps to reduce leakage by timing analysis). The modern Java CryptoAPI also has an $l$ parameter.

This practice is used in the Internet Key Exchange protocol of RFC 2409 with parameters of RFC 3526. It limits the cryptographic resistance to at most $O(2^{l/2})$, but, conjecturally, not significantly further down if the order of the generator used is a prime $q$ of at least about $l$ bits (or twice such a prime), which to my knowledge is met by all recommended DH parameters. See Paul C. van Oorschot and Michael J. Wiener, On Diffie-Hellman Key Agreement with Short Exponents, in proceedings of Eurocrypt 1996, which gives justification and a narrower criteria.

Choosing a larger bound for $x$ does not harm (demonstrably: by more than one bit of security), except for speed (execution time is roughly proportional to the bit length of $x$, all other things being equal). The absolute maximal security is obtained when $x$ is uniform on an interval of width equal to the order of the generator, but for some recommended DH parameters this comes at significant performance cost.

Note: This answer has been considerably expanded, following constructive criticism of an earlier version. I now stress that the above statement is relying on a stronger (thus mathematically less certain) assumption than a pure Diffie-Hellman assumption, and detail the conditions conjectured sufficient to ensure that a short exponent is secure.

---

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

• selects a random integer $x_a\;$ (resp. $x_b\;$) less than the bound $m$ discussed; the lower bound for $x$ can be $0\;$, $1\;$ (Handbook of Applied Cryptography Protocol 12.47), or $m/2\;$ (PKCS#3 with optional parameters $l$ and $m=2^l\;$);
• 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\;$).

Assuming that the messages have not been altered during the exchange, $z_a=z_b\;$. Both are $z\;=\;g^{x_a\cdot x_b}\bmod p\;$. For proper choice of $p$, $g$ and $m$ it is believed computationally infeasible to determine that common $z\;$ from knowledge of $y_a$, $y_b$, $p$ and $g\;$. That $z$ can then be used to establish a common symmetric secret key using a Key Derivation Function (beware that this protocol is vulnerable to a Man-in-the-Middle).

An $l/2$-bit security level requires choosing an upper bound $m$ at least $O(2^l)\;$. That's because regardless of parameters $p$ and $g$, there are generic attacks recovering $z$ in full with cost $O(2^{l/2})$ modular multiplications. One such attack finds $x_b$ from $y_b$, by precomputing $y_b\cdot g^u\bmod p$ for $u<2^{l/2}$, then searching $(g^{2^{l/2}})^v\bmod p$ for $v\le2^{l/2}$ among that; once a match is found, it comes $x_b\;=\;v\cdot2^{l/2}-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).

Common wisdom is that baring mathematical breakthrough or quantum computers usable for cryptanalysis, and with otherwise sound parameters, random-enough primes $p$ of 3072 bits can give about 128 bits of security. Beyond that, various practices exist for the choice of $p$, $g$, and $m\;$.

1. It can be used a safe prime $p\;$ (that is, such that $p=2q+1$ with $q$ a prime), and $g$ a generator of $\mathbb Z_p^*\;$ (a positive integer such that $g^q\bmod p\ne1\;$); and bound $m=p-1\;$. This works in the group $\mathbb Z_p^*\;$, which has even order $p-1\;$. Noticeably, a passive adversary can find whether the common $z$ is a quadratic residue modulo $p$ or not, which leaks ≈0.81 bit of entropy. This is a non-issue when $z$ is post-processed by a proper KDF.
2. As a variant it can be used $g$ of order $q\;$ (that is with $g^x\bmod p$ taking $q$ distinct values for unbounded $x\;$, which can is insured if $g^q\bmod p=1\;$ and $g\bmod p\ne1\;$), and bound $m=q\;$; or equivalently it can be used $g$ and $m$ as in [1.] above, but with restriction to even $x\;$. This is relying on a pure Diffie-Hellman assumption in the group of quadratic residues modulo $p\;$, which has prime order $q=(p-1)/2\;$. It is demonstrably as secure as [1.] is.
3. It can be used a prime $p$ such that $p=q\cdot r+1$ where $q$ is a prime of about $l$ bits; and $g$ of order $q\;$, which is equivalent to $g^r\bmod p\ne1\;$; and $m=q\;$. This is relying on a pure Diffie-Hellman assumption in a Schnorr Group of prime order $q$ of about $l$ bits. Common wisdom is that it offers about $l/2$ bits of security for small $l$; thus with a $p$ of 3072 bits, using $q$ of about 256 bits is believed not to harm security compared to $q$ of 3071 bits in [1.] or [2.] above. There's a speedup by a factor of nearly 12, which the applied cryptographer loves (even though Schnorr groups create complications for authenticated variants of the Diffie-Hellman key exchange protocol, where an active adversary could try to sneak in $y$ not member of the Schnorr group).
4. As a variant of any of the above three practices, and as suggested in the first part of the present answer, it can be chosen $m=2^l$ (and $m/2\le x<m$ in a PKCS#3 context).

When [4.] is combined with [1.] or [2.], we have the speedup of [3.] with $p$ still a safe prime. With $l$ large enough, there is no known reduction in security compared to [1.] or [2.]; but we do not know for sure how large $l$ should be. I see no argument to assert if at equivalent $l$, the security is more or less than the security of [3.] alone, which is commonly used.

When [4.] is combined with [3.], there demonstrably can't be a significant reduction in security compared to [3.] alone: no more than $\max(\log_2(q)-l,0)+1$ bits worth could be lost.

When using one or both of [3.] or [4.], the upper bound $m$ for $x$ is typically 160 to 512 bits, further with $m=q$ when not using [4.]. Otherwise (when using [1.] or [2.] without [4.]) the bound is typically per $p-1$ or $q$, thus 1023 to 4096 bits (though $p$ of 512 bits has been used, including as intentionally weakened cryptography).

Answer 2

I have to strongly disagree with the previous answer. The standard Decisional Diffie-Hellman assumption holds for the case that $g^{x_a}$ and $g^{x_b}$ are uniformly distributed in the group (which should be a prime-order subgroup). Thus, it depends on the order of the group. For example, if one takes $p=2q+1$ with both $p$ and $q$ prime and works in the subgroup of order $q$, then each of $x_a$ and $x_b$ should be uniformly chosen between 0 and $q-1$. The same is true of ECDH.

If you take a shorter exponent then there may not be any known attacks, but it becomes a less-standard and less established assumption. Since there is almost no cost in taking random values of the full length of the exponent, this is my strong recommendation.