0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – Morrolan
    Aug 20, 2022 at 10:06
  • $\begingroup$ 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". $\endgroup$
    – fgrieu ♦
    Aug 20, 2022 at 10:32
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Yen
    Aug 21, 2022 at 9:22
  • $\begingroup$ I'm looking for the same problem. Can anyone please help me how to find it. Thank you $\endgroup$
    – radha gudala
    Sep 2, 2022 at 10:22
  • $\begingroup$ @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. $\endgroup$
    – fgrieu ♦
    Sep 2, 2022 at 12:39

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$
    – fgrieu ♦
    Sep 4, 2022 at 15:58
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ @fgrieu should be good now (: $\endgroup$
    – Abra Cadabra
    Sep 5, 2022 at 6:03
  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Sep 5, 2022 at 6:16

Your Answer

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

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