21
$\begingroup$

This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective.

RSA labs makes a similar statement:

The discrete logarithm problem bears the same relation to these systems as factoring does to the RSA system: the security of these systems rests on the assumption that discrete logarithms are difficult to compute.

Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

If you had a discrete log oracle could you use it to attack RSA?

$\endgroup$

3 Answers 3

11
$\begingroup$

According to this:

To summarize: solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes.

So, given your question "Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?" the answer would be yes. Furthermore, if you can solve DLP for composite moduli, you can also solve it for prime moduli. This is, however, slightly different from the answer you linked to since the modulus in DH is not composite. @poncho stated in a comment to that answer that "If your Oracle to solve DLOG works only in a prime modulus, there's no obvious way to use that to factor" which I have not been able to verify.

So, being able to solve DLP for a composite moduli would break both RSA and DH, but it is unclear whether breaking DH would allow you to break RSA.

$\endgroup$
4
  • $\begingroup$ Can you find a citation that states that it is an open question if a break in DH would have implications for RSA? $\endgroup$ Sep 27, 2011 at 18:34
  • 1
    $\begingroup$ @e501 I'll keep looking, but haven't found anything yet. I did find a 2003 BS thesis (wstein.org/projects/john_gregg_thesis.pdf) which doesn't show a link (nor does it state that there is definitely no link) leading me to believe that it is still an open problem. $\endgroup$
    – mikeazo
    Sep 27, 2011 at 18:43
  • $\begingroup$ It's unlikely you'll find anything that shows there's no connection between solving the DLP for primes and factoring because they're very different problems with no obvious connection. You could similarly fruitlessly search for citations stating that an efficient solution to the TSP would not lead to a fast factoring algorithm or DLP solutions. $\endgroup$
    – ByteCoin
    Oct 16, 2011 at 21:49
  • $\begingroup$ @ByteCoin: actually, an efficient solution to the Traveling Salesman Problem would lead to a fast factoring algorithm (and DLP problem and a break to AES and a host of other things as well...) $\endgroup$
    – poncho
    Mar 3 at 19:11
13
$\begingroup$

There is a reduction from RSA to DL if the DL oracle accepts composite modulus. For prime modulus, a reduction is not known. I copied the following from this wikipedia page with minor edits.

Let $n = p\,q$ be an RSA modulus.

  1. Generate random integer $a$ co-prime to $n$ and a random integer $x$ taken in an interval much larger than $n$, say $[1,1000n]$.

  2. Compute $b = a^x \bmod n$ but don't tell $x$ to the 'discrete log oracle'.

  3. Instead ask it to find the discrete log of $b \bmod n$ (to base $a$). Let the value returned by the oracle be $y$.

  4. If $y$ is a solution, then so is $y\pm\varphi(n)$ where $\varphi$ is Euler's totient function, and $0<\varphi(n)<n$. It follows there are at least $1000$ solutions $y$ that lie in the interval of $1000\,n$ integers from which we picked $x$ uniformly at random, thus the oracle has probability $\le\frac1{1000}$ of finding $x$. There is thus a high probability that $y\neq x$. If so, $|x-y|$ will be a multiple of the order of $a$, which can easily be used to factor $n$. I will not go to the details of factoring once (a multiple of) the order of $a$ is known (since this is a well known method, also used in Shor's algorithm). If we are unlucky and $x=y$, then we start over.

$\endgroup$
1
  • 1
    $\begingroup$ The justification was flawed with the former "random number $x<n$ but very close to $n$": it was uncertain that "There is a very high probability that $y\ne x$". Suppose $n=p\,q$ with all 4 of $p$, $q$, $(p−1)/2$ and $(q−1)/2$ large primes and $p\ne q$. Then a random $x$ in $(5n/9,n)$ is also the highest $y$ less than $n$ such that $b=a^y\bmod n$. An oracle always returning such $y$ can't be used to factor $n$ by the method given. The argument was fixed by taking $x$ random in an interval much larger than $n$. $\endgroup$ Oct 4, 2018 at 9:59
5
$\begingroup$

You need to refine your definition of discrete logarithm to get a precise answer, as the discrete logarithm problem can be defined for any group, Being able to compute the discrete logarithm on the group of points of a degenerate elliptic curves defined over the ring $Z_n$ also yields the factorization of $n$ (see Silverman's xedni calculus).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.