# Reversing Diffie Hellman from the secret

This is a homework assignment that's been giving me some trouble:

By eavesdropping on a Diffie-Hellman key exchange, we observe

modulus $$p$$

the base $$3$$

$$A\ =\ 3^a \bmod p\quad$$ and

$$B\ =\ 3^b \bmod p$$

If we somehow had access to the secret $$=\ 3^{ab} \bmod p$$, how could you retrieve the secret exponents $$a$$ and $$b$$?

$$p$$ is 996-bit. $$A$$, $$B$$ also are very large numbers. I think I am missing something about exponential arithmetic. I've tried working on the actual numbers using PARI/GP, but the numbers are too big to use the built-in discrete logarithm functionality.

• Common wisdom is that with $p$ , $3^a\bmod p$ and $3^b\bmod p$ known, additional knowledge of $3^{ab}\bmod p$ does not help decisively towards finding $a$ and $b$, for random choice of these. Also, in unauthenticated DH key exchange, the attacker only wants $a$ and $b$ in order to find $3^{ab}\bmod p$, thus it seems strange to assume that the later is known. Did you test if $p$ is prime? If it (or its factors if it is composite) is of the special form $\dfrac{r^e\pm s}t$ making SNFS possible? – fgrieu Mar 5 '19 at 8:17
• If $p$ is prime, do you know the factorization of $p-1$? Even if you can get its partial factorization, if the order of 3 consists solely of small factors, solving the discrete log problem to obtain $a$ or $b$ is easy... – poncho Mar 5 '19 at 14:12