3
$\begingroup$

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

  • 0
    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$.2010-09-05
  • 0
    What do you mean by "low"? Do you mean small as an integer, e.g. g=2, 3, 5, etc.?2010-09-06
  • 0
    @ShreevatsaR I'll add it.2010-09-06
  • 0
    @GregS Yes, I'm thinking of an integer less than 102010-09-06
  • 0
    One (horribly inefficient) way would be to take the discrete logarithms of both $g^a \mod p$ and $g^b \mod p$ (using e.g. Pollard ρ), multiply a and b, and perform modular exponentiation again with the product as the exponent.2010-09-06
  • 0
    It has been my understanding that there are methods (Pollard factorization?) which are faster on average for small g and so I have always chosen a random and verified g. Sorry that I can't remember why.2010-09-06
  • 4
    @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).2010-09-14

2 Answers 2

2

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

2

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:

enter image description here

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:

enter image description here

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