# What happens if we choose the random secret keys in Diffie-Hellman greater than prime?

Diffie-Hellman works as follows:

Given public parameters $$p$$ (a large prime) and $$g$$ (always referred to as a generator of $$(\mathbb{Z}^∗_p)$$. Then:

• Alice randomly chooses $$a and sends $$A\leftarrow g^a \mod p$$ to Bob;

• Bob randomly chooses $$b and sends $$B\leftarrow g^b \mod p$$ to Alice;

• Alice computes $$S\leftarrow B^a \mod p$$;

• Bob computes $$S\leftarrow A^b \mod p$$.

What happens if we choose $$a$$ and $$b$$ grater than $$p$$?

• I'd just try this myself :) Commented Jan 30, 2019 at 14:41
• Hint: apply Fermat's Little Theorem.
– fgrieu
Commented Jan 30, 2019 at 15:18
• g (usually) generates a subgroup of $Z_p^*$, see the autorecommended crypto.stackexchange.com/questions/828/… Commented Jan 31, 2019 at 2:15

The modulus operation $$\pmod p$$ is performed at each step and reduces the result into $$\bmod p$$. And a clever implementation can use the Fermat's Little Theorem instead of taking the power than reducing to modulo $$p$$. After that it's possible to use the modular version of repeated squares algorithm or similar.

Example 1) code used from sublimerobots

sharedPrime = 23    # p
sharedBase = 5      # g

aliceSecret = 600     # a
bobSecret = 1500      # b

Alice Sends Over Public Chanel:  8
Bob Sends Over Public Chanel:  4

Privately Calculated Shared Secret:
Alice Shared Secret:  2
Bob Shared Secret:  2


Example 2)

sharedPrime = 23    # p
sharedBase = 5      # g

aliceSecret = 6000000     # a
bobSecret = 15000000   # b

Alice Sends Over Public Chanel:  8
Bob Sends Over Public Chanel:  4

Privately Calculated Shared Secret:
Alice Shared Secret:  2
Bob Shared Secret:  2


I think you are confusing the mathematical representation and the actual value.

In the sense of optimization, the code from sublimerobots is not good. Actually. instead of

bobSharedSecret = (A**bobSecret) % sharedPrime


a faster version

bobSharedSecret = pow(A,bobSecret,sharedPrime)


which uses modular binary exponentiation.

• Dear @kelalaka, I think that something is wrong with your answer. In example 2, you said $5^{6000000} \bmod 23 =17$ but this is wrong. Commented Jun 29, 2019 at 18:03
• Two remarks: A] use of FLT is optional, and only provides a time saving by a factor like $\log(a)/\log(p)$ (about 2 in the first example, about 5 in the second). B] As pointed in above comment, the values in the second example are wrong.
– fgrieu
Commented Oct 27, 2019 at 19:15
• @fgrieu I don't know why it was a mistake and why I did not correct it. I've used code to generate! Thanks. Commented Oct 27, 2019 at 19:38

It could have three consequences.

1) If you are very unlucky, and you pick a "zero" ($$a$$ such that $$a=0\mod p-1$$), it will break your system : (but this will happen with a negligible probability, and it could be detected) An external observer will easily guess the shared secret

2) You lose in efficiency

3) Your integer had to be chosen upper-bounded (you can not pick uniformly over all the integers, if you choose badly this point (something not divisible by $$p$$), it will create a bias in the distribution of your keys (probably not a problem in practice, but in theory it's less secure).

• $a\equiv0\pmod p$ does not seem to matter. $a\equiv0\pmod{p-1}$ matters in that it will make the shared secret always $1$, which is insecure; but the two parties still hold the same shared secret. You get $a\equiv0\pmod{p-1}$ using $a\equiv 0\pmod{p-1}$.
– fgrieu
Commented Oct 28, 2019 at 12:42
• you are alright about the (p-1), I put more precision about "break" Commented Oct 28, 2019 at 12:46