Score:1

Cracking secret key, n, and m by hand with the Diffie-Hellman key exchange brute force

us flag

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:

  1. 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$.
  2. Nikita secretly chooses an integer $n$.
  3. Michael secretly chooses an integer $m$.
  4. Nikita computes $g^n \pmod{p}$ on her handheld computer and tells Michael the resulting number over the phone.
  5. Michael tells Nikita $g^m \pmod{p}$.
  6. 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

DannyNiu avatar
vu flag
Attempt 1 is on the right track. It should be noted that, the logarithm is discrete, so the real number log function is not applicable here. It should be an integer, and as you said, otherwise it doesn't make sense.
BoostMatch avatar
us flag
How can you solve it if it's a discrete log?
DannyNiu avatar
vu flag
Brutal-force (trying one by one) is good for small numbers like that in your exercise. Hackers would use mathematical techniques such as Pollard-rho or general number field sieve (GNFS).
BoostMatch avatar
us flag
@DannyNiu Oh, hence the "brute force" in the exercise!
kelalaka avatar
in flag
With a small program while constructing the [the index table](https://crypto.stackexchange.com/a/76241/18298) find your desired value.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.