Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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.? –  GregS 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
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). –  Accipitridae Sep 14 '10 at 20:04

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.