# DH Key Exchange Protocol

Since I am not able to comment under the topic, I would like to ask here why in question 2 old post, we cannot distinguish the two distributions, even with unlimited computational power? Also, what can be said about the distribution of exponents a+b modp when b is taken at random from Zp, but a is fixed?

Any help would be appreciated a lot.

It's easier to take the questions out of order.

what can be said about the distribution of exponents a+b mod p when b is taken at random from Zp, but a is fixed?

If $$b$$ is a uniform independent random value from the range $$[0, p-1]$$, that is, the probability of each possible value is $$1/p$$, and $$b$$ is distributed independently from $$a$$, then $$a+b \bmod p$$ is a uniform independent (of $$a$$) random value from the range $$[0, p-1]$$; that is, the probability of $$a+b \bmod p$$ being any possible value from the range is also $$1/p$$, and information about the distribution of $$a$$ (such as having it be a fixed value) does not change this.

The easiest way to see this (for a fixed $$a$$) is to note that, for any target value $$c = a+b \bmod p$$, there is a unique value of $$b = c-a \bmod p$$ that must be selected for the value $$a+b \bmod p$$ to be that value. The probability of $$b = c-a \bmod p$$ occurring is $$1/p$$ (because that value is in the range, and we assumed the probability of all values in that range be $$1/p$$), hence the probability that $$c = a+b \bmod p$$ is also $$1/p$$.

With this, your first question is easy:

I would like to ask here why in question 2 old post, we cannot distinguish the two distributions, even with unlimited computational power?

Alice sees either $$g^b$$ or $$g^{a+b}$$; an adversary with unlimited computational power can solve the discrete log, however that gives him either $$b$$ or $$a+b$$ (for random $$b$$); both probability distributations are identical, and so he cannot distinguish them.

• Thank you very much for your help. One last question. Why the value of a must be a fixed value? – user178592 Jan 6 at 6:30
• @user178592: it doesn't - the only requirement is that b be distributed independently of a. Assuming a fixed a just make the demonstration easier.. – poncho Jan 6 at 14:43