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
3  
@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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.