One possible statement of the Discrete Logarithm Problem modulo prime $p$ (the one used in practice in DSA, and more generally when working in a Schnorr group) goes:
- given
- large random prime $q$,
- very large prime $p$ with $p-1$ a multiple of $q$,
- integer $g$ of order $q$ modulo $p$ (equivalently, such that $g^q\bmod p=1$ and $g\bmod p\ne1$ ),
- $a$ obtained by taking random integer $x\in[0,q)$ and computing $a\gets g^x\bmod p$
- find $x$.
The best known algorithms to solve this on classical computers (including Pollard's rho for logarithms) have cost $O\left(\sqrt q\;\log p\;\log\log p\right)$ when $p$ is suitably large (e.g. 3072-bit $p$ or larger for 256-bit $q$).
Variants exist with the following:
- $p=2q+1$ (equivalently, $(p-1)/2$ is prime¹); but then the security bound is much lower for equal $\log q$, because the best algorithm becomes (an extension of) GNFS.
- It is asked that $g$ is of order $p-1$ (equivalently, that $g$ is a generator), rather than of order $q$ as in the above. It has at least the virtue of insuring that the order of $g$ is large.
- Discussion on $p-1$ being a multiple of a known large $q$ is removed and replaced by hope that's the case, which holds with good probability for random $g$ and very large prime $p$. One problem is, it can get hard to find $q$ and/or ascertain² the order of $g$.
By any of the above definitions of the DLP, the modulus $p$ is prime. That makes it incorrect (or at least, neither proven nor widely conjectured) to state, as the question does:
The hardness of RSA depends on two things: the Integer factorization problem and the DLP.
Also, by any of the above definitions of the DLP, the order of $g$ is a given (it's the given $q$, or $p-1$ in some variants). Even if we extend the definition of the DLP to allow for composite modulus $n$ instead of $p$, and as long as we keep assuming that the order of $g$ is a given in that extended DLP, the above statement remains incorrect (or at least, neither proven nor widely conjectured): we don't know how to break RSA given an hypothetical oracle breaking that extended DLP.
If we further extend the definition of the DLP by not assuming that the order of $g$ is a given, then it can be proven that breaking this further extended DLP allows to factor $n$, thus break RSA. The above statement becomes true, but equivalent to the common wisdom:
The hardness of RSA depends on the Integer factorization problem.
or otherwise said: breaking the integer factorization problem breaks RSA. The converse is an open problem, and sometime conjectured.
What is wrong with choosing a multiple of two primes as modulus in DH Key exchange?
If additionally the order of $g$ is known, we can factor the modulus $n$ as $n=r\,s$ with primes $r,s$. And then, using the Pohling-Hellman algorithm, we can reduce the DLP modulo $n$ to several easier DLP problem modulo $r$ and $s$ (or modulo $r^2$ is $s=r$).
In Diffie-Hellman, we don't need to make the order of $g$ known, thus we could get away with choosing $n$ in a way making it hard to find its factorization, as in RSA. But then security of DH would depend to some degree on integer factorization on top of some variant of the DLP, and that's generally not something wanted. It's done only in some contexts, like RSA accumulators.
Further, in many applications of the DLP to cryptography including Schnorr signature and DSA, the order of $g$ needs to be public. Thus using a composite $n$ would require using a much larger modulus at equivalent security, leading to slower computation for no benefit.
¹ That is, $p$ is a safe prime. That's stated as a requirement for DH key exchange in the question, but it's not: any Schnorr group (as in the first part of the question) will do.
² However, we can still pick $g$ of likely order $p-1$ with low residual odds of the contrary: pick a random $g$ until $g^{p-1}\bmod p=1$, and $g^{(p-1)/r}\bmod p\ne1$ for all primes $r$ dividing $p-1$ and $r$ low enough that we find it with simple factorization methods: trial division to some bound and a few rounds of Pollard's rho for factorization.
