# Relations between RSA and Generalized Diffie-Hellman (GDH), factoring and GDH

Definition: (The generalized Diffie-Hellman problem)

Let $$n=pq$$ for two large primes $$p,q$$. Given $$x, x^a, x^b,n$$, find $$x^{ab}\pmod{n}$$.

(1) Is there a known reduction from the GDH problem to the RSA problem (i.e. finding $$m$$ from $$m^e\pmod{n}$$)?

(2) Is there a known reduction from the GDH problem to integer factorization?

(That is, given an oracle which solves the second problem mentioned in (1)/(2), can you find an efficient algorithm which solves the GDH problem?)

Side-notes:

1. There is of course a reduction from GDH to DLOG, but I do not know of a reduction from DLOG to integer factorization or to the RSA problem.

2. It is known that the RSA problem limited to $$e=2$$ (i.e. finding square roots modulo $$p$$) can be reduced to integer factorization, but this is a non-interesting case. For a general $$e$$, AFAIK such reduction is not known.

3. Also, I am just as interested to hear about DH instead of GDH. (The DH problem is the same as GDH, but with a prime $$p$$ instead of semiprime $$n$$.)

• Unless I'm mistaken, the RSA problem is simple to reduce to integer factorization (factor $n$, compute $\varphi(n)$ with the factorization, compute $d=e^{-1}\pmod{\varphi(n)}$, compute $m=(m^e)^d\pmod{n}$; this is exactly how decrypting RSA is actually done). Jan 3 '15 at 17:24
• @cpast: however, that reduction is the wrong direction; if you have a black box that solves the RSA problem, there is no known way to use it to efficiently factor. This leaves open the possibility that the RSA problem is easier than factoring. Jan 3 '15 at 17:49
• @poncho Then the statement should be "there is no known way to reduce factorization to RSA," not vice versa. So if DLOG reduced to RSA it would reduce to factoring, but not necessarily vice versa. Jan 3 '15 at 18:09
• Who says $e = 2$ is non-interesting? $e = 2$ is great! Best performance (when $p \equiv q \equiv 3 \pmod 4$, anyway), clearest connection to factoring, More: cr.yp.to/papers.html#rwsota Mar 8 '19 at 6:02

• Nit: Biham et al did not show equivalence (nor did they claim it); instead, they showed that factoring reduces to the GDH problem - however, they did not show the other way around (and it would appear to be difficult to show; being able to factor N certainly does not imply you can solve the GDH problem modulo N; otherwise, an attacker wanting to solve the DH problem modulo a prime $p$ can pick a $q$, map the DH problem to a GDH problem modulo $pq$, and solve that using the known factorization of $pq$). Perhaps factoring other composites would help you solve GDH - it looks unlikely... May 11 '20 at 18:48