Let $ALG_2$ be an algorithm that solves the RSA problem, can it solve the generalized Diffie-Hellman problem? 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?
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:


Pick $g$ and $h$ uniformly at random.
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).$$

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.

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.