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

Question

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<p$ and sends $A\leftarrow g^a \mod p$ to Bob;

• Bob randomly chooses $b<p$ 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$?

Answer 1

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.

Answer 2

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).