DHKE
In an exponential Diffie-Hellman, denoted by DHKE, one takes a group $G$ with a generator $g$ with its order $n$.
Alice and Bob, during the key exchange, generate random numbers $a$ and $b$ in the range $a,b\in (1,n)$ and transmits $g^a$ and $g^b$ and finally, they establish the key as $g^{ab}$ then use a KDF to derive a symmetric key and IV/nonce.
There is also an Elliptic Curve version of DHKE and it is denoted by ECDH and it is more used than the classical exponential version.
Prime
In DHKE, we choose prime to be a safe prime, that is $p = 2 \cdot q + 1$ with $q$ is also a prime. The $q$ is called a Sophie Germain prime.
This is a countermeasure against Pohlig-Hellman algorithm that benefits from the small factor of the $p-1$. If a safe prime is used then the factors are $2$ and $q$. Having a large factor is a countermeasure against the Pohlig-Hellman.
There is also Schnorr group with $p = r\,q + 1$. This can be considered as a generalization of the safe primes. The safe prime is optimal.
Usually, the generator $g$ is chosen to generate order $q$ so that the Legendre Symbol of $g^a$ doesn't leak low order bit of $a$.
Prime Generating
The naive approach generates a prime $q$ then checks for the primality of $2 \, q +1$ (Menezes: Algorithm 4.86). In pseudocode;
do
p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)
There are faster methods
Double-Speed Safe Prime Generation by David Naccache, 2003
as the title suggests, this speeds this up by about a factor of two by testing both $2q + 1$ and $(q − 1)/2$ for primality.
The idea is using the random prime $p$ as safe prime or Sophie Germain prime;
do
p = randomPrime(k-bit integer)
while ((p − 1)/2 and 2p + 1 are composite)
Safe Prime Generation with a Combined Sieve by Michael J. Wiener, 2003.
They proposed sieving small primes up to $2^{16}$. This provides $15x$ speed up than the naive algorithm.
The idea starts with this observation; both $q$ and $q=2p+1$ must be congruent to $2$ modulo $3$. Therefore one can eliminate the candidates with which are $0$ modulo $3$ and $1$ modulo $3$.
This can be generalized to any odd prime $r$. Eliminate $q$'s that are conguruent to $(r-1)/2$ modulo $r$ since in this case $p$ is divisible $r$.
Take a set $S$ all odd prime $<B$. Then $\prod_{r\in S}(r-2)/r$ of the candidates will survive the sieve.
If $B=2^{16}$ it is estimated that it can produce $\approx \times 15$ speed up.
Collision
Now we will look at the probability of arriving at the same random number if there are $k$ people using the same DHKE modulus. We are assuming that the $k$ people use the same secure (unpredictable) random number generator to generate their random keys. To simplify this, we can assume that there is one person who generates random numbers. In this case, this is completely the birthday-paradox and in Cryptography we look at this as the birthday attack to find a collision with 50%. This is a common way to look at the collision of the hash functions.
Let $H$ be the range of the random number generator, and the $p$ represents the probability we want, then $n(p; H)$ be the smallest number of values we have to choose;
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
In the classic hash collision case, we set $p=1/2$, and this approaches
$$n(0.5;H) \approx 1.1774 \sqrt H$$ and we usually represent as $\mathcal{O}(\sqrt{H})$
Now, let's look at some actual numbers.
2048-bit prime
Assume that $n$ is a 2048-bit number, remember $n$ was the order of the generator $g$. Then
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
With 50% probability $$n(0.5;2^{2048})\approx 2^{1204}$$
As a result, you need to generate $2^{1204}$ random numbers to hit one again with 50%. Not feasible.
4096- bit prime
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
With 50% probability $$n(0.5;2^{4096})\approx 2^{2048}$$
As a result, you need to generate $2^{2048}$ random numbers to hit one again with 50%. Not feasible.
Pre-Compute the dLog table.
Since the modulus is pre-determined by the standards, one can argue that some organizations with superpowers built some DLog table for the modulus.
This is not a danger, too. Let assume that they can build a table up to $2^{64}$ then the probability of your random hit is $$\frac{\ell \, 2^{64}}{2^{2048}}$$ with $\ell$ try. Put the possible key generation number of your group into $\ell$. So, 2048-bit is a really big number to deal with.
