# How to know if you have guessed the correct Diffie-Hellman shared secret?

Given only $$p,$$ $$g,$$ $$A = g^a\pmod{p}$$ and $$B = g^b\pmod{p},$$ the possible values for the shared secret are all the unique values of $$A^b\pmod{p}$$, where b is some integer. The shared secret is also equal to $$B^a\pmod{p}$$, where a is some integer.

So, we can check each one of these possible values for the shared secret. My question is, how do we check if a number is the correct shared secret?

My guess is this:

Usually the shared secret is used in a symmetric encryption scheme, the overall terms of which must logically be agreed upon in the public channel. So from our vantage point, we would know what type of symmetric encryption is being used, and therefore how the shared secret is being used, and could therefore try decrypting a given message with each possible shared secret until we find one that gives us the original, unencrypted message. But then we would have to know what the original unencrypted message should look like.

• As we known, the security of DH protocol is mainly based on the discrete logarithm problem. If $|p|$ is very large, then no PPT algorithm can sovle this problem. I suggest you read some cryptographic book to further understand this point. Nov 13, 2021 at 3:50

In practice, the number of possible values for the shared secret is too large for scanning over all the possibilities to be practical - there are always easier attacks. And, as you appear to have guessed correctly, recognizing the shared secret based on $$g, g^a \bmod p, g^b \bmod p$$ is believed to be a hard problem (in fact, we call it the "Decisional Diffie-Hellman problem")
One attack is to take $$g$$ and $$g^a \bmod p$$ and attempt to recover $$a$$ (that is, solve the discrete log problem) - once we have $$a$$, we can compute $$B^a \bmod p$$ (which is the shared secret), and that's the shared secret.
For both of these attacks, we typically select security parameters (such as the size of $$p$$ and the size of the symmetric key) to make both these approaches infeasible.
• The thing is, the discrete logarithm problem has infinite solutions, because there are infinite values for $a$ that satisfy $g^a\pmod{p} = A$ where A is some number in the set {1,...,p-1}. That's what confuses me when people say "solve the discrete logarithm problem". Afaik solving it would just come down again to guessing and checking different possible $a$ values, and so this is just a more computationally intensive version of the Decisional DH problem. Nov 13, 2021 at 20:41
• @user363406: if we find any solution $a$, then we can find all the other solutions by adding or subtracting multiples of $q$ (where $q$ is the order of $g$). Another way of saying this is that there is (at most) one solution in the range $[0, q)$; since we usually know the value of $q$, we can say that there is a "unique" solution. BTW: there are known groups where the decisional DH problem is known to be easy (given the values $g, g^a, g^b, g^{c}$, we can always determine if $g^{ab} = g^c$), and the computational DH problem is believed hard - hence the cDH problem appears inherently harder Nov 13, 2021 at 21:33