# 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}$.

-
It would be good to precisely state the Diffie-Hellman problem: Given $g$, $p$, $g^a \pmod p$ and $g^b \pmod p$, find the value of $g^{ab} \pmod p$. – ShreevatsaR Sep 5 '10 at 23:52
What do you mean by "low"? Do you mean small as an integer, e.g. g=2, 3, 5, etc.? – James K Polk Sep 6 '10 at 0:15
@ShreevatsaR I'll add it. – Baldur Sep 6 '10 at 0:20
@GregS Yes, I'm thinking of an integer less than 10 – Baldur Sep 6 '10 at 0:21
@Dan Brumleve, as far as I know there is no known algorithm that can take advantage of small generators for solving the Diffie-Hellman problem more efficiently. 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). – Accipitridae Sep 14 '10 at 20:04

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).

-

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\}$
-