One possible statement of the Discrete Logarithm Problem modulo prime $p$ (the one used in practice in [DSA][1], and more generally when working in a [Schnorr group][2]) 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-1)/2}\bmod p=p-1$ ), - $a$ obtained by taking random integer $x\in[0,q)$ and computing $a\gets g^x\bmod p$ - find $x$. The best know algorithms to solve this on classical computers (including [Pollard's rho][3]) 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][4]. - 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 a random very large prime $p$. One problem is, it can get hard to find $q$ and/or the order of $g$. - 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. ___ 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. Even if we extend the definition of the DLP to allow for composite modulus $n$ instead of $p$, and as long as we assume 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 is proven that breaking that further extended DLP allows to factor $n$, thus break RSA. The above statement becomes true, but trivially equivalent to the common wisdom: **The hardness of RSA depends on the Integer factorization problem.** (Actually proven in only one direction: breaking the integer factorization problem breaks RSA). ___ > 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=\prod{r_i}^{k_i}$. And then, using the [Pohling-Hellman algorithm][5], we can reduce the DLP modulo $n$ to several easier DLP problem modulo ${r_i}^{k_i}$. 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 be depend on integer factorization (on top of some variant of the DLP), and that's not something wanted. 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][6]. 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. [1]: https://en.wikipedia.org/wiki/Digital_Signature_Algorithm [2]: https://en.wikipedia.org/wiki/Schnorr_group [3]: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms [4]: https://en.wikipedia.org/wiki/General_number_field_sieve [5]: https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm [6]: https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes