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