# Demonstrating Diffie-Hellman key exchange using only p, A, B;

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.

-
I believe you'll also need the value of $g$; you cannot derive it with the information you have –  poncho Apr 1 at 4:39
I have to be able to get the value of g given this information, but I'm unsure of how to do it. –  EGHDK Apr 1 at 6:30
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. –  poncho Apr 1 at 12:58

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.

-
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? –  poncho Apr 1 at 13:11
Is this basically what this video is showing 5 minutes 10 seconds into it? youtube.com/watch?v=YEBfamv-_do –  EGHDK Apr 1 at 17:41
@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. –  DrLecter Apr 1 at 19:11
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. –  qbyte Apr 2 at 1:54
@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$. –  DrLecter Apr 3 at 6:01