Let $ALG_2$ be an algorithm that solves the RSA problem, can it solve the generalized Diffie-Hellman problem?

Question

Let $ALG_2$ be an algorithm that solves the RSA problem for all $e\in \mathbb{Z}_n^*$ i.e given $e,m^e,n$ then $ALG_2(e,m^e,n)=m$. Is it possible to use this algorithm to solve the generalized Diffie-Hellman problem?

By generalized Diffie-Hellman I mean that we choose $n=pq$ where $p,q$ are both primes (found something else online so wasn't sure if everyone will understand).

So at start, I thought it can but couldn't prove that. So I just thought maybe it can't because what it actually does is get 2 numbers- $e$ and $m^e$- and calculate root $e$ of $m^e$ i.e $m$. But at Diffie-Hellman we don't know anything about the ratios between $r_a,r_b$ or even $g^{r_a},g^{r_b}$ and all we know is $g,g^{r_a},g^{r_b},n$. The only thing I can think of is find $r_a$ and $r_b$ by guessing numbers and using $g$ but it doesn't use $ALG_2$.

Anyone got any ideas?

Answer 1

Suppose you had an algorithm $\operatorname{DL}(n, g, h)$ that, with probability $p$, successfully yields $x$ such that $h \equiv g^x \pmod n$.

Then you could define $\operatorname{FACTOR}(n)$ as follows:

1. Pick $g$ and $h$ uniformly at random.
2. Compute $x = \operatorname{DL}(n, g^2, h^2)$.
   • If successful, $h^2 \equiv (g^2)^x \equiv (g^x)^2 \pmod n$; hence $$n \mid (g^x)^2 - h^2 = (g^x + h) (g^x - h).$$
3. Fail if $g^x \equiv \pm h \pmod n$.
   • If not, then each of $p$ or $q$ must divide $g^x \pm h$ but not both.
4. Compute $\gcd(g^x \pm h, n)$.

This succeeds with about probability $p/2$—every quadratic residue $h^2$ has exactly four square roots modulo $n$, so there's only a 1/2 chance that $g^x$ is $\pm h$—and a handful of arithmetic.

Nobody has found a way to factor $n$ given an oracle to solve the RSA problem modulo $n$, so this suggests you're not likely to find a way to implement $\operatorname{DL}(n, g, h)$ in terms of your $\operatorname{ALG_2}(e, c, n)$ RSA oracle. If you did, the editors of many reputable cryptography journals and conferences would like to hear from you!

This reduction breaks down if your DL algorithm works only for quadratic nonresidues. On the other hand, if you it worked only for quadratic nonresidues, then you could probably use that to (somewhat inefficiently) solve the quadratic residuosity problem, and that might be publicationworthy in reputable cryptography journals; as far as I know nobody has found a reduction of RSA to QR or vice versa.

Answer 2

It does not look likely that an RSA oracle would be of much help in solving the generalized DH problem.

Suppose we had a way of using an RSA oracle to solve the generalized DH problem; further assume that the invocations the method gives to the RSA oracle are restricted to the $n$ we are solving the generalized DH problem in, and assume that the method is strictly more efficient than solving the DH problem over one of the prime factors.

If so, then we would be able to efficiently solve the standard DH problem; given values $g, p, g^x \bmod p, g^y \bmod p$, then we could select a safe prime $q$ (that is, one for which $(q-1)/2$ is also prime), and map the original DH problem into one over $n=pq$ (I tried to write out the details, they're both fairly straight-forward and tedious). So, we take this combined problem $h, n, h^z \bmod n, h^w \bmod n$, which is a generalized DH problem, and involve the method. Whenever the method calls the RSA oracle, we would use the known factorization of $n$ to compute the solution. Then, when it gives us the answer $h^{zw} \bmod n$, we would then map it back to $\bmod p$, which is the answer to the original problem.

Now, the above logic does not rule out a method of using an RSA oracle that involves solving for $n'$ values other than the modulus from the generalized DH problem. However, as I mentioned in the intro, that doesn't immediately sound likely.