Problem: You see Michael and Nikita agree on a secret key using the Diffie-Hellman key exchange. Michael and Nikita choose $p = 97$ and $g = 5$.
Nikita chooses a random number n and tells Michael that $g^n \equiv 3\pmod{97}$, and Michael chooses a random number $m$ and tells Nikita
that $g^m ≡ 7 \pmod{97}$. Brute force crack their code: What is the
secret key that Nikita and Michael agree upon? What is $n$? What
is $m$?
This is how the Diffie-Hellman exchange is defined in the textbook:
- Together Michael and Nikita choose a 200-digit integer p that is likely
to be prime, and choose a number $g$ with $1 < g < p$.
- Nikita secretly chooses an integer $n$.
- Michael secretly chooses an integer $m$.
- Nikita computes $g^n \pmod{p}$ on her handheld computer and tells
Michael the resulting number over the phone.
- Michael tells Nikita $g^m \pmod{p}$.
- The shared secret key is then $s\equiv g^{nm}\pmod{p}$
which both Nikita and Michael can compute.
My thoughts/attempts:
Attempt 1. I tried to find $n$ through solving the modular equation $5^n\equiv 3\pmod{97}.$ Then we have $n\equiv \log_53\pmod{97},$ which is not an integer and thus doesn't make sense.
Attempt 2. I tried to find the key using $g^n$ and $g^m.$ However, I don't see a way to reach $g^{nm}$ since $g^ng^m = g^{n+m},$ and we cannot calculate $(g^n)^m$ or $(g^m)^n$ without knowing $m$ or $n,$
which from Attempt 1 I can't find integers for.
Would appreciate help! Thank you