Return to Answer

• $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 a random very large prime $p$. One problem is, it can get hard to find $q$ and/or ascertain² the order of $g$.

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 trivially equivalent to the common wisdom:

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, we can reduce the DLP modulo $n$ to several easier DLP problem modulo ${r_i}^{k_i}$.

• $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$.

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:

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$).

• 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$.

² 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$ with $r$ low enough that it can be found with simple factorization methods: trial division to some bound and a few rounds of Pollard's rho for factorization.

• 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$.

² 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.

The best know 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$).

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:

or otherwise said: breaking the integer factorization problem breaks RSA (the converse is an open problem, and sometime conjectured).

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.

² 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$ with $r$ low enough that it can be found with simple factorization methods: trial division to some bound and a few rounds of Pollard's rho for fctorization.

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$).

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 trivially equivalent to the common wisdom:

or otherwise said: breaking the integer factorization problem breaks RSA. The converse is an open problem, and sometime conjectured.

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.

² 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$ with $r$ low enough that it can be found with simple factorization methods: trial division to some bound and a few rounds of Pollard's rho for factorization.