Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers 3

up vote 6 down vote accepted

There is a reduction from DL to RSA 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 = pq$ be RSA modulus.

  1. Generate random number $a$ co-prime to $n$ and random number $x < n$ but very close to $n$.

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

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

  4. There is a very 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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
Can you find a citation that states that it is an open question if a break in DH would have implications for RSA? –  Ethan Heilman Sep 27 '11 at 18:34
1  
@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. –  mikeazo Sep 27 '11 at 18:43
    
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. –  ByteCoin Oct 16 '11 at 21:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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