2
$\begingroup$

I'm trying to figure out how to demonstrate DH key exchange using what is given to me. I'm unsure of how to tackle the problem.

Question:

Demonstrate Diffie-Hellman key exchange.

Given p=104933, A=324, B=5832. Prime factors for p-1 {2,37,709}

A and B are Alice and Bob secret keys respectively.

What is the value of the shared key?

Process to solve:

So there are 5 steps to DH key exchange.

  1. Alice and Bob share prime p and generator g
  2. Alice sends g^a mod p to Bob
  3. Bob sends g^b mod p to Alice
  4. Alice computes the shared key
  5. Bob computes the shared key

I get stuck at step 1 though because I'm unsure of how I'm supposed to find the generator given this information.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I believe you'll also need the value of $g$; you cannot derive it with the information you have $\endgroup$
    – poncho
    Commented Apr 1, 2014 at 4:39
  • $\begingroup$ I have to be able to get the value of g given this information, but I'm unsure of how to do it. $\endgroup$
    – EGHDK
    Commented Apr 1, 2014 at 6:30
  • 1
    $\begingroup$ No, there is not enough information given to let you derive $g$. Now, if they said "use the smallest value that generates the group for $g$", then you could find that, and then use that. However, remember that any value of $g$ will work within the protocol (although some choices, such as $g=1$, do have some security issues, of course, in this toy example, there aren't any secure choices). Also, in practice, we generally don't use values of $g$ which generate the entire group, and so you are told to use such a value, that's something contrary to common practice. $\endgroup$
    – poncho
    Commented Apr 1, 2014 at 12:58

1 Answer 1

Reset to default
2
$\begingroup$

I guess the problem is to find the generator $g$.

Denote the factors for $p-1$ to be $p_1 =2, p_2 =2,p_3 = 37, p_4 = 709$.

With $p$, and the factorization of $\phi(p)$ you can find a generator in the following way:

Randomly choose an element $x$ from $Z_p$ and test whether $x^{\phi(p)/p_i}$ mod $p \ne 1$ for every $i =1,2,3,4$. If this is the case, $x$ is a generator. Otherwise, just select another element to run the test. You should find one soon. (Please refer to wikipedia for the method.)

Since $5^{2\times 37 \times 709}$ mod 104933 = 104932, $5^{2\times 2 \times 709}$ mod 104933 = 45751, $5^{2\times 2 \times 37}$ mod 104933 = 92770. Then 5 is a generator.

Next steps are basic algebra, I will stop here.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ There are 50976 generators for $Z/104933$, and that's assuming that, by generator, the question meant a generator for the entire group, and not the generator for the subgroup we'll be doing DH in. So, 5 is a generator; how do we know that that's the generator that's meant, and not any of the 50975 other generators that exist? $\endgroup$
    – poncho
    Commented Apr 1, 2014 at 13:11
  • $\begingroup$ Is this basically what this video is showing 5 minutes 10 seconds into it? youtube.com/watch?v=YEBfamv-_do $\endgroup$
    – EGHDK
    Commented Apr 1, 2014 at 17:41
  • 1
    $\begingroup$ @qbyte Every generator $g$ of $Z_{104933}^*$ will yield private keys for A and B such that the public keys for A and B are 324 and 5832 respectively. Simply because every element of $Z_{104933}^*$ can be written as a power of g for every possible choice of the generator g. So this question cannot be answered as poncho says. $\endgroup$
    – DrLecter
    Commented Apr 1, 2014 at 19:11
  • $\begingroup$ Any generator $g$ (by generator, of course it generates the entire group) will work for Diffie-Hellman in my opinion. And the shared key would be $g^{ab}$ mod $p$. So, different generators result in different keys to be shared between A and B. However, that is irrelevant to the fact that any generator works. $\endgroup$
    – qbyte
    Commented Apr 2, 2014 at 1:54
  • 1
    $\begingroup$ @qbyte yes. But since the used value of $g$ is missing in the question and any choice for the generator will produce different private keys that yield to the given public keys you cannot uniquely determine the value for $g^{ab}$ as this value will be different for every choice oft $g$. $\endgroup$
    – DrLecter
    Commented Apr 3, 2014 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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