Solving Diffie–Hellman problem for low primitive root What's a good way of solving the Diffie–Hellman problem when those exchanging the message have chosen a low primitive root $g$ (e.g. $g=3$)?
Of course you could brute force it but I'm interested in knowing whether there is a formula for solving it when you know $g^a \pmod{p}$ and $g^b \pmod{p}$ as well as $p$ and $g$ of course.
Edit: For those unfamiliar with the Diffie–Hellman problem the integers $g$ and $p$ (with $1 < g < p$ and $p$ being prime), $g^a \pmod{p}$ and $g^b \pmod{p}$ are public. The integers $a$ and $b$ are private integers and we want to calculate the secret key $s = g^{ab} \pmod{p}$.
 A: Diffie–Hellman is a protocol for data exchange with no shared secret.
It already assumes that you know $p$, $g$, $g^a\pmod{p}$ and $g^b\pmod{p}$.
So under the protocol assumptions, the answer to your question is no.

Public Information:


*

*Prime number $p$

*Generator $g\in{Z^*_p}$


Protocol:

Advantage of Alice and Bob over Eve:


*

*Alice and Bob can easily compute $k=g^{ab}$

*Eve intercepts $g^a$ and $g^b$, but cannot easily compute $g^{ab}$


Terminology:

Assumptions:


*

*$DLOG$ holds in the Diffie-Hellman protocol

*$CDH$ holds in the Diffie-Hellman protocol


Of course, if either one of these assumptions is false, then the answer to your question is yes.

Prove $CDH \implies DLOG$:


*

*$\neg DLOG \implies$ Given $g$ and $g^x$, it’s easy to compute $x$

*So given $g$, $g^a$ and $g^b$, one can easily compute $a$ and $b$, and then compute $g^{ab}$

*Conclusion: $\neg DLOG \implies \neg CDH$


Prove $DDH \implies CDH$:


*

*$\neg CDH \implies$ Given $g$, $g^x$ and $g^y$, it’s easy to compute $g^{xy}$

*So given $g$, $g^a$, $g^b$ and $g^c$, one can easily compute $g^{ab}$, and then compare it with $g^c$

*Conclusion: $\neg CDH \implies \neg DDH$


Prove $DDH$ does not hold in the Diffie-Hellman protocol:


*

*For random $a,b\in{Z_p}:ab$ is even with probability $\frac{3}{4} \implies g^{ab}\in{QR_p}$ with probability $\frac{3}{4}$

*For random $c\in{Z_p}:c$ is even with probability $\frac{1}{2} \implies g^{c}\in{QR_p}$ with probability $\frac{1}{2}$

*Solution:


*

*Prime numbers $p$ and $q$, s.t, $p=2q+1$

*Generator $g\in{QR_p}$ (instead of $g\in{Z^*_p}$)


*Example:


*

*$p=11 , Z^*_p = \{1,2,3,4,5,6,7,8,9,10\}$

*$q=5  , QR_p  = \{1,3,4,5,9\}           $


A: What you are asking is what is known as the discrete logarithm problem. The reason Diffie-Hellman is good for large numbers is that solving the discrete logarithm, in general, is hard. It there was a formula we knew for it, this wouldn't be good for DH-cryptography. I will copy the rest of my answer from Accipitridae: 

However, there are some other DL based cryptosystems, where choosing a small generator may indeed be a problem. One such example is the Elgamal signature scheme. An attack here is described in the "Handbook of applied cryptography" (Chapter 11, Note 11.67). 

