# 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$$?

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:  17
Bob Sends Over Public Chanel:  4

Privately Calculated Shared Secret:

Alice Shared Secret:  8
Bob Shared Secret:  8


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

• 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. – Meysam Ghahramani Jun 29 at 18:03