# In a Diffie-Hellman key exchange Find this key and compute the shared secret key k

Hi I struggling to find the answer of my schhol exam, can anyone help me .

In a Diffie-Hellman key exchange the multiplicative group of integers modulo p is used with the parameters p = 59, g = 3 mod 59. The public keys A = 28 and B = 36 are exchanged. One of the private keys is relatively small. Find this key and compute the shared secret key k.

I know how to find the shared secret key but i do not know how to find private key that is small.

• Are you aware of how the public keys are derived from the private keys? Combine this with the exercise's hint that one of the private keys is 'relatively small' - can you then think of how to figure out said private key? Commented Aug 20, 2022 at 10:06
• Per policy, homework questions must come with description of what has been tried/where one is stuck. Thus I'll only give some clarification of that homework. What it names "public keys" is what's exchanged between the communicating parties; and what it names "private key" is what this names "secret integer".
– fgrieu
Commented Aug 20, 2022 at 10:32
• – Yen
Commented Aug 21, 2022 at 9:22
• I'm looking for the same problem. Can anyone please help me how to find it. Thank you Commented Sep 2, 2022 at 10:22
• @radha gudala: please read this the content of chat. You should be able to talk, too. If you want to ping me, include "@ fgrieu" at the end of the message, without the quotes and with the space moved BEFORE the @ sign.
– fgrieu
Commented Sep 2, 2022 at 12:39

Hearing that the private key is relatively small means that probably you could compute it via brute-force, meaning just trying values until you find the answer.

So, you have your generator $$g=3$$ and you can just start trying small exponents. Eventually, you would find that $$g^9 \equiv 36 \mod 59$$.

Therefore, you now know that B's private key is $$b=9$$. From that, you just continue the protocol as if you were B to find eventually the shared key to be 5.

• Yes. Additionally, it's inexpensive to go from one private key tried to the next: all there is to do is multiply by $g$ modulo $p$. The computations go: $g^1\bmod p=3\bmod59=3$, $g^2\bmod p=3×3\bmod59=9$, $g^3\bmod p=9×3\bmod59=27$, $g^4\bmod p=27×3\bmod59=22$, $g^5\bmod p=22×3\bmod59=7$, $g^6\bmod p=7×3\bmod59=21$, $g^7\bmod p=21×3\bmod59=4$, $g^8\bmod p=4×3\bmod59=12$, $g^9\bmod p=12×3\bmod59=36$, matching B (we would have stopped if we matched A).
– fgrieu
Commented Sep 4, 2022 at 15:58

We should be able to brute-force it easily.

i = 3
iteration = 1

while True:
if i % 59 == 28:
print(f'28: {iteration}')
break
if i % 59 == 36:
print(f'36: {iteration}')
break
i *= 3
iteration += 1


FYI: 9 was printed out.

• @fgrieu should be good now (: Commented Sep 5, 2022 at 6:03
• It now works. A possible improvement is to prevent i from growing unnecessarily large. Replacing the current i *= 3 by i = i*3 % 59 and removing the two earlier % 59 fixes that. Perhaps I would also start at i = 1 with iteration = 0, with the benefit that $g$ and $p$ now appear only at a single place.
– fgrieu
Commented Sep 5, 2022 at 6:16